- #1
roadrunner
- 103
- 0
1) Problem 1 For every i; j with 1<=i; j<=8 fi nd a nim heap which is equivalent to the i x j
game of Chop.
CHOP Game Start with an i x j array of boxes viewed as a plank which
is secured only at the lower left hand corner. Each player is a
pirate, and they alternate turns. On each turn a player must
either make a vertical or horizontal chop of the plank, and then
any piece no longer connected to the lower left hand corner falls
off into the water. The player who moves last wins.
What I need to do
Generalize the result of Problem 1 by finding a general formula for the nim heap
equivalent to an i x j game of Chop.
What I did
Essentially the way we were showed in class was to start with a 1x1 and then 1x2, 2x2, 2x3,3x3,etc chop game and determine the "small base cases" and work our way up. after we had a 2x2 grid,
1 0
0 1
He said that each new board was simple the smallest value not present in the corresponding row and column.
For example: If i had the below configuration and wanted to know X, I would look at the 2,3,0 and 2,3 and notice that no 1 is present, therefore X=1
2 3 0 X
1 0 3 2
0 1 2 3
I did this up to i,j=11
10 11 8 9 14 15 12 13 2 3 0
9 8 11 10 13 12 15 14 1 0 3
8 9 10 11 12 13 14 15 0 1 2
7 6 5 4 3 2 1 0 15 14 13
6 7 4 5 2 3 0 1 14 15 12
5 4 7 6 1 0 3 2 13 12 15
4 5 6 7 0 1 2 3 12 13 14
3 2 1 0 7 6 5 4 11 10 9
2 3 0 1 6 7 4 5 10 11 8
1 0 3 2 5 4 7 6 9 8 11
0 1 2 3 4 5 6 7 8 9 10
I can see some patterns in the table but none that apply in all cases...I have no idea where to go with this!
Thanks
PS: SOrry the grid doesn't line up perfectly, not sure how to do ASCII in here or post a table
game of Chop.
CHOP Game Start with an i x j array of boxes viewed as a plank which
is secured only at the lower left hand corner. Each player is a
pirate, and they alternate turns. On each turn a player must
either make a vertical or horizontal chop of the plank, and then
any piece no longer connected to the lower left hand corner falls
off into the water. The player who moves last wins.
What I need to do
Generalize the result of Problem 1 by finding a general formula for the nim heap
equivalent to an i x j game of Chop.
What I did
Essentially the way we were showed in class was to start with a 1x1 and then 1x2, 2x2, 2x3,3x3,etc chop game and determine the "small base cases" and work our way up. after we had a 2x2 grid,
1 0
0 1
He said that each new board was simple the smallest value not present in the corresponding row and column.
For example: If i had the below configuration and wanted to know X, I would look at the 2,3,0 and 2,3 and notice that no 1 is present, therefore X=1
2 3 0 X
1 0 3 2
0 1 2 3
I did this up to i,j=11
10 11 8 9 14 15 12 13 2 3 0
9 8 11 10 13 12 15 14 1 0 3
8 9 10 11 12 13 14 15 0 1 2
7 6 5 4 3 2 1 0 15 14 13
6 7 4 5 2 3 0 1 14 15 12
5 4 7 6 1 0 3 2 13 12 15
4 5 6 7 0 1 2 3 12 13 14
3 2 1 0 7 6 5 4 11 10 9
2 3 0 1 6 7 4 5 10 11 8
1 0 3 2 5 4 7 6 9 8 11
0 1 2 3 4 5 6 7 8 9 10
I can see some patterns in the table but none that apply in all cases...I have no idea where to go with this!
Thanks
PS: SOrry the grid doesn't line up perfectly, not sure how to do ASCII in here or post a table