mathematics - Coin removal problem

I have a slight variation of the coin flipping problem.

There is a line of $n$ coins on the table; some of them are heads up and the rest are tails up, in no particular order. The object of the puzzle is to remove all the coins by a sequence of moves. On each move, one can remove any head-up coin, after which its neighboring coin or coins, if any, must be turned over. Coins are considered “neighbors” if they are next to each other in the original line; if there is a gap between coins after some moves, the coins are no longer considered neighbors.

Determine the property of the starting line that is necessary and sufficient for the puzzle to have a solution. For those lines that can be removed by the puzzle’s rules, design a method for doing so.

Answer

The row of coins can be fully removed if it has the following property:

It has an odd number of heads

Proof:

By induction.
The property obviously correctly predicts solvability for a row of length 1, where "H" is solvable and "T" is not.
Suppose the property correctly predicts solvability for the row lengths $1$ to $n$.

Case 1: A row of $n+1$ coins with an odd number of heads.
Do a move on the last heads coin, which is at location $m$. This leaves a row of coins to the left of length $m-1$, and a row to the right of length $n-m+1$. If the row to the right is non-empty, it will have one head (at location $m+1$ that you flipped) and the rest tails, so it is solvable by the induction hypothesis. The row to the left will also have an odd number of coins because before the flip it had en even number, so that is also solvable by the induction hypothesis. Therefore the original row of $n+1$ coins is solvable (and a good next move is the last heads of the row).

Case 2: A row of $n+1$ coins with an even number of heads.
Do a move on any heads coin, at location $m$. This leaves a row of coins to the left of length $m-1$, and a row to the right of length $n-m+1$. If either of the two rows is empty ($m=1$ or $m=n+1$), then we have a single row of $n$ coins that still has an even number of heads (one removed, and and coin flipped), so it is unsolvable by the induction hypothesis.
If you really do have two rows now, then one of the rows will have an even number, the other will have an odd number of heads. You can think of the move as flipping three coins in a row (the middle of which was heads) and then removing the middle tails coin to split the row. Flipping the three coins changes the parity of the number of heads to odd, and splitting the row then means that exactly one of the resulting rows must be odd and one even. By the induction hypothesis, one of these rows is not solvable.
The coins become unsolvable whichever move you make, so the original row was unsolvable.

By induction, the property correctly predicts solvability for all values of $n$.

Solving strategy:

The proof shows that you can solve a row by always making your move on the last (or first) heads coin of the row.
Note that making a move in the middle somewhere can sometimes lead to a dead end, where it splits the row into two that are both unsolvable (both have an even number of heads). The simplest example is of course a row of three heads (HHH) which would turn into two separate tails coins if your move was the middle one.