# Coin Removal Variation

A variation on this problem, where coins can become neighbors.

There is a line of $$n$$ coins on the table, all showing either heads or tails. The object of the puzzle is to remove all the coins by a sequence of moves. On each move, one can remove any heads-up coin, after which its neighboring coin or coins, must be flipped. Coins are considered “neighbors” if they are next to each other; if the coin in between two coins is removed, those coins now become neighbors.

Determine which starting conditions are completable, and provide an algorithm for completing the game when possible.

[Warning: what follows is a bit intricate. I suspect it can be streamlined.]

To determine whether a configuration is solvable,

first place an extra two heads on each end. Then note for each head how many tails are to its left and compute the sum of (-1)^(# tails to the left) over all heads mod 3. (That is: +1 when the number of tails to the left is even, -1 when it's odd.) If the result is a multiple of 3 then the configuration is not solvable; otherwise, it is. There is just one (obvious) exception: if the configuration consists of a bunch of tails and no heads at all, it is not solvable even though (if the number of tails is even) the number you obtain is 4.

Proof:

First, let's see what happens to this "score" when we make a move. Suppose first of all that the head we remove is not at either end of the row. We replace p H q with p' q' (I trust the notation is obvious). Since p,q have both flipped and the coin we removed was H, the signs of the stuff to the right have not changed. There are four possibilities, and we might as well just check them all: T H T (-1) -> H H (2); T H H (-2) -> H T (1); H H T (2) -> T H (-1); H H H (3) -> T T (0). In all cases, the sum mod 3 is unaltered. What if the head we remove is at one end? At the left end we have [H H] H H -> [H H] T or [H H] H T -> [H H] H; writing s for the "tail score" we are replacing 4+s with 2-s or 3-s with 3+s, and while this can change the score mod 3 neither operation can change whether the score is a multiple of 3. And at the right end we have H H [H H] (4) -> T [H H] (-2) or T H [H H] (-3) -> H [H H] (3) and the score doesn't change mod 3. Oh, one more case: if our head is at both ends then the configuration is [H H] H [H H] which reduces to [H H] [H H]; and neither 5 nor 4 is a multiple of 3. So -- and I suspect there was a neater way to prove this -- no legal move makes a difference to whether the score is a multiple of 3.

Now

if we manage to empty the row, all that remain are the two "dummy" heads we added on each end, and H H H H has a score of 4, which is not a multiple of 3. This establishes that if the initial score is a multiple of 3, then we can't remove all the coins. So, a fortiori, if the initial score is a multiple of 3 or the initial position has tails but no heads, then we can't remove all the coins.

And

if the initial score is not a multiple of 3 and the initial position contains at least one head, then let us make whatever moves we like except that we will not allow ourselves to make a move that leaves no heads unless it also leaves no coins. Clearly if we can keep doing this then we will eventually have no coins -- so can we do it? Well, let us adopt the following rule: we will always find a block of heads and remove the coin at one end of the block, and we will pick the end that's furthest from the end of the row. (In the event of a tie, choose either.) If this move leaves no heads then the coin we removed must actually have been at an end of the row (else there would have been a T next to it, which would have become H); so (since we pick the further-from-the-end end of a block) in fact our whole row must have been a single block of H. And since removing one end of it left no heads, it must have had length <= 2. And since it didn't remove all the coins, it must have had length >= 2. So its length was exactly 2, so our augmented row was [H H] H H [H H], with a score of 6, which is a multiple of 3. This establishes (since if the score is ever a multiple of 3 then it's always a multiple of 3) that if we can't remove all the coins then either the initial score is a multiple of 3, or the initial position had no heads.

This completes the proof; and the last spoilered paragraph above happens to include an algorithm that does the job. (The bit in boldface.)

• Maybe I don't understand the scoring method. Wouldn't TT have a score of 4, but still not be solvable?
– Cain
Oct 24, 2018 at 14:59
• And TH has a score of 3 but is solvable?
– Cain
Oct 24, 2018 at 15:21
• Ah, yes, those do seem to be loopholes. Let me check exactly what has gone wrong in my analysis. The first looks fixable, the second worries me more. Oct 24, 2018 at 16:03
• Ah, no, TH doesn't have a score of 3, so that's a relief. The "extended version" is [H H] T H [H H] scoring +2-3 = -1. Oct 24, 2018 at 16:04
• First loophole fixed. Sorry about that. (Again, I think the second loophole is a non-loophole because TH has a score consistent with its solvability.) Oct 24, 2018 at 16:09

It seems that there are

only two infinite families of configurations which are impossible to solve:
$$1_n$$, a line consisting of $$n$$ tails
$$2_n$$, a line consisting of $$n$$ tails and one head at the start and end.

It's easy to see that

there's no 'move' available in $$1_n$$ and
both moves in $$2_n$$ will just lead to $$2_{n-1}$$ (or, if $$n=2$$, to $$1_n$$)

There are a few configurations

with 5 or less coins which are not solvable. As long as you avoid them, you should be fine. These configurations are:
(3) THT
(4) HHTT, TTHH
(5) THTTT, TTTHT
The forced move in (5) will lead to (4); one possible move in (4) leads to (3), the other to $$1_3$$; the forced move in (3) leads to $$1_2$$.
Any position with 6 coins, except for $$1_6$$ or $$2_6$$, has a move to avoid $$1_5$$, $$2_5$$ and (5).

• I think there might be more permutations or concatenations to those families though, if nothing else. Consider T...THT..THT...
– Cain
Oct 23, 2018 at 22:16
• Approximately 2/3 of all starting positions are solvable and 1/3 unsolvable. Here is another infinite family of unsolvable positions: any row of heads whose length is 2 mod 3 is unsolvable. Or any row of heads whose length is a multiple of 3, followed by one tail. Oct 24, 2018 at 17:57

No answers in 4 hours so I kick off with one simple starting position (or its mirror)

T T T T T T T T T H

T T T T T T T T H
T T T T T T T H
.....
T H
H

Then the last Head is taken.

• Interestingly, I believe HT...TH is unsolvable.
– Cain
Oct 23, 2018 at 20:23
• I originally intended to include that case as solvable, until I noticed the implication that only one coin may be removed on each move, although the problem states "any H coin". Oct 23, 2018 at 20:48

Any combination of T's with one H to start can be solved.
Case 1: H on an end is shown in @Weather Vane 's solution
Case 2: an H in the middle of Ts
TTTHTT
TTH HT
TTT H (Case 1)

If there are all H's and one T it can be solved.
Case 1: T on the end, even number of H's
HHHHT
HHT H
HHH
HT
H
Case2: T on the end of an odd number of H's
HHHHHT
THHHT
H THT
HHT
T H
H
Case 3: T in the middle of H's
HHTHHH
HHH TH
TH TH
THH
H T
H

Will be cleaning formatting up later.

• Hmm, both an even and odd number of Heads have solvable configurations, seems like this will not be as simple as the previous puzzle.
– Cain
Oct 23, 2018 at 20:14
• @Cain See my answer. Indeed it's not all that simple. Oct 24, 2018 at 0:44