I think this document has a really good explanation of the relevant theory: https://web.mit.edu/sp.268/www/nim.pdf. Personally, it took me a bit to get through the document; at first I just tried reading, but I got much more out of it by writing some of the lemmas/theorems down and practicing a bit myself. I think the graphs under “From Games to Graphs” and “The Sprague-Grundy Function” sections were particularly helpful for this problem.
Here’s how I started thinking about it: a set of pins is a game position. Each game position is either terminal or has followers, which are other game positions that can be moved to. Each game position can be assigned a Sprague-Grundy (SG) based on the SG values of its followers. Now try creating a graph of game positions:
The only terminal position is no pins left, which we can write as
XorXXor however manyXbased on the number of pins you start with. This position hasSG(X) = 0because it’s terminal.The game position
Ican have one pin knocked down, which would make itX. SoXis a follower ofI, andSG(I) = mex{SG(X)} = mex{0} = 1The game position
IIcan have either one pin knocked down, making itXI==IX==I, or two, making itXX==X. So it has these two followers, andSG(II) = mex{SG(I), SG(X)} = mex{0, 1} = 2.Now let’s look at
III, since this is where we get to start using some of the other information from the document. The followers areXII(SG of 2),XXI(SG of 1), andIXI. For this last one, we could see that it only has one follower and get the SG like that, OR we could use the Sprague-Grundy theorem. This says “the SG function for a sum of games on a graph is just the Nim sum of the SG functions of its components”. ForIXI, it has two games ofI, each with SG of 1. When we take the nim sum (xor the binary representations), we get 0. So in conclusion,SG(III) = mex{2, 1, 0} = 3.
And you can keep going bottom to top to get other SGs by taking 1 or 2 II away at a time and calculating nim sums.
CLICK HERE to find out more related problems solutions.