Simple proof for take-and-flip-over game solution

Question

I happened upon a puzzle (https://www.etsy.com/listing/98226237, image), and fairly quickly figured out how to solve it. However, then I tried to explain to a bright 9-year old why that solution works. And though I kind of succeeded, it was really hard to make the explanation ("proof") simple and understandable.

So my question is: What is the simplest explanation that we can come up with?

Here is the game (in my own words). Given is a row of 9 slots, each one having a coin showing heads or tails. The following moves are allowed:

• Optionally, only as the first move, flip over any one coin.
• Repeatedly, take any coin showing head, and flip over the coins in the neighboring slots (if any).

The goal is to take all coins.

My question is to describe all winning strategies (i.e., the set of all 'winning' moves at each point in the game), and prove it correct, in the simplest and/or most convincing way possible. Preferably using the least amounts of surprises/'rabbits'.

For completeness, if I got this right, here is the solution that needs to be explained:

• First, if the number of heads is even: Flip over any coin. (Now the number of heads is odd.)
• Then repeatedly: In any 'segment' of non-empty slots, choose the now 1st, 3rd, 5th, ..., or last 'head' coin to take-and-flip-over-neighbors.

(Note that this works for any number of slots, not just for 9 slots.).

Answer 1

OK. Here's a proof: I'll split into two cases:

1. 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

2. The "really good" case, where the game consists of a sequence of coins containing an odd number of Hs. (Details on solving this in a moment)

3. The "sort of bad" case: the game consists of a sequence of adjacent coins, with a nonzero even number of Ts. (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 Ts. To make this explicit: pick the first T and flip it, thus reducing the number of Ts and leaving an odd number of Ts. (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 xs 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 Hs).

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 Hs than the original sequence, i.e., an odd number of Hs, 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 Ts. There are two subcases: T...THTxxx and T...THHxxx. The savvy reader will observe that these are simply a sequence of Ts 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 Hs as before the split, or (ii) two fewer (hence again an odd number of) Hs 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.

Answer 2

Each time we take a coin, we split a contiguous chain of coins into two parts (or only one part if the taken coin is at the end, or no part at all if the chain consisted only of a single coin). As there is no further influence between separate chains, a winnig strategy must ensure that all produced chains are winnable by themselves.

Clearly, a chain of length $1$ is winnable (without the optional flip as first move) iff it shows H.

A chain of length $2$ is winnable only if it is TH or HT, for with TT we cannot take a coind and with HH it becomes T after removing either coin.

We suspect the

Claim. A chain of $n\ge 1$ coins is winnable iff it shows an odd number of H, and a first move is a winning move iff we take a H in an odd positions (among the H's only).

Proof. (By strong induction on $n$). The case $n=1$ is trivial.

Assume $n>1$ and the claim is known to be true for all smaller $n$. Let $k$ be the number of H's. If we take the $i$th of the H's, then (before flipping) there are $i-1$ H's in the left part and $k-i$ on the right.

• If $i$ is even, then $i-1$ is odd and in particular $>0$. After flipping the neighbour of the taken coin, the left subchain has an even number of H's (and still $\ge1$ coins), so by induction hypothesis is not winnable

• If $k-i$ is odd, the same argument shows that the right subchain is not winnable.

• In the remaining case, i.e., if $i$ is odd and $k-i$ is even (so $k$ is even), each of the two subchains is either empty (and won) or has an odd number of H's after flipping (and so is winnable by induction hypothesis)

$\square$

In particular, a single chain of $9$ (or any other number of) coins is winnable iff it has an odd number of H's, and so if the initial state has an even number of coins, we can (and must) flip an arbitrary coin in order to ensure this.

Answer 3

(Here is my answer to my own question. There is still the rabbit of the 'odd/even segments' distinction, but it seems at least reasonable for someone who played around with this game. And it is longer than I had hoped.)

We will first handle the 'main phase' of the game, and then the initial optional move.

After playing around a bit, we see that most take-and-flip-over moves split the initial coin sequence into separate independent sequences. So let's give that concept a name: a segment is a row of slots that all have coins, and the neighboring slots (if any) don't. So the initial state has a single segment, and the winning state has zero segments; and every take-and-flip-over move replaces a segment by zero or more shorter segments, which then get handled independently.

And with some more experimentation, we notice that it seems relevant whether a segment has an odd or even number of heads; let's call these odd segments and even segments. For example, an odd segment like H is immediately winning, and an even segment like HH results in T and we lose with no heads left to take.

What segments result from take-and-flip-over moves? It is easy to see that:

• (1) Taking a heads from an odd segment results in either all odd segments or two even segments:
  • (1a) If one takes the 1st, 3rd, 5th, ..., or last heads then all resulting segments are odd.
  • (1b) If one takes the 2nd, 4th, ... heads then both resulting segments are even.
• (2) Taking any heads from an even segment results in an even segment, and (except if a corner heads is taken) also an odd segment.

So to win it is necessary to avoid even segments, since you can never get rid of them: the only move that affects an even segment is a type (2) move, and that always results in a new even segment. So moves of type (2) are useless, and type (1b) moves must be avoided.

And to win it is also sufficient to have only odd segments, since in that case we are never blocked ('progress'), and we cannot get into an infinite loop ('termination'). With only odd segments we can always make progress by a type (1a) move, since every odd segment has at least one heads. And we always reach the end in a finite number of moves, because every move decreases the maximum segment length down to zero (yes I've chosen $\max(\emptyset)=0$ here), and we have won.

Therefore we must make sure that the optional initial move creates an odd segment, and the full solution is then as follows:

• Only if the initial segment is even, flip over any coin. This makes sure the main phase starts with an odd segment.
• Repeatedly, do any type (1a) move. This will make all slots empty in a finite number of steps, having only odd segments along the way.

Answer 4

(Here is my attempt at a short answer, which has the disadvantage of starting with two fat rabbits.)

We make the following distinctions:

• A segment is a maximal set of neighboring filled slots; we call a segment odd or even based on its number of heads.
• A winner is any heads that has an even number of heads on both sides in its segment. (For example, in THHTHT-HH only the first and third H are winners.) The other heads are losers.

It is easy to see that an odd segment always has a winner (e.g., its first H), and an even segment has no winners.

For the main take-and-flip-over phase we see the following.

• Taking a loser leaves at least one even segment (on one of its 'odd' sides), so it leaves a segment without winners. Therefore we keep having a segment we cannot remove, i.e., we lose.

• Taking a winner leaves no even segments, so each of the new segments (if any) again has a winner. Therefore we can keep taking a winner, which keeps decreasing the maximum segment length, until all coins are taken, i.e., we win.

This proves that we must start the main phase with at least one winner, so

if the initial segment is even (no winners) then we must flip over any coin to make it odd (at least one winner),

and then repeatedly

we must take any winner (which are the 1st, 3rd, ..., last heads in any segment).