Solution
Counting the Winning Nim Moves
Show the problem again
Four piles of Nim contain 17, 26, 39 and 52 stones. Two players alternate; a move removes any positive number of stones from a single pile, and whoever takes the last stone wins (normal play). Two first moves are different if they act on different piles or remove different numbers of stones. How many first moves leave the opponent in a losing position? Give an integer.
Worked solution
The answer is 3. By Bouton's theorem a position is lost for the player to move exactly when the XOR (nim-sum) of the pile sizes is 0. Here 17 ⊕ 26 ⊕ 39 ⊕ 52 = 24, so the first player wins. A move on a pile of size a reaches nim-sum 0 only by changing a to a ⊕ 24, and this is legal only if a ⊕ 24 < a, i.e. if a has a 1 in the leading bit of 24 (the 16s place). The piles 17 (10001), 26 (11010) and 52 (110100) have a 1 in the 16s place; 39 (100111) does not. This gives the moves 17 → 9, 26 → 2 and 52 → 44. Pile 39 would have to grow to 63, which is not allowed. So there are exactly 3 winning moves.
Source: Bouton's analysis of Nim (1901). Statement written for AxiomIQ.