Let us consider a two player game, played with piles of coins. On your turn you choose a pile of coins and remove some nonzero number of coins from that pile. The players take turns doing this, and eventually piles run out of coins. If it is your turn and there are no coins left, you lose.
If you know some game theory, you will recognize this game as Nim and you might as well stop reading this post right now, since I'm not going to say anything you don't already know. Anyway, if you haven't seen this game, I encourage you to try it out, its a fun and simple game until you have seen the complete solution, you can probably find some programs online that will play with you (and beat you, because the solution is simple to program).
Before I go through the solution, I want to set up some notation. *x will denote a pile of x coins, and *x+*y will denote a game with two piles of coins with sizes x and y. {a,b,c} will denote a game where the legal move is for a player to move to any of positions a, b, or c, so we can say that *4={*0, *1, *2, *3}, and *2={*0, *1}, of course *0={ }. Lets begin by trying to solve a few simple cases of the game.
The one heap game is trivial, you simply remove all the coins in the heap with your first move and the game is over. The two heap game is fairly simple, suppose that we have a position like *7+*4, then we simply reduce the *7 by three coins to *4. With two heaps of the same number of coins, we simply have to mirror everything our opponent does to win, if he reduces one of the 4 heaps to x, we reduce the other 4 heap to x, eventually our opponent will remove a piles final coin, and we sweep the other pile away to win.
The larger games are harder, but we can solve a few cases right away. For example, if it is our turn from the position *8+*6+*6, we should simply remove the heap of size 8, and mirror our opponent in the two heap game. Or is we are in a position *9+*8+*6+*6, we can simply reduce 9 to 8 and play two mirror games. Actually, we can see that if ever we are in some position with *a+*b+*c+*x+*x, we can ignore the last two heaps, our opponent can find no winning move in those two heaps (we just respond in the other one) and we can find no winning move in those two heaps (our opponent will do the same to us). So, from an optimal strategy point of view, adding *x+*x to any game does not change anything. We can also see that adding *0 to any game does not change anything, so we can see that there is some sense in which
*x+*x=*0
Naturally, in the game with only *0, the active player loses, and in the game with only *x+*x, the active player loses.
Now we are in a position to analyze a slightly more complicated position, *2+*1. What are the legal moves from this position? We can reach any of *2+*0, *1+*1, or *0+*1, which are *2, *0, and *1, respectively, so we can see that *2+*1={*2, *0, *1}, which is *3
*2+*1=*3
Which means that in any game with *a+*b+*c+*2+*1, you can treat this as the same as *a+*b+*c+*3. In particular *3+*2+*1 is a losing position for the first player, as it is the same as *3+*3. It also means that a game like *a+*b+*c+*3+*2+*1 is just the same as the game *a+*b+*c+*3+*3, which we have seen is the same as the game *a+*b+*c.
*3+*2+*1=*0
Actually, one might try to derive this last equation from *2+*1=*3 by adding *3 to both sides and using *3+*3=*0. Sounds reasonable enough, and if it weren't valid then our choosing to use "+" to denote these games would be questionable indeed. Actually, this means that we should also be able to add *1 to *2+*1=*3 to arrive at *2=*3+*1, is this equation valid? Well, from the position *3+*1 we can reach any of *3+*0, *2+*1, *1+*1, *0+*1, so we can see that *3+*1={*3, *3, *0, *1}={*3, *0, *1}. But we know that *2={*0, *1}, so are these things really the same?
Suppose we have a winning strategy in the game G+*2 (where G is any collection of heaps, so G represents something like *a+*b+*c), I claim we can use that as a winning strategy in G+*3+*1. If your winning strategy ever tells you to move in G, then do so. If your winning strategy is to move in *2, it must be to *1 or *0, both of which are accessible in *3+*1, so you can follow your strategy. Our only concern is that our opponent makes use of the move from *3+*1 to *3, but we can immediately revert that to *2 (since *2 is a legal move from *3), and then we can actually continue to follow our strategy.
The conclusion of this is that if you have analyzed a game and found is looks like {*0, *1, *2, *5, *9} or so, you can treat this game as *3. It can access any game that *3 can, and if you opponent moves to one of the larger numbers you can immediately revert it to *3. 3 is said to be the Minimal EXcluded number from the set {0,1,2,5,9}, denoted 3=mex{0,1,2,5,9}.
{*a, *b, *c, ...} = *n, where
n=mex{a,b,c,...}
This gives us {*0, *1, *3}=*2 which validates the equation *3+*1=*2. We can confirm that *3+*2=*1 through a similar method.
This actually gives us a complete solution for the N-pile game, as long as the piles are not larger than size 3, any two piles *x and *y can be replaced by one pile, using one of *x+*x=*0, *1+*2=*3, *1+*3=*2, *2+*3=*1. In the end, there is one pile, and you simply must reduce it to zero, if the one pile is already *0, you are in a losing position and must hope for a mistake.
Next, what do we do if we are in a position with a pile of size 4? Well, lets see what *1+*4 gives us. We can move to any of *0+*4, *1+*3, *1+*2, *1+*1, *1+*0, which means *4+*1={*4, *2, *3, *0, *1}, which is clearly *5. We can find *1+*5 as well, we can move to any of*0+*5, *1+*4, *1+*3, *1+*2, *1+*1, *1+*0, which means *1+*5={*5, *5, *2, *3, *0, *1} which by the mex rule is the same as *4. The mex rule gives us our general answer, actually:
*a+*b=*c, where
*c is the smallest number not of the form *a'+*b or *a+*b'
for any a' less than a and b' less than b
This is enough for us to fill in an entire addition table for nim if we want (these numbers are often called nimbers, just to be whimsical). A partial nimber addition table is
0 1 2 3 4 5 6 7
1 0 3 2 5 4 7 6
2 3 0 1 6 7 4 5
3 2 1 0 7 6 5 4
4 5 6 7 0 1 2 3
5 4 7 6 1 0 3 2
6 7 4 5 2 3 0 1
7 6 5 4 3 2 1 0
If you extend this, you'll see it has some nice structure in terms of blocks of powers of two. Actually, you can find a general rule, which I will not prove here:
*2a+*2b=*(2a+2b)
unless a=b
So, nimber addition for different powers of two is the same as number addition. Of course if a=b then the nim sum is zero. One can also see from the nim addition table that nim addition is associative and commutative, meaning that the nimbers form an abelian group under nim addition with identity *0 and every element is its own inverse. We can use this to do some more complicated nim addition, for example *22+*7+*25 = (*16+*8)+(*4+*2+*1)+(*16+*8+*1) = *16+*16+*8+*8+*4+*2+*1+*1 = *0+*0+*6+*0 = *6. One can extend the nimbers to allow for a multiplication and make it a full blown field (sometimes called On2), but lets not bother with that.
One might find this addition easier to do in binary, in fact, some people describe nim addition as "convert to binary and add without carrying". This means that Patrick's addition rule from last time is actually just nim addition.
At this point is it fairly natural to solve the puzzle from last time. We can see that *a+*b+*c+...=*x+*y+*z+... if and only if *a+*b+*c+...+*x+*y+*z+...=*0, so we have an immediate check to see if Sean has any split that does not make his brother cry. If he has such a split, any split will work, so he simply gives his brother the smallest candy to keep the most for himself.
Alright, so any time you are in a situation in nim, simply check the nim sum, if it is not zero then there is some move that will make it zero. If it is already zero then you have lost and must either resign or hope for a mistake.
Nim is actually very important in game theory because any two player, perfect information, finite, impartial game with the normal ending condition can be reduced to nim. To clarify those technical terms, finite means that there is no infinite sequence of legal moves anywhere in the game, the normal ending condition is that if you have no legal moves you lose. Finally impartial means that in any position of the game, both players have the same set of legal moves available to them (contrast to something like chess where one player plays white and the other black, chess is not impartial).
As an example of another impartial game, consider the game of Cram. This game is played on a chessboard and on a players turn they place a 2x1 domino on the board to cover two squares. If it is your turn and you have no room to place a domino, you lose. One can reduce this game to nim by considering what moves are available from any given position. For example, if there is only a 1x1 square, this is the same as *0 (no legal moves). A 2x1 or 3x1 box has exactly one move, to *0, so those positions are *1. A 4x1 box or an L-shape can move either to *0 or to *1, so it is *2. You can just sort of explore the entire game like this if you feel like it.
Anyway, I think thats all I got for this. I really find the entire theory fascinating for some bizzare reason, and that puzzle reminded me that I wanted to make a post working out the solution. If you find this sort of game theory interesting, I recommend you look up the series of books by Gardener, Winning Ways For Your Mathematical Plays.
