6
$\begingroup$

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.

|cite|improve this question
$\endgroup$
  • 3
    $\begingroup$ There is something missing otherwise we could remove all but two coins and be done. Can we only remove coins that are heads? Is the final state fixed to HH? $\endgroup$ – Kitter Catter Dec 22 '16 at 19:55
  • $\begingroup$ Removed coins must be heads. Added this in! $\endgroup$ – Nitin Dec 22 '16 at 20:05
  • $\begingroup$ Could you show how to get to the final state from 6 starting coins? I don't think your statement of $n \equiv 0 \pmod 3$ having a valid solution is true. $\endgroup$ – gowrath Dec 22 '16 at 21:42
  • 1
    $\begingroup$ @gowrath: it is not required that the remaining two coins be heads, so if you start with three heads you just remove the middle one to get to two tails. You can use the five heads to two heads to get down to three from any $0 \bmod 3$ $\endgroup$ – Ross Millikan Dec 22 '16 at 22:24
  • 1
    $\begingroup$ This is an equivalent problem to having $n - 2$ coins placed in a row, the ability to take any coin and flip its neighbors, and determining the values of $n$ for which you can remove all coins. $\endgroup$ – Peter Kagey Dec 23 '16 at 6:22
2
$\begingroup$

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.

|cite|improve this answer
$\endgroup$
  • 1
    $\begingroup$ Would you be able to explain the intuition that led to the second invariant? $\endgroup$ – Nitin Dec 24 '16 at 13:46
  • 2
    $\begingroup$ @Nitin I did not come up with that semi-invariant using "intuition". I came up with it after listing a lot of small cases that I wanted to prove "not equivalent" in some sense and tried to describe the pattern simply. $\endgroup$ – Glen Weyl Jan 5 '17 at 16:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.