4
$\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 it on the table in front of them. Then each player looks at the coins tossed by his left and right neighbours.

If the neighbours got the same result (both heads or both tails), the player in the middle gets eliminated and doesn't get to play further.
If the neighbours got different results (one heads and one tails), the player sitting in between them survives for the next round.

All the eliminated players pick up their coins and leave the table , and the remaining players proceed to the next round.

The game is won when only two players remain seated on the table.
Those two then get the ultimate prize - the ultimate honor of getting to see the secret spaghetti recipe.

If all players are eliminated at the same time, the game is a tie and nobody gets the prize.

If the coin-toss is such that nobody gets eliminated, then the game continues normally. No tie or everyone wins thingy.

No changing of seats in between the game.

You and your friend are offered a chance to play this game and try your luck. The aim is for at least one of the two of you to survive until the end of the game.

You can choose your and your friend's seats, and you can also choose to play starting with 10, 11, or 12 players including yourself and your friend.

Which would you choose and why? Please include a full explanation.

Thanks to @GOTO0 and @randal'thor for the original idea for this puzzle. This is just another version of the original one.

$\endgroup$
  • $\begingroup$ In a 4-player round, there's a 25% chance everyone gets eliminated, a 50% chance that exactly two get eliminated, and a 25% chance nobody gets eliminated. What happens in the latter case? Does everyone continue tossing until somebody gets eliminated (which they must eventually, with probability 1)? $\endgroup$ – Rand al'Thor Dec 29 '14 at 12:38
  • $\begingroup$ Another question: do you want to maximise the probability that you survive to get the recipe, or that you and your friend end up as the last two players? $\endgroup$ – Rand al'Thor Dec 29 '14 at 12:38
  • $\begingroup$ Are both you and your friend playing? If so, can you both choose where to sit at the start? Can you change positions every time someone gets eliminated? $\endgroup$ – Lopsy Dec 29 '14 at 13:50
  • $\begingroup$ Thanks @randal'thor. Looks more clean now. And I just want to maximize the probability that either me or my friend gets the recipe. But if it's both of us then it's great. $\endgroup$ – Rohinb97 Dec 29 '14 at 13:50
  • $\begingroup$ @Rohinb97 - Either you or your friend? Damn - that makes most of my answer redundant. What about the nobody-eliminated thing (which I think can only happen when there are 4 players remaining)? $\endgroup$ – Rand al'Thor Dec 29 '14 at 13:54
4
$\begingroup$

Partial answer. No matter how many players there are, I believe you and your friend should sit next to each other.

For example, suppose there are 4 players left. If you and your friend sit next to each other, then you have a $2/3$ chance of winning a spaghetti recipe. If you sit across from each other, it's only $1/3$.

Lemma: Given the choice between a 1/2 probability of both you and your friend surviving, and a certain chance that exactly one of you is eliminated, you should choose the latter.

Proof: The first choice gives $\frac 12 (\Pr[\text{You win}]+\Pr[\text{Friend wins}]-\Pr[\text{You both win}])$ chance of getting a spaghetti recipe. The second choice gives $\frac 12 (\Pr[\text{You win}]+\Pr[\text{Friend wins}])$, a larger chance. $\square$

By choosing our seats, my friend and I cannot influence our individual probabilities of surviving. However, we can influence the probability that we both survive. The lemma tells us that we want to make this probability as small as possible. We'd rather exactly one of us survive.

Now, when there are an even number of players left (which, after the first round, there always will be), you can split the players into two cycles. Each cycle contains every alternate player. Call the cycles $A$ and $B$. In each of these cycles, an even number of players live on.

Suppose you live in cycle $A$ and you survive. This has no influence on cycle $B$, but it does mean that at least one other person in cycle $A$ has to live. If you survive, then you want your friend to be eliminated, so you should put your friend in cycle $B$. If you and your friend sit next to each other, then you are always in different cycles.

Admittedly, this is not a proof, because the situation is more complicated. Sometimes nobody wins the game. So we really want to maximize

\[ \Pr[\text{Exactly one of us survives | Somebody wins the game}]. \] But I conjecture that this doesn't affect the result.

TL;DR I'm guessing that you want to sit next to your friend at a table of as few people as possible.

$\endgroup$
  • 3
    $\begingroup$ This answer is really "I'm going to guess what the correct answer is, given that the correct answer will come from a computer program." $\endgroup$ – Lopsy Dec 29 '14 at 15:01
1
$\begingroup$

Partial answer...

If there are 2 players left, you win.

If there are 3 players left, there are 4 possibilities, all equally likely: everyone eliminated, only player A eliminated, only player B eliminated, only player C eliminated. So you have 50% chance of surviving.

If there are 4 players left, there are 4 possibilities, all equally likely: everyone eliminated, nobody eliminated, the players on either side of you eliminated, you and the player opposite you eliminated. Assuming that the 4 players keep tossing until someone is eliminated, the second possibility is out, leaving you with a 1/3 chance of surviving. EDIT: unless everyone is eliminated, either you or the player on your left must survive. So there's a 2/3 chance of either you or your friend surviving, provided you can choose where your friend sits.

If there are 6 players left, then there's a 1/2 chance you're eliminated, a 1/8 chance you and one other player survive, and a 3/8 chance you and three other players survive. So your chance of surviving the whole game is $\frac{1}{8}+\frac{3}{8}.\frac{1}{3}=\frac{1}{4}$. This might be redundant. What are the chances of either you or your friend surviving?

I got all of this just by brute-forcing it: going through all the possibilities.


A general statement: in each round, you have exactly 50% chance of surviving to the next round (since the results of the players on either side of you could be HH, HT, TH, TT with equal probability).

Another general statement, thanks to xnor: after each round, the number of surviving players is even. So all that's left to calculate is your chance of ultimate survival starting with 8, 10, 11, or 12 players (we don't need to worry about 7 or 9, or for that matter 3 or 5).

$\endgroup$

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.