Solution
Removing Powers of Two
Show the problem again
Three heaps contain 14, 20 and 29 stones. Two players alternate; a move picks one heap and removes exactly 2^j stones from it for some j ≥ 0 (1, 2, 4, 8, ...), as long as the heap holds at least that many. A player who cannot move loses. Two moves are different if they use different heaps or remove different amounts. How many first moves leave the opponent in a losing position? Give an integer.
Worked solution
The answer is 6. For a single heap the Grundy value is n mod 3. Induction: a heap of 1 can only move to 0, so g(1) = 1. For n ≥ 2 the moves remove 1 or 2 (and others), so the heap can reach n-1 and n-2, which have the two residues different from n mod 3 (by induction their values are exactly those residues). No power of 2 is divisible by 3, so no move reaches a heap of the same residue as n. Hence the set of reachable values is exactly the two values other than n mod 3, and its mex is n mod 3. The heaps 14, 20, 29 are all ≡ 2 (mod 3), so the Grundy sum is 2 ⊕ 2 ⊕ 2 = 2, a first-player win. A winning move takes one heap to residue 0, i.e. removes an amount ≡ 2 (mod 3), which means 2^j with j odd: 2, 8, 32, .... Each heap allows 2 and 8 (32 is too big), so 2 moves per heap and 3 × 2 = 6 in total. A direct search of the game agrees.
Source: Original problem written for AxiomIQ.