Solution
Losing Nim Triples
Show the problem again
A game of Nim is played with three piles, each containing between 1 and 15 stones inclusive; there are 15³ = 3375 ordered starting triples (a, b, c). Players alternate removing any positive number of stones from one pile, and whoever takes the last stone wins. For how many ordered triples does the second player win with optimal play? Give an integer.
Worked solution
The answer is 210. By Bouton's theorem the second player wins exactly when a ⊕ b ⊕ c = 0, i.e. c = a ⊕ b. We need a, b, c all in 1..15. Choose a and b freely in 1..15; then c = a ⊕ b is automatically at most 15 (it fits in four bits), and it is non-zero exactly when a ≠ b. So there are 15 × 14 = 210 ordered triples.
Source: Bouton's theorem on Nim (1901). Statement written for AxiomIQ.