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

`X`

or`XX`

or however many`X`

based on the number of pins you start with. This position has`SG(X) = 0`

because it’s terminal.The game position

`I`

can have one pin knocked down, which would make it`X`

. So`X`

is a follower of`I`

, and`SG(I) = mex{SG(X)} = mex{0} = 1`

The game position

`II`

can have either one pin knocked down, making it`XI`

==`IX`

==`I`

, or two, making it`XX`

==`X`

. So it has these two followers, and`SG(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 are`XII`

(SG of 2),`XXI`

(SG of 1), and`IXI`

. 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”. For`IXI`

, it has two games of`I`

, 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.