Counting Losing Coin Rows
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.
Related problems & prerequisites
Worth solving first
- Removing Powers of Two 8.0/10
- Losing Nim Triples 7.0/10
- Nim Where You May Split a Pile 7.0/10
Source: A coin-turning game in the style of Mock Turtles from Winning Ways. Statement written for AxiomIQ.