maximum possible number of turns for a coin flipping game 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
 A: 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:


*

*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)$.

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