Solution
A Row of Coins and a Ruler
Show the problem again
Sixteen coins lie in a row, numbered 1 to 16 from left to right. Coins 3, 6, 10, 12 and 13 show heads; the rest show tails. A move chooses a block of consecutive coins whose rightmost coin shows heads, and flips every coin in the block (so the rightmost coin becomes tails, and a block of length 1 is allowed). A player who cannot move loses. How many different first moves (different blocks) leave the opponent in a losing position? Give an integer.
Worked solution
The answer is 3. The game is a sum of independent games, one per head, because flipping a coin an even number of times is the same as not touching it. A single head at position p can be moved to any set of heads strictly to its left, with the block's left end a ≤ p flipping coins a..p-1. Computing Grundy values gives g(p) = the largest power of 2 dividing p (the 'ruler function'): 1, 2, 1, 4, 1, 2, 1, 8, ... The heads at 3, 6, 10, 12, 13 have values 1, 2, 2, 4, 1 with XOR 4, so the first player wins. Flipping the block a..p toggles each of those coins, so it changes the nim-sum by g(a) ⊕ g(a+1) ⊕ ... ⊕ g(p). A winning move needs this block XOR to equal 4, with coin p a head. Using the values 1, 2, 1, 4, 1, 2, 1, 8, 1, 2, 1, 4, 1 for positions 1 to 13, the blocks ending at a head with XOR 4 are exactly: coin 12 alone (value 4); coins 11 to 13 (1 ⊕ 4 ⊕ 1 = 4); and coins 2 to 6 (2 ⊕ 1 ⊕ 4 ⊕ 1 ⊕ 2 = 4). No block ending at coin 3 or 10 works: the blocks ending at 3 have XOR 1, 3, 2, and those ending at 10 have XOR 2 or 3 (starting at 10 or 9) or contain position 8 with value 8 (all others, giving XOR at least 8). The other blocks ending at 6, 12 and 13 likewise give XORs different from 4. So there are exactly 3 winning moves, which a full search of the game tree (2^16 positions) confirms.
Source: Turning Turtles / the Ruler game from Berlekamp, Conway and Guy, Winning Ways. Statement written for AxiomIQ.