54
$\begingroup$

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.

$\endgroup$
  • 4
    $\begingroup$ Great puzzle! +1 $\endgroup$ – Rand al'Thor Dec 28 '14 at 13:37
  • 1
    $\begingroup$ Knowing my luck, I'd probably say 10 and rig their coins :D $\endgroup$ – warspyking Dec 28 '14 at 13:47
  • $\begingroup$ Actually, I rescind my previous comment. Unless I'm getting something completely wrong, it's a dud puzzle! $\endgroup$ – Rand al'Thor Dec 28 '14 at 14:06
  • 2
    $\begingroup$ What happens if you change the rules so that you win if your opponents' coins are the same and lose if they're different? $\endgroup$ – Rand al'Thor Dec 28 '14 at 14:38
  • 1
    $\begingroup$ A very nice puzzle. But what if instead of the condition that the two must eliminate each other, both would have been considered winners? That would make the game fair, won't it? $\endgroup$ – Rohinb97 Dec 28 '14 at 16:02
54
+500
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ I'm also writing out all the cases... there are a lot of them. See if you can find an inductive proof. $\endgroup$ – McMagister Dec 28 '14 at 14:06
  • 2
    $\begingroup$ My first instinct was it's impossible, I just had no proof and knew someone would beat me to it :D $\endgroup$ – warspyking Dec 28 '14 at 14:10
  • 8
    $\begingroup$ @warspyking Its impossibility means there's no point in rigging the coins either! Just refuse to play. Or steal all their coins; at least that gets you some money. $\endgroup$ – Rand al'Thor Dec 28 '14 at 14:12
  • 3
    $\begingroup$ Excellent and rigorous proof! I am reminded of my student days. $\endgroup$ – McMagister Dec 28 '14 at 14:32
34
$\begingroup$

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.

$\endgroup$
  • 3
    $\begingroup$ Very nice! Simpler and more mathematical than my or Callidus's proofs. $\endgroup$ – Rand al'Thor Dec 28 '14 at 18:06
16
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ I got there first, and am proving it more rigorously as well! :-p (PS: welcome to the site!) $\endgroup$ – Rand al'Thor Dec 28 '14 at 14:24
  • 1
    $\begingroup$ Very elegant and intuitive proof! +1 and welcome from me, too. $\endgroup$ – GOTO 0 Dec 28 '14 at 14:25
  • 1
    $\begingroup$ Normally the puzzles get answered before I even see them :-) $\endgroup$ – Callidus Dec 28 '14 at 14:28
  • $\begingroup$ @GOTO0 I've now completed my more rigorous proof. $\endgroup$ – Rand al'Thor Dec 28 '14 at 14:29
  • 1
    $\begingroup$ @randal'thor: I'm afraid to say that even if you were first I do prefer this answer. It is shorter and simpler and rigorous enough for me. :) $\endgroup$ – Chris Dec 28 '14 at 14:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.