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
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
If $S_k$ is true for $1 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.
No comments:
Post a Comment