Putnam 1995, Problem B-5

A game starts with four heaps of beans, containing 3,4,5 and 6 beans. The two players move alternately. A move consists of taking either
a) one bean from a heap, provided at least two beans are left behind in that heap, or
b) a complete heap of two or three beans.

The player who takes the last heap wins. To win the game, do you want to move first or second? Give a winning strategy.

Solution:
This problem is dumb if you know the Sprague-Grundy theory of normal impartial games (see Conway, Berlekamp and Guy, *Winning Ways*, for details). I'll describe how it applies here. To each position you assign a *nim-value* as follows. A position with no moves (in which case the person to move has just lost) takes value 0. Any other position is assigned the smallest number not assigned to a valid move from that position.  
For a single pile, one sees that an empty pile has value 0, a pile of 2 has value 1, a pile of 3 has value 2, a pile of 4 has value 0, a pile of 5 has value 1, and a pile of 6 has value 0.  
You add piles just like in standard Nim: the nim-value of the composite of two games (where at every turn you pick a game and make a move there) is the "base 2 addition without carries" (i.e. exclusive OR) of the nim-values of the constituents. So our starting position, with piles of 3, 4, 5, 6, has nim-value \( 2 \oplus 0 \oplus 1 \oplus 0 = 3 \).  
A position is a win for the player to move if and only if it has a nonzero value, in which case the winning strategy is to always move to a 0 position. (This is always possible from a nonzero position and never from a zero position, which is precisely the condition that defines the set of winning positions.) In this case, the winning move is to reduce the pile of 3 down to 2, and you can easily describe the entire strategy if you so desire.