contest math - Solution to a coin puzzle

Setup: You have $n$ coins placed in a row. Initially, all coins are heads. There is one allowable action: you can remove a coin that is not at one of the ends of a row, and flip its neighbors. The removed coin must be heads.

Example: HTHTH becomes HHHH if you remove the middle coin.

Problem: For which $n$ can you reach a state with only two coins remaining?

My attempt: Given any 5 heads in a row, we can always remove them in a manner such that we'll end up with 2 heads in a row, without removing any of the ends. Removing the 2nd coin, the 3rd coin, and then the 2nd coin:

HHHHH -> TTHH -> THT -> HH

and we can easily see inductively for $n \equiv 0, 2 \mod 3$ that there's a solution.

It seems like there isn't a solution for $n \equiv 1 \mod 3$ but I'm having a hard time showing this.

Answer

We show that we can reach a state with only two coins remaining if and only if $n - 1$ is not divisible by $3$.

If: Easy induction. Just note how $$\text{HHHHH} \to \text{TTHH} \to \text{THT} \to \text{HH}$$ and apply repeatedly, with a final $$\text{HHH} \to \text{TT}$$ if needed.

Only if: We will note two semi-invariants that prove this impossible. Both are easy to verify by checking all four possible transformations.

$\text{}$1. The number of tails is always even. Therefore, if we want to end with two coins they must be the same color.

$\text{}$2. Count each heads $+1$ if it appears to the right of an even number of tails and $-1$ if it appears to the right of an odd number of tails. Then the total of these $+1$'s and $-1$'s is constant mod $3$.

For example, $$\text{HHHHTHHTHTTH} = 4 - 2 + 1 - 0 + 1 = 4.$$ If $n - 1$ is divisible by $3$, then invariant 2 above is also congruent to $1$ mod $3$. But $\text{HH}$ is $2$ mod $3$ and $\text{TT}$ is $0$ mod $3$ so it's impossible.