Coin removal problem

Question

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 1

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.

Answer 2

It looks like a line is solvable if and only if

there is an odd number of heads in the line

and the strategy to solve the puzzle is to make sure

that whenever you take away a head, the remaining sub-lines each have an odd number of heads.

I'm on mobile right now and can't type a rigorous mathematical proof; moreover, two other users seem to be doing this so I'm going to spend that time upvoting their answers instead :)

Answer 3

Let $h$ be the number of heads-up coins. If $h=0$,

We have no starting moves so no solution available.

If $h=1$,

The solution is trivial. Flip the one heads-up coin, after which we have on both sides either a smaller line with $h=1$, or no line at all if the heads-up coin was at either end to start with.

If $h=2$,

There is no solution. There is no move which would bring the number of coins in the current continuous line from 2 to 1. If the heads-up coins are next to each other, flipping either one will leave a tails-up coin with no heads-up coins left. And if there is a gap, flipping either one will create a smaller continuous line with $h=2$ and a gap which is one smaller. Eventually you get to a position where the heads-up coins are next to each other.

If $h=3$,

This is always solvable. If the three heads-up coins are next to each other, we can remove the left-most one, leaving the current line with $h=1$. On the left-hand side of the created gap we either have nothing (if the flipped coin was on the edge) or a separate line with $h=1$, so both sides are solvable.

...TTTTHHHTTTT...

Flip the left-most one
...TTTH THTTTT... (both parts are solvable with $h=1$)

For any odd $h$,

We can always "move" the left-most heads-up coin right with the aforementioned process until we have two heads-up coins next to each other on the left side. When we flip those, we're left with $h_{new}=h-2$, eventually reaching 1.

For any even $h$,

I think these are always unsolvable.

Let's say $h$ is even and take a look at an arbitrary heads-up coin H. If we look at the sub-lines on the right and left side of H. Since $h$is even, one of the sub-lines has to have an even number of heads-up coins and one of them an odd number. When we flip H, one of the coins in the odd sub-line is flipped, resulting in a sub-line with an even number of heads-up coins. This can be zero, but in this case there is always at least one tails-up coin remaining (the one we flipped on our last move). So there is no way to make both sub-lines solvable after the flip.