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.
No comments:
Post a Comment