Solution
Three Heaps, Three Subtractions
Show the problem again
Three heaps contain 38, 53 and 71 stones. Two players alternate; a move picks one heap and removes exactly 2, 5 or 6 stones from it (a heap with fewer stones than the amount cannot be used for that amount). A player who cannot move loses. Two moves are different if they use different heaps or different amounts. How many first moves put the opponent in a losing position? Give an integer.
Worked solution
The answer is 3. Compute the Grundy values of a single heap for the subtraction set {2, 5, 6}: g(0), g(1), ... = 0, 0, 1, 1, 0, 2, 1, 3, 0, 2, 1, and then g(11) = 0, g(12) = 0, g(13) = 1, ... the sequence repeats with period 11. Since 38 ≡ 5, 53 ≡ 9 and 71 ≡ 5 (mod 11), each heap has Grundy value 2, so the sum has Grundy value 2 ⊕ 2 ⊕ 2 = 2 and the first player wins. A winning move must bring one heap to Grundy value 0 (the other two heaps then cancel, 2 ⊕ 2 = 0). From 38, 53, 71, removing 5 gives 33, 48, 66, residues 0, 4, 0 (mod 11), all of Grundy value 0. Removing 2 or 6 never reaches value 0: the six such moves land on 36, 32, 51, 47, 69, 65, with residues 3, 10, 7, 3, 3, 10 and values 1, 1, 3, 1, 1, 1. So each heap has exactly one winning move (remove 5), for 3 in total, as a direct game-tree search confirms.
Source: Sprague-Grundy theory applied to a subtraction game; written for AxiomIQ.