Came across Problem D in Codeforces Round #102, solution of which is equivalent to Nim, a game on mathematical analysis of which I have little, if any, previous knowledge. Did some reading on Nim and I wanted to write a couple of proofs and explanations I deduced as a blog post in case I need to return to them later on. Also, the link to the proofs given in contest's editorial was broken, which made it sort of a necessity for me to work on the proofs.
I intended the title of this post to be Proof of a Determining the Winner for a Generalized Version of Nim. However the long titles screw up the styling of my current blog theme and I got tired of trying to find a semantic equivalent to it. Keep in mind, however, Nim can be modified/generalized in a variety of ways, and this blog post will only cover the proof of generalizing it by removing the constraint of taking pieces from a single pile. (i.e. players will be able to pick up pieces from multiple piles) For other modifications of Nim the Wikipedia article, which covers a few, may be a good starting point.
Introduction to Nim
I don't want to repeat the definitions given on Wikipedia or other sources, so I suggest you go look at them yourselves. However, just for the lazy ones among you, the gist of the game, as defined in Bouton's original paper on Nim's analysis is two players taking turns in picking up any number of objects from one of the 3 piles of objects provided to them. Depending on the game mode, either the player who picks up the last object wins(i.e. normal mode) or she loses(i.e. misere mode, as put in such a posh way on Wikipedia).
Bouton's paper analyzes and proves that for any given state of this game, a mathematical approach could be applied to find the winner. Nim is a very interesting game that can be modified in various ways. A generalization, which is also featured in Bouton's paper is to increase the number of piles instead of having just 3.
Another generalization, which I am to cover in this post, is to let players pick elements from multiple piles. Obviously a player may not pick from all piles at once, as the first player may win by picking all elements from all piles as her first move. But we may still make a generalization that a player may pick elements from up to K piles such that K is less than the total number of piles.
Though I do not want to repeat the stuff I read, I do feel the need to paraphrase the proof for picking-from-a-single-pile case both as practice, and as an introduction to the next step of this post. Proof provided in Wikipedia article makes heavy use of XOR operator. It is good to understand the case of picking elements from a single pile, but it feels a little off when trying to prove the case for more generalized versions of the game. Bouton's paper has the same approach, but instead of relying on a practical operator such as XOR, the paper covers the same proof with a more theoretical narrative, making it easier to get a grasp of the proof I will give below.
Proof for Single Pile
Bouton's paper defines a safe game state that any player should try to reach with her move. The point is, when the game reaches that desired state after a player's turn, the other player will certainly lose, regardless of any move she may make.
Bouton's proof proceeds in two steps. First is proving that, when player A leaves the game at a safe state, Player B can not end up with another safe state. The second step is proving that when a Player A leaves the game at a safe state and Player B obtains an unsafe state, Player A can always bring the game back to another safe state. Note that the proofs in this post assume that the game is played in the normal mode(i.e. whoever makes the last move wins), not in that sophisticated-sounding misere mode. You may, however, modify the proof to work for that mode.
The safe state defined for a single pile case is as follows. If sum of the i-th digits of the binary representations of the amount of elements in each pile is divisible by 2, for all i values, then the game state is said to be safe. The desired state is deduced from the actual end of the game. (i.e. no piles having any elements for any player to pick up)
We need to prove that if Player A has left the game in a safe state, the game state may not be safe after a single move by player B.
If Player B can not move, she loses the game. If she can, she has to pick up a positive amount of objects from a pile.
The idea is that Player B will change the digits of a binary representation of a single number. (i.e. number of elements in a single pile) In other words, the move Player B makes will cause at least 1 binary digit, di, to turn from 0 to 1, or vice versa. The game state after that move is calculated by summing the values of binary digits i of number of elements in each pile and checking if it is divisible by 2. We know that it was divisible by 2 after Player A made her last move, as we assumed that she left the game in a safe state. But, the move by Player B changes at least a single binary digit (i.e. di) causing the sum of ith digits to have an odd number of 1s, and making the value not divisible by 2, consequently yielding an unsafe game state.
The important thing here is not how many digits Player B's move may effect, but the fact that each digit i has an even sum, and since Player B can only change the number of elements in a single pile, it can never change the even sum of a binary digit i to another even sum. It can only increase or decrease it by 1.
Assume a move by Player A got the game to a safe state, and a following move by Player B, as proven above, got it back to an unsafe state. We need to prove that there exists a move Player A can make and get the game back to a safe state.
First off, we know that player A can move as there is at least 1 pile with positive amount of elements. (i.e. the game state is unsafe, unlike 0 elements in all piles, which is a safe state)
In the previous step of the proof we mentioned that Player B caused K many digits to have a odd sum. For Player A to obtain a safe state, she needs to get those digits back to having an even sum. I believe it should be intuitive that Player A is able to get a safe state by modifying the number of elements in a single pile in such a way that the new number of elements is different from the old one only in the binary digits that were previously modified and deemed unsafe by Player B in her last move.
Note that Player A can only reduce the number of elements in a pile. As she can not add any elements to a pile, she can not turn the 0s on the left of the leftmost 1 of the binary representation of a number into 1. Therefore, we need to pick the correct pile so that Player A can correct all the binary digits modified by Player B, with a single move.
The pile to reduce is, not surprisingly, the one having a 1 in the leftmost binary digit deemed unsafe by Player B, say dleft, as its value is obviously high enough to be able to reduce to a value that corrects all other modified digits. As the sum of values in that binary digit of all piles is odd, we know that there exists at least one such pile that Player A can choose to modify.
This concludes the proof for picking elements from a single stack case.
It may still be a little vague how this safe state preservation technique will lead to Player A winning the game. Try to see the fact that, as the game progresses and the amounts of elements in various piles are decreasing, the binary digit dleft will shift towards right, until at some point it reaches to the rightmost digit with 1. Then, at the last unsafe state, Player A will end the game by just removing all of that last pile with a value 1 at dleft. (i.e. drightmost)
The proof given above shows that a safe state preservation approach helps determine whether a player will win or lose the game. If at a player's turn the game state is not safe, that player may ensure a win by playing optimally. (i.e. otaining a safe state, and preserving it) If, however, the game state is safe at that player's turn, then the proof states that there exists an optimal counter move for any move made by that player, leading to the player's inevitable loss.
Proof for Multiple Piles
The next step is to prove that a safe state preservation approach may still work if players are able to pick up elements from K-many piles, given K is less than the total number of piles. This time, the safe state is defined as sum of the i-th digits of the binary representations of the amount of elements in each pile being divisible by (K+1), for all values of i. The proof for this case can also be viewed in two steps, similar to the single pile case.
We should prove the same statement in Step 1 of the previous proof. (i.e. case of picking from a single pile) The idea behind the proof is the same as well.
After a move by Player A that got the game to a safe state, Player B may change the digits of binary representations of at most K piles. Yet, in order to make any binary digit i that Player B's move may modify, she needs to modify i-th binary digit of at least (K+1) different piles so that she gets a sum in of all i-th digit elements still divisible by (K+1). For any number of piles she may choose to modify, it is not possible to maintain a sum for the modified binary digits that is divisible by (K+1), as the sum was divisible by (K+1) to begin with and she can not modify more than K piles. Of course, we assume that Player B changes at least one such digit di in at least one pile, which is same as assuming that Player B can move at all. This assumption is not irrational. After all any move changes at least a single binary digit, and unless she can move, she loses the game. Therefore, as long as she can move, she has to move, and changes at least a single binary digit.
Similar to the case for a single pile, any digit di in at most K piles that Player B modifies with her move, she can change the sum of all i-th digit values by at most K. Obviously, that amount of change in the sum can not yield a value divisible by (K+1) from a value that was divisible by (K+1) to begin with.
As in Step 2 of single pile case, we assume a move by Player A got the game to a safe state, and a following move by Player B, as proven above, got it back to an unsafe one. We are to show that Player A can get it back to a safe state, regardless of which unsafe state the game is currently at.
The game state is unsafe, thus Player A can make a move. With that move, Player A should get the unsafe digits back to having a sum divisible by (K+1). Before the move by Player A, let's say there are T digits that Player B has modified to an unsafe state. We know that the sum of their values have a remainder in the range [1, K] when divided by (K+1). Player A, by her move, can pick at most K piles and increase and decrease the values of their binary digits accordingly so that the sum of all unsafe digits are safe again.
How Player A can pick those piles to modify is a little trickier than the single pile case, but it is still possible to understand. She will find the largest remainder among the sums, say Q, which will show her the amount of piles she needs to modify. It should be intuitive why it is sufficient to modify Q piles. Then she can look for piles which have an amount of elements with value 1 in their L-th binary digit. (i.e. leftmost unsafe digit) If there are more than Q piles with a value 1 on their L-th binary digit, then she can pick any Q of them and reduce them appropriately to make all sums of digits safe again. If there are less than Q piles with value 1 on their L-th digit, she needs to look for the second leftmost unsafe digit. This procedure should progress till she finds Q piles to reduce.
There is no case where Player A may fail to find Q piles to modify. This fact can be proven easily by the fact that at some digit i, the sum gives the remainder Q when divided by (K+1). So, on the worst case, when we reach that digit, we will be able to pick Q piles to reduce.
The proof for picking elements from multiple stacks can be concluded here, I believe.
Checking divisibility by (K+1) when removing from K piles is allowed sounds quite harmonious. Yet it was not that easy to comprehend, even after reading the proof for the simpler case given on Wikipedia article. The proof I presented above is quite textual and seems to not depend on algebra or other concrete, step-by-step methods as most proofs do. For most, including me, such a textual proof may be hard to understand. Still, I chose to narrate the proof almost purely theoretically instead of going over it with an sample case, as I believe this approach gives more a perspective over the ideas governing the proof. If you are having a hard time to understand, though, then I suggest you generate a few example games and walk over the optimal strategy told here to understand the points made in the proofs given above.
I do not currently have the time to do so, but anoyone interested in working further on the theory of this game may, as an exercise, try to modify the narrative above to prove that the winner can be determined in misere mode as well. You may also enjoy learning more about impartial games in general.
I hope anyone reading this post finds it as useful as I found the time I spent trying to understand and prove the theorems above.