Question

Alice and Bob are have several piles of chips. On each turn they can either remove 1 or 2 chips from one pile, or split a pile into two nonempty piles. Players take turns and a player that cannot make a move loses. Find the value of the Sprague–Grundy function for positions with one pile made of n chips. (Please do not forget to prove correctness of your asnwer.)

Answer 1

Nim is a combinatorial game, where two players alternately take turns in taking objects from several heaps. The only rule is that each player must take at least one object on their turn, but they may take more than one object in a single turn, as long as they all come from the same heap.

Nim is the most well-known example of an impartial game, a game where both players have the same moves all the time, and thus the only distinguishing feature is that one player goes first. It is also completely solved, in the sense that the exact strategy has been found for any starting configuration.

Rules

The basic Nim begins with two players and several heaps, each containing several objects. Occasionally, heaps are also called piles, and the objects are called stones.

Each player, in turn, must take at least one stone, but they may take more than one stone as long as they all come from the same pile. It's allowed to make a pile empty, effectively removing the pile out of the game. When a player is unable to move, the game ends. Naturally, as long as there is a stone, either player can take that stone, and thus can move. So the ending condition can be rephrased, where the game ends if there is no stone left.

In normal Nim, the loser is the player unable to move. It is called normal condition by convention from combinatorial game theory, where a normal game gives the win to the last player making a move. In misère Nim, the player unable to move wins instead; this is equivalent to the player taking the last stone losing.

Example Game

Consider the following example of the game. There are three piles, initially having 3, 4, 53,4,5 stones respectively. Alice and Bob are playing, with Alice starting.

In normal play, Alice wins, as Alice has taken the last stone and thus leaving Bob with no move. In misère play, Alice would lose instead, but in this case Alice would have taken 2 stones from Pile 3 on move 7, leaving Bob with pile sizes 0, 1, 0 and thus forcing Bob to take the last object.

In the above game, Alice has played a perfect game, never letting Bob to be able to snatch the win. This can be generalized into a general strategy.

Strategy

• f the suggested move makes the pile have 1 stone left, make it have 0 stones instead, or
• If the suggested move makes the pile have 0 stones left, make it have 1 stone instead.

In other words, the correct move is to leave an odd number of piles of size 1. (In normal play, there should be an even number of piles of size 1 instead, to make the nim-sum zero.)

Proof of Winning Strategy

The following proof is for normal Nim's strategy, given by C. Bouton.

theorem:

The moving player wins in normal Nim if and only if the nim-sum of the pile sizes is not zero.