A Row of Coins and a Ruler
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.
Related problems & prerequisites
Worth solving first
- Removing Powers of Two 8.0/10
- Nim Where You May Split a Pile 7.0/10
- Counting the Winning Nim Moves 7.0/10
Source: Turning Turtles / the Ruler game from Berlekamp, Conway and Guy, Winning Ways. Statement written for AxiomIQ.