Nim with 3, 4 and 5
Two players play Nim with three piles of 3, 4 and 5 counters. A move removes any positive number of counters from one pile, and the player who takes the last counter wins.
How many different first moves guarantee a win for the first player?
Fractions, decimals with at least 3 significant digits, and expressions such as sqrt(2)/2, e^-1 or pi/4.
Write the pile sizes in binary and add them without carrying (exclusive or): the nim-sum.
A position is lost for the player to move exactly when its nim-sum is 0. Which moves bring the nim-sum to 0?
h
s Shown after a correct answer. Revealing it first marks the problem as seen, not solved.
Idea. By Bouton's theorem, the player to move loses exactly when the nim-sum (the bitwise XOR of the pile sizes) is 0. A winning first move must produce a position with nim-sum 0.
Step 1: the nim-sum. In binary, , , , and It is not 0, so the first player can win.
Step 2: the winning moves. A move changes one pile from to , which is possible only if , that is if the binary digit of value 2 is 1 in . Only qualifies. So the only winning move is to take 2 counters from the pile of 3, leaving piles 1, 4, 5 with nim-sum .
Answer. Exactly 1 first move wins.
Why the rule works. From nim-sum 0 every move breaks the zero, and from a nonzero nim-sum some move restores it. The player who keeps restoring it takes the last counter.