Left coin, right coin, last coin?

Question

In this game, all players start sitting at a round table, each with a coin in their hand. At every turn, all players toss their coins together and put them on the table in front of them. Then each player looks at the coins tossed by his left and right neighbours. If the neighbours tossed different faces of the coin (one obverse and one reverse), the player in the middle survives for the next turn. Otherwise, if the neighbours both tossed the same face of the coin (both obverse or both reverse), the game is lost for the player sitting in between them.

After everybody knows who's continuing to the next turn, the losers pick up their coins and leave the table.

The game is won when there is exactly one player left sitting at the table, who will be the winner and grab the lucky $10 bonus.

If all players are eliminated at the same time, the game is a tie and nobody gets the bonus. If there are only two players left, since left and right neighbours will be the same opponent, the players will necessarily eliminate each other at the next turn.

You are offered a chance to play this game and grab the lucky $10 bonus. You can choose to play in a game starting with 10, 11, or 12 players including yourself.

What would you choose and why?

If the lucky $10 bonus sounds boring, replace it with 10 rep points or whatever you find worth playing for.

Answer 1

It doesn't matter which option you choose, because

it's impossible to win.

Your probability of survival if you're one of n players left is as follows:

n=1: 100% (obviously!)
n=2: 0%
n=3: 0%
n=4: 0%
n=5: 0%
n=6: 0%
n=7: 0%
n=8: 0%
n=9: 0%
n=10: 0%
n=11: 0%
n=12: 0%

Informal proof
It was established in the question that if there are only 2 players left, they must annihilate each other. So if there are 3 left, your only hope of survival is to annihilate both your opponents, which can only happen if your result (WLOG, heads) is the same as both of theirs, which means their results must be the same, which means you're annihilated too.

The same argument goes on. If there are $n$ players left, where $n>1$, your only hope is to annihilate them all in one go (since all lower cases have been checked), which means annihilating yourself too. The proof is slightly different for odd and even $n$.

Formal proof
Let $S_n$ be the statement that if there are n players left, you can't possibly win. We've already proved $S_2$ and $S_3$, so by strong induction it will suffice to prove that

if $S_k$ is true for $1<k<n$, then $S_n$ is true.

If $S_k$ is true for $1<k<n$ and you're one of n players remaining, your only hope is to annihilate all your opponents in one go. (Otherwise, at the next stage you'll be one of $k$ players remaining where $1<k<n$, so you lose by the induction hypothesis.) WLOG, assume your coin comes up heads. Say you're A and the players on your left are B, C, D, ... while those on your right are Z, Y, X, ... (I'm not assuming $n=26$; this is just notationally convenient.) To eliminate B, you need C to get heads; then to eliminate D, you need E to get heads, and so on. Similarly, to eliminate Z, you need Y to get heads; then to eliminate X, you need W to get heads, and so on.

If $n$ is odd, you're already done at this stage because by proceeding in steps of 2 you cover all the other players before coming back to yourself (whom you don't want to eliminate!), so everyone gets heads and you get eliminated too.

If $n$ is even, you now know that you need every second player, starting from yourself, to get heads. In order to eliminate C, you need B and D to get the same (doesn't matter whether it's heads or tails); then to eliminate E, you need D and F to get the same, and so on. Taking this all the way round, you find that B, D, F, H, ..., V, X, Z (ending with Z since you know $n$ is even) to get the same result. But B and Z getting the same result means you get eliminated too.

So you can't win when there are $n$ players remaining. QED.

Answer 2

The answers of rand al'thor and Callidus are great; I just want to give a different argument for the result.

Claim: After each round, the number of surviving players is even.

Proof: Let $f_i$ be the flip of player $i$, with tails $1$ and heads $0$ (it's arbitrary which is which). Let $s_i$ be $1$ if player $i$ survives the round and $0$ otherwise. Then, the condition that a player survives is his neighbors' flips are opposite can be written as

$$s_i = f_{i-1}+f_{i+1} \bmod 2, $$

wrapping indices around. Adding these equations for every player, each $f_i$ appears in exactly two summands, which cancel modulo $2$.

$$ \sum_i s_i = 2 \sum_i f_i = 0 \mod 2$$

So, an even number of $s_i$ are $1$, which means an even number of players survive. Therefore, in particular, you cannot be the only surviving player after any round.

Answer 3

It doesn't matter; you can't win.

If there are two players left, both lose.

If there are three players left:

If all get the same coin face, all lose. If one is different, that player loses and the other two keep playing; but there are two of them and they lose.

If there are four players left:

If all get the same coin face, all lose. If one is different, that player and the one opposite lose, and there are only two left, they lose. If it's HTHT, everyone loses. If it's HHTT, everyone keeps playing and eventually loses.

If there are more:

You need to eliminate everyone but yourself in one go or you'll end up with one of the unsurvivable low numbers above. Suppose you get H, then you need a H on one side, T on the other. On the H side, it needs to be H's all the way or someone else will survive. On the T side, it needs to be alternating H/T all the way, like this: ...HHH-You-THTH.... Where these meet at the other side of the table, the two sequences can't continue and so someone else will survive (maybe more, but that just leaves us with another round).