Sprague–Grundy theorem / Game of nim / Bowlingpins hackerrank

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.

Leave a Comment

Your email address will not be published.

Scroll to Top