Maximum possible number of turns for a coin flipping game

combinatoricscontest-mathpuzzle

8 coins are in a row and numbered from left to right.

For each turn, we count number of heads. If see k heads among these 8 coins, we flip the k-th coin (H to T, vice versa).

We stop until we see 8 tails and no heads.

What's the maximal number of turns until we stop?

My thoughts: say it's all tails first and the 8th one is head, then we flip from 1 to 7, change them all to heads. Then we change them back to tails. But how do I prove this is maximum?

My thoughts 2: TTTTHHHH will take 36 flips apparently

Best Answer

This is actually interesting.

Let's say there are $n$ coins, and we want to find the maximum flips.

It turns out that,

for $n$ even, the maximum is attained at TT...THH..H, with $n/2$ T and $n/2$ H;

for $n$ odd, the maximum is attained at T...THH...H, with $(n - 1)/2$ T and $(n + 1)/2$ H.

In both cases, the maximun number of flips is $n(n+1)/2$, and the configuration attaining the max is unique.

I'll leave the proof to others, because it's time for bed...

Seems nobody else wants to give a proof ...

OK here we go.

Let $M(n)$ be the maximum number of flips among all configurations of $n$ coins. For such a configuration, there are two possibilities:

  1. The $n$-th coin is T. Then the $n$-th coin will always remain T, until the end of the game. Hence it is essentially a game with $n - 1$ coins and the maximum number of flips is no more than $M(n - 1)$.

  2. The $n$-th coin is H. Then the $n$-th coin will still remain H, until the configuration HH...H is reached. After that, it's easy to see that $n$ more flips leads to the final configuration TT...T.

    Therefore it suffices to consider the number of flips until the configuration HH...H.

    Now we reindex the coins: previously they were indexed $1, 2, \dotsc, n$, and now we index them as $n - 1, \dotsc, 1, 0$. Under this new index system, the rule of flipping becomes: if there are $k$ tails among the first $n - 1$ coins, then we flip the coin with new index $k$. The procedure continues until all the first $n - 1$ coins are H, i.e. we reach the configuration HH...H.

    This is then exactly the same game with $n - 1$ coins, and with heads and tails exchanged. Thus the maximum number of flips until the configuration HH...H is $M(n - 1)$, and hence the total maximum number of flips (until the configuration TT...T) is $M(n - 1) + n$.

Combining 1. and 2., we get $M(n) = M(n - 1) + n$, and the maximum is attained only when the last coin is H, and the first $n - 1$ coins attain the maximum for the game with $n - 1$ coins, with H and T switched and order inversed.

By induction on $n$, this proves exactly our claims.

Related Question