Solution
Counting Losing Coin Rows
Show the problem again
Sixteen coins lie in a row, each showing heads or tails (so there are 2^16 = 65536 arrangements). A move chooses a block of 1, 2 or 3 consecutive coins whose rightmost coin shows heads, and flips every coin in the block. (A block cannot extend past the left end of the row.) The player who cannot move loses. For how many of the 65536 arrangements does the second player win with optimal play? Include the all-tails arrangement. Give an integer.
Worked solution
The answer is 16384. The game splits into independent single-head games: a head at position p can move to any set of heads to its left that is obtained by flipping up to two coins immediately before p. Computing Grundy values by hand: g(1) = 1 (only move removes the head), g(2) = mex{0, 1} = 2, g(3) = mex{0, g(2), g(2) ⊕ g(1)} = mex{0, 2, 3} = 1, g(4) = mex{0, g(3), g(3) ⊕ g(2)} = mex{0, 1, 3} = 2, and the values keep alternating: 1 for odd positions, 2 for even positions. An arrangement is losing for the mover exactly when the XOR of its heads' values is 0, i.e. when it has an even number of heads on odd positions and an even number of heads on even positions. Each parity condition holds for half of the 2^8 patterns on the corresponding 8 coins, so the count is 2^7 × 2^7 = 16384. Brute force over all 65536 positions confirms it.
Source: A coin-turning game in the style of Mock Turtles from Winning Ways. Statement written for AxiomIQ.