The Grim Game of Nim
Suppose you and an opponent are playing a game of Nim with a beginning board as follows:
Players take turns removing balls from the board according to the following rules:
- For your turn, you may remove as many balls from any single row of the array as you like.
- Removing balls from multiple rows in one turn is forbidden.
- You must take at least one ball from a row for your turn.
- Whoever takes the last ball loses.
It is agreed that your opponent makes the first move, but as compensation you may, if you choose to, add one new row of as many balls as you'd like to the board above.
Assuming that your opponent plays optimally and you want to guarantee yourself a win, how many balls should you place in the new row to be added?
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
1 solution
Thanks for writing up the solution!
Ok I think I know what went wrong with my calculation. 8 should have been written as 2^3 and not 2^2+2^2 and 4 should have been written as 2^2 instead of 2^1+2^1. Now, we can clearly see that 4 and 8 has no pairs since all other numbers from 1-7 has been paired up.
You might like to hunt online for the literature about Nim, and (in this case) misère Nim. What you are calling "balanced" is what is more normally described as "having Nim-sum 0 ". The Nim-sum of a board is the binary sum (without carrying) of the numbers in each pile. A board with Nim-sum 0 , and with at least one pile with more than 1 in it, is a guaranteed win for the second player, which is what we want here, as follows:
- Any play from a board with Nim-sum 0 results in a board with nonzero Nim-sum.
- When faced with a board with nonzero Nim-sum, a play can always be made to produce a board with Nim-sum zero.
- If the first player always has a Nim-sum 0 board to play from, and if there is initially at least one pile with more than one counter in it, then at some time in the future the second player must be presented with a board with all piles except one having one counter in it. The second player then either takes the whole of this bigger pile, or else all but one of that pile, to leave the first player with an odd number of piles, each with one counter in it.
Log in to reply
Oh wow I didn't realize that all of this stuff had actual names! I'll check it out!
Log in to reply
There is a thing called the Grundy function, which can be used to determine optimal strategies for a wide variety of Nim-like games. Check it out.
yes but putting 8 and 4 also keeps the board balanced. No? 8=2^2+2^2 and 4=2^1+2^1
Log in to reply
I'm not exactly sure what you mean.
We can only add one row, so multiple rows are out of the question.
Also, although 8 and 4 are composed of the sum of two identical powers of two, we check vertically to see if the columns are balanced. Here is an example of why 8 won't work:
| 1 | 0 | 0 | 0 |
| 0 | 1 | 1 | 1 |
| 0 | 1 | 1 | 0 |
| 0 | 1 | 0 | 1 |
| 0 | 1 | 0 | 0 |
| 0 | 0 | 1 | 1 |
| 0 | 0 | 1 | 0 |
| 0 | 0 | 0 | 1 |
This would be the game state described by adding a new row of 8 . Note that the left-most column has only a single one bit going down. This would make the game state unbalanced, and our opponent can win simply by clearing the top-most row.
yes i meant adding either 4 or 8, not 4 and 8. typo.
Log in to reply
Ok, I get what you're saying now. The table in my previous comment indeed shows the case for 8 . The 8 ′ s column would become unbalanced since there is only a single one bit in the column. If we tried 4 :
| 1 | 0 | 0 |
| 1 | 1 | 1 |
| 1 | 1 | 0 |
| 1 | 0 | 1 |
| 1 | 0 | 0 |
| 0 | 1 | 1 |
| 0 | 1 | 0 |
| 0 | 0 | 1 |
Then the 4 ′ s column would have five 1 bits in it, which is of course odd and unbalanced.
Just saw your comment. When I say adding the bits in a column I mean picking a single column and adding all of the bits in that column. Does that help?
I think I am thinking of adding columns instead of rows...
I do not choose to add a new row. 1--2-3-4-5-6-7 is a winning setup if my oponent starts.
Here is a general strategy for winning any game of Nim with the above rule set:
First, we need to convert the board to a binary array. This will be done simply by taking the number of balls in a given row and making it into a binary number. For example:
For example, the first and third columns of the above binary arrays are balanced, since their bits sum up to 2 , which is even. However, the middle column is not, since its bits sum up to 1 , which is odd.
For example, the middle column of the above game state is unbalanced, so the game state is also unbalanced.
Now, we will come up with a strategy according to the following two lemmas:
Proof: By definition, every columns is balanced in a balanced game state, so the parity of the 1 bits in every column is even. Since we will be removing balls from a row, that binary value will decrease, thus resulting in at least one of the 1 bits turning into a 0 bit. Since this occurs in a single row, the column where this occurs will be unbalanced, thus resulting in an unbalanced game state. □
Proof: Suppose we have an arbitrary unbalanced game state, where the largest unbalanced column is column i . Now choose a row j in column i such that its bit is a 1 . Call this bit k . Now, use subtraction to clear out all bits to the right of bit k in column j . We can now subtract one more from row j , which balances column i and places a 1 bit in every column in row j . We can now go one-by-one through each column to the right of column i and see if it is balanced. If it is, we leave the row- j bit in that column alone. If it is not balanced, we simply subtract out that bit's value.
Here is an explicit example of the process for some grid:
Hence, a state can always be made balanced again in one move. □ .
Putting this together, a balanced state will always be made unbalanced, and an unbalanced state can always be made balanced. Now, consider the following:
Now, consider the following two lemmas:
Proof: Consider the final state of one ball. If that was not the beginning of the game, then there was a previous move, which either took from the same row as the final ball (satisfying the critical turn condition) or from a different row.
We can continue this train of logic for the different row; if there was more than one ball in the row, then the critical turn occurred. Otherwise, if there was one ball remaining in the different row and the game was not two rows of one ball, we can look at a third row. Etc.
Eventually, this will resolve either by a critical turn happening, or the game beginning as a single column of n balls. We assumed that the latter did not occur, and so a critical turn must have happened that game. □ .
Proof: Look at the one and only row with more than one ball remaining. Remove all but one ball from that row and analyze the current game state. If it is unbalanced, end your turn. Otherwise, remove the last ball from the row.
This will guarantee a win since your opponent is now forced to make essentially the same move every single time, which is removing a single ball from one of the remaining rows. Leaving an unbalanced board state for your opponent (which both of the above cases will do) will force your opponent to leave a balanced board state, and you to never leave a balanced board state by Lemma 1 .
Because an empty board state is a balanced state, your opponent MUST take the final ball and lose.
Putting it all together: By Lemmas 1 & 2, we know that our opponent beginning their turn in a balanced state will always result in us beginning our turn in an unbalanced state, and that we can always bring it back to balanced if we choose to.
Now, look at the condition for the critical turn to occur. It is by definition an unbalanced state! This means that by forcing our opponent to begin their turn in a balanced state, we can guarantee (using Lemma 3) that WE get the critical turn, which ensures our victory (Lemma 4).
If we check the board given to us, we can see that it is balanced. Since we want our opponent to begin their turn balanced, we place 0 balls into a new row. We can also see using this strategy that this is the only way to guarantee a win.