The coin removal puzzle is a puzzle with 
coins arranged at consecutive
fixed positions in a row, each showing either heads or tails. A move removes a heads-up
coin and flips each coin still
present at either immediately adjacent original position. Gaps remain after removals,
so coins separated by a gap do not become neighbors. The
goal is to remove all the coins. The same puzzle
can be played with face-up and face-down cards (Numberphile
2019).
An initial row can be cleared iff it contains an odd number of heads-up coins (Shelton and Siler 2004). A proof uses strong induction on the row length. A single coin can be removed exactly when it shows heads, and a row with no heads-up coins has no legal move.
Suppose a row has a positive even number of heads-up coins. Removing any heads-up coin leaves two portions that together contain an odd number of heads before the neighboring coins are flipped. At least one nonempty portion therefore has an odd number of heads. Flipping its end coin changes that count to an even number. This shorter portion cannot be cleared by the induction hypothesis, and the gap prevents moves in the other portion from affecting it.
Conversely, suppose the row contains an odd number of heads. Remove the leftmost heads-up coin. If the left portion is nonempty, it now has exactly one heads-up coin. If the right portion is nonempty, its initially even head count becomes odd after its end coin is flipped. Each nonempty portion is shorter and can be cleared by the induction hypothesis. Empty portions require no moves, completing the proof.
