OK. Here's a proof:
I'll split into two cases:
The "bad" case: the game consists of a single segment of adjacent coins, all T
. This case can be solved by turning the first coin to H
, and then taking it; the result can then be solved by case 2
The "really good" case, where the game consists of a sequence of coins containing an odd number of H
s. (Details on solving this in a moment)
The "sort of bad" case: the game consists of a sequence of adjacent coins, with a nonzero even number of T
s. (The cases of, say, TT
or TTTT
are worth considering as examples). As in case 1, we can flip any coin, producing an odd number of T
s. To make this explicit: pick the first T
and flip it, thus reducing the number of T
s and leaving an odd number of T
s. (With this simplification, we can see that this is really handled exactly the same as case 1, so we can lump them together into "the bad cases". What makes them "bad" (from my point of view) is that they're solvable only if you can use the 'first-move-only' move where you flip just one coin. We'll see why that's a problem in a moment.
At this point, it's worth simply solving all 1- and 2-coin problems:
Solution Table
H
-- take coin 1 (T1)
T
-- flip coin one; take coin 1 (F1T1)
HH
-- F1T2T1
HT
-- T1T2
TH
-- T2T1
TT
-- F1T1T2
Now let me look at case 2 (but only for 3 coins or more, because I've solved all the 1- and 2-coin problems) and split it into a few cases:
2a. The sequence starts HTxxx
where the x
s indicate any number (possibly zero!) of either H or T.
2b. The sequence starts THTxxx
2c. The sequence starts THHxxx
2d. The sequence starts TTxxx
(where at least one of the remaining coins must be an H
because we're in case 2, where there's an odd number of H
s).
In the first three cases, I'm going to show how to reduce the problem to a smaller problem that is in case 2; we can then (once I handle the fourth case) repeat and repeat until we're down to one or two coins, and then apply the solutions in the solution table to finish off. SO here goes:
2a. HTxxx
: T1 to produce -Hxxx
, a shorter sequence with exactly the same (odd) number of heads! (the dash indicates an empty space)
2b. THTxxx
: T2 to produce H-Hxxx
, a pair of sequences; the left one is solvable by the solution table; the right one is shorter, but has the same (odd) number of heads we had before the "T2".
2c. THHxxx
: T2 to produce H-Txxx
. Again the left sequence is easy, and the right sequence is shorter, but contains two fewer H
s than the original sequence, i.e., an odd number of H
s, so we're still in case 2.
The remaining case is case 2d: we start with a sequence of the form T...THxxx
, where the dots indicate an arbitrarily long sequence of T
s. There are two subcases: T...THTxxx
and T...THHxxx
. The savvy reader will observe that these are simply a sequence of T
s followed by cases 2b or 2c. We apply exactly the same solution: flip the first H
. The sequence splits into T....H-Hxxx
, or T...H-Txxx
In each case, the left hand sequence has exactly one H
, so we're in the "good" case. The right-hand sequence is shorter than the original, but has either (i) the same (odd) number of H
s as before the split, or (ii) two fewer (hence again an odd number of) H
s as before the split.
So in each case-2 situation, we've reduced the problem to one or two smaller case-2 situations, which we can solve independently. We're done.