Coin inverting game

Question

Header and Tailer play the following game. At the beginning, the juror lays out a row of $n\ge5$ coins on the table that alternately show heads and tails, with the leftmost coin showing heads. Header and Tailer move alternately, with Header making the first move. In every move

• the active player first takes a coin from his own pocket and adds it (heads or tails) to the row; Header adds his coin at the right end, and Tailer adds his at the left end.
• Then the active player flips an arbitrary sequence of consecutive coins that show the same side.
• A recently added coin can be flipped over only with adjacent coins , but when the same player lays another coin down, it is treated like any other coin.

Header wins if he succeeds to make the row all heads. Tailer wins if he succeeds to make the row all tails. The winner receives all coins on the table (that have been put there by the juror, by the opponent, and by himself).

Question: For which values of $n$ does Header have a winning strategy?

Ps: this is not perfectly answered yet , i did affect the bounty for hardest work, waiting for a specific winning range of n for the header .

Answer 1

Header can win. Here is the quick answer with the more elaborate logic showing how I arrived at it after.

Quick answer

The setup is initially $HTHTH$. On his first turn, Header will add T on the end, making $HTHTHT$. Then he will flip the first $T$ to make $HHHTHT$.

On Tailer's turn, he can add either $T$ or $H$ at the front.

Lets try $T$ first. So, he will make $THHHTHT$. Now he must flip a section.

• If he flips the $HHH$ section, it now becomes $TTTTTHT$. If header plays $H$ and flips the first $H$, Tailer will be left with $TTTTTTTH$. No matter what letter is added, the section of $T$s is the only section that can be flipped, which leaves only $H$s, so Header will win.
• If he flips the middle $T$, then it now becomms $THHHHHT$. Header can play $H$ and flip all the interior $H$s to make $TTTTTTTH$, which is the same as the previous scenario.
• If he flips the last $H$, it becomes $THHHTTT$. Again, Header can add $H$ and flip the section of $H$s to make $TTTTTTTH$ - a guaranteed win for Header.

So now lets try adding $H$ instead. This makes $HHHHTHT$.

• If he flips first section of 4 $H$s, it becomes $TTTTTHT$. Header can again add an $H$ and flip the interior $H$ to get a winning position.
• If he flips the first $T$, then he leave $HHHHHHT$. Header wins easily by adding $H$ and flipping the $T$ to leave all $H$s.
• If he flips the last $H$, it becomes $HHHHTTT$. Again, Header wins easily by adding $H$ and flipping the section of $T$s.

Long Answer

For notation, we will use a version of regex symbols. $^*$ means the previous coin is repeated 0 or more times (i.e. appears at least once).

For example, $HT^*H^*$ can be used to represent $HTH$ or $HHHTTTH$ or $HHTTHH$.

For the following scenarios, Header plays on the end of the string of coins, and Tailer plays at the front.

We will break the solution down to the component parts.

Single section of coins

1a) $H^*$

By definition, this is a win for Header regardless of whose turn it is to play.

1b) $T^*$

By definition, this is a win for Tailer regardless of whose turn it is to play.

Two sections of coins

2a) $H^*T^*$

Either player can win by placing their coin as their own piece and flipping the opponent's. For example, Header can win by playing $H$ to make $H^*T^*H$ and then flipping all the $T$s. Tailer can win by playing $T$ to make $TH^*T^*$ and then flipping all the $H$s.

2b) $TT^*HH^*$

This is a winning position for either player since they can flip their opponents coins to win.

2c) $TH^*$

This is a losing position for Header since he cannot flip the first $T$. Any play he makes will result in 1b) - an automatic win for Tailer.

2d) $T^*H$

Losing position for Tailer.

Three sections of coins

3a) $T^*H^*T^*$

An immediate winning position for Tailer by placing $T$ and flipping the $H$s.

This is also a winning position for Header by placing $H$ to make $T^*H^*T^*H$ and flipping the first section of $H$s to leave $T^*H$. By 2d), this is a losing position for Tailer.

3b) $H^*T^*H^*$

This is obviously a winning position for Header.

This is also a winning position for Tailer since he can play $T$ and flip the section of $T$s to leave $TH^*$, which is a losing position for Header by 2c).

Four sections of coins

4a) $HT^*H^*T$

If Header plays an $H$ and then flips any section, he will leave $H^*T^*H^*$, which is a winning position for Tailer.

If Header plays $T$, he will have $HT^*H^*TT$. Flipping the first set of $T$s leaves $H^*T^*$, a winning position for Tailer by 2a). Flipping the middle set of $H$s leave $HT^*$, also a winning position for Tailer by 2a). Flipping the last set of $T$s leaves $HT^*H^*$, which is three sets of coins, proven by 3b) to be a winning position for Tailer.

Thus, this is a losing position for Header.

By symmetry, this is also a losing position for Tailer.

4b) $TH^*T^*H$

If Header plays an $H$ and then flips any section, he will leave either $TT^*HH^*$ or $THH^*$, or $TH^*T^*$. All three are winning positions for Tailer by 2b) or 3a).

If Header plays $T$, he will have $TH^*T^*HT$. Any move will result in three sections of coins, both of which are shown by 3a) and 3b) to be winning positions for whose ever turn it is.

Thus, this is a losing position for Header.

By symmetry, this is also a losing position for Tailer.

4c) $HH^*T^*H^*TT^*$

This is different from 4a) because Header now has the option to flip the first set of $H$s as well. So, if Header plays $H$ and flips the first set of $H$s, he leaves $T^*H^*T^*H$. This is a losing position for Tailer by 4b), thus Header can win with this setup.

Again, by symmetry this s a winning setup for Tailer as well.

4d) $TT^*H^*T^*HH^*$

This is different from 4b) in that Header can also flip the first section of $T$s. If Header plays $T$ and then flips the first section of $T$s, then Tailer will be left with $H^*T^*H^*T$, which we showed in 4a) is a losing position for Tailer.

Thus, this is a winning position for Header.

By symmetry, this is also a winning position for Tailer.

Five sets of coins

This brings us to the initial configuration for Header: $HTHTH$. By playing $T$ and flipping the first $T$, Header will make the set of coins look like $H^*THT$. This is a known losing position for Tailer by 4a).

Thus, Header can win by playing $T$ and flipping the first $T$.

Answer 2

Start with the case n=5. The winning scenario for H is given below for each combination of starting hands.
1.No T start, direct win
-H H H H H
2.One T sequence start, win at first turn
H H H H T = add a T, then flip the last two.
H X X X H = where single one of the Xs is a T, add a H at the end and flip the T.
H H T T H = add an H, flip the TT sequence.
H T T H H = add an H, flip the TT sequence.
H H H T T = add a T, flip the TTT sequence.
H T T T H = add an H, flip the TTT sequence.
H H T T T = add a T, flip the TTTT sequence.
Summary: Add an H and flip the sequence, if there is a single T sequence and the last coin is not a T. Add a T and flip the sequence, if there is a single T sequence and the last coin is a T.
3.Two T sequences start,
a)
H H T H T = add a H at the end, flip the HH sequence at the beginning.
Player T now has the hand T T T H T H.
Player T can either add a T, T T T T H T H. Now each flip will result in a single T sequence.
Or add a H, H T T T H T H. Now each flip will again result in a single T sequence.
Single T sequence is a one turn win.
b)
H T H H T = add a H at the end, flip the H sequence at the beginning.
Player T now has the hand T T H H T H.
Player T can either add a T, T T T H H T H. Now each flip will result in a single T sequence.
Or add a H, H T T H H T H. Now each flip will again result in a single T sequence.
Single T sequence is a one turn win.
c) H T T H T = add a H at the end, flip the H sequence at the beginning.
Player T now has the hand T T T H T H.
Player T can either add a T, T T T T H T H. Now each flip will result in a single T sequence.
Or add a H, H T T T H T H. Now each flip will again result in a single T sequence.
Single T sequence is a one turn win.
d)
H T H T T = add a H at the end, flip the H sequence at the beginning.
Player T now has the hand T T H T T H.
Player T can either add a T, T T T H T T H. Now each flip will result in a single T sequence.
Or add a H, H T T H T T H. Now each flip will again result in a single T sequence.
Single T sequence is a one turn win.
e)
H T H T H = add a H at the end, flip the rightmost T.
Player T now has the hand H T H H H H.
Player T can either add a T, T H T H H H H. Now each flip will result in a single T sequence.
Or add a H, H H T H H H H. Now each flip will again result in a single T sequence.
Single T sequence is a one turn win.
Summary:If there are two T sequences and T as a last element, add a H at the end and flip the first H. If there are two T sequences and H as a last element, add a H at the end and flip the rightmost T. Then all moves of the opponent causes a single T sequence, which is a one turn win. I will elaborate the algorithm for n>5, if I can find time. All of the cases for n = 6 are covered by n = 5 except for H T H T H T. Proof: All other cases include a pair of coin which can thought as a single pair. Thus covering only this case will prove the same logic for n = 6. Right now as I can see all the possible games starting as H T H T H T can be defended and set in a dead lock by a clever T player. I will try to prove it, when I have the time. If this hand can be defended by T, then all other values of n might also cause such a hand. So n = 5 is the answer (assuming I didn't get lost at some point).

Answer 3

Header has a winning strategy when n is even, ending in T.

For notation purposes, a sequence of H's or T's can be reduced to a single H or T. The row can be simplified as an alternating pattern of H and T.

Flipping a middle sequence of H or T reduces the pattern by a TH (or HT) pair. For example, HTHTH becomes HHHTH, HTTTH or HTHHH. These three are all equivalent to HTH.

Flipping an end (when allowed), removes a letter from the pattern.

Header's winning strategy: Reduce the row to THTHT

if Tailer plays T, (TTHTHT is the same as THTHT) and flips a middle sequence, the row is reduced to THT.

Then Header plays H, making it THTH and flips a middle sequence, resulting in TH. At this point the H is recently added and cannot be flipped at Tailer's turn.

Regardless of what Tailer plays next, the T sequence has to be flipped, making Header the winner.