15
$\begingroup$

Credit to GOTO0 for the original idea for this puzzle, which is the converse of his puzzle.

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 survives for the next turn. If the neighbours got different results (one heads and one tails), the game is lost for the player sitting in between them. 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 there is exactly one player left sitting at the table, who will be the winner and get an extra 10k rep on Stack Exchange.

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 (e.g. if there are only two players left, since the left and right neighbours will be the same opponent), again it's a tie and nobody gets the prize.

You are offered a chance to play this game and boost your reputation on Stack Exchange. You can choose to play starting with 10, 11, or 12 players including yourself. Which would you choose and why? Please include a full explanation.

[If the 10k rep sounds boring, replace it with $10k, the famous spaghetti recipe, access to Jon Skeet's SO account, or whatever you find worth playing for.]

Disclaimer: I don't know the solution!

Spoiler:

You (probably) won't actually get 10k rep for answering this. The most I can guarantee you is 25 rep for an upvote and accept. Sorry about that.

$\endgroup$
  • $\begingroup$ @MarchHo Thanks! I always like to inject a bit of humour. $\endgroup$ – Rand al'Thor Dec 28 '14 at 17:11
  • $\begingroup$ Sorry warspyking, that prize was crazily big! Not even Jon Skeet would give that away, but 10k in a bounty might be possible on Stack Overflow for all I know. $\endgroup$ – Rand al'Thor Dec 28 '14 at 17:14
  • $\begingroup$ Well what site do we get 10K on? Lol $\endgroup$ – warspyking Dec 28 '14 at 17:26
  • 1
    $\begingroup$ my impression is, that after having the original question (as a new idea with an interesting answer a I UV it!), any follow-up "explore this alternative"-question is better suited for math SE than puzzlingSE.In particular if you don't know the answer and therefore also don't know if it is in any way entertaining. -1 from me for this puzzle (at least for now) $\endgroup$ – BmyGuest Dec 29 '14 at 7:53
  • 1
    $\begingroup$ @BmyGuest You're still the only downvoter... $\endgroup$ – Rand al'Thor Mar 12 '15 at 22:35
9
$\begingroup$

Lopsy answered 11. rand al'thor then asked to consider e.g. 9 and 13. I will give a recursive formula for the probability of winning for a game of $N$ players. According to Lopsy's Lemma, for $N$ even there is no chance of winning so I consider only odd $N$.

First, let me define notation for two types of sequences of coins. I use $B(n_1)$ for a "block" sequence of same sided coins, of length $n_1$. E.g. $B(5)$ can be $TTTTT$ or $HHHHH$. I use $A(n_2)$ for an "alternating" sequence of coins, of length $n_2$. E.g. $A(5)$ can be $THTHT$ or $HTHTH$. We also define the following when combining sequences:

  • $A$ types concatenate with $A$ types, and $B$ types concatenate with $B$ types. Namely $A(n_1)A(n_2) = A(n_1 + n_2)$ for any integers $n_1, n_2$, and similarly for $B$ types. Without loss of generality I will only consider fully concatenated forms from here on.

  • An $A$ type sequence always starts with the opposite of the preceding coin, e.g. $B(2)A(2)$ corresponds to $TTHT$ or $HHTH$.

  • A $B$ type sequence always starts with the same side as the preceding coin, e.g. $A(2)B(2)$ corresponds to $THHH$ or $HTTT$.

Note that any periodic sequence can be described by combining $A$ and $B$ type sequences and specifying the first coin. E.g., $TH H THTHTH HH$ is described by specifying $T$ as the first coin, then $A(2)B(1)A(6)B(2)$.* I call such forms "canonical", i.e.

The canonical form of a periodic sequence specifies the first coin in the sequence, and a list of alternating $A$ and $B$ type sequences of specified lengths.**

Note that canonicalization provides a bijection from the set of all length-$N$ periodic coin sequences to the set of all length-$N$ canonical forms having an even number of coins contained in $A$-type subsequences.

Let us consider just the first round of an N player game. Without loss of generality, assume my coin is $T$. Starting from me, looking to the left, and skipping every other player, I write the sequence of $N$ coins in canonical form. (This is the counting scheme from Lopsy's lemma.) Let $N_A$ denote the total number of coins contained within $A$-type subsequences. Note that $N_A$ is the number of people eliminated in this round and $N_A$ must be even (see Lopsy's answer). Therefore the probability of $N_A$ people being eliminated is

$$ \frac{\binom{N}{N_A}}{2^{N - 1}}. $$

Since I assumed I have $T$, we have only $2^{N-1}$ possible sequences of coins in the denominator.$\dagger$

Denote the probability that in a single N-player round, $N_A$ people are eliminated, while I am not eliminated, as

$$ P_1(N, N_A) = \left(1 - \frac{N_A}{N}\right) \frac{\binom{N}{N_A}}{2^{N - 1}}. $$

We must now consider all possibilities recursively. Denote the probability of winning the entire N-person game as $P(N)$. Then $P(1) = 1$, and for $N > 1$,

$$ P(N) = \sum_{N_A} P_1(N, N_A) P(N - N_A), $$

where the sum runs over all even, positive integers $N_A$, such that $N_A \leq N - 1$.


*: Note that the first coin is "preceded" by the last coin since this is a periodic sequence. The last coin differs from the first, and is part of a $B$ type sequence, so the first coin is the start of an $A$ type sequence. To be more rigorous, the construction should go like $TA(1)B(1)A(6)B(2)$, then $A(1)A(1)B(1)A(6)B(2)$, then $A(2)B(1)A(6)B(2)$.

**: Note that the first and last sequence types can be the same. E.g., $T$, $A(2)B(3)A(2)$ is in its canonical form.

$\dagger$: If we let my coin be $H$ or $T$, then both the numerator and denominator will pick up a factor of two. Another way to obtain the denominator is by summing over all possible eliminations, i.e. $\sum_{i=0}^{(N - 1) / 2} \binom{N}{2i} = 2^{N-1}$.

Edit 12/28: Clarify why the example "canonical form" starts with $A(2)$, and that the canonical form is for periodic sequences.
Edit 12/29: Fix factor of 2 in probability of eliminating $N_A$ players, as pointed out by Lopsy.

$\endgroup$
  • 3
    $\begingroup$ This is awesome. Just one issue: I'm getting that the probability that $N_A$ people are eliminated is $2\binom{N}{N_A}/2^N$ when $N_A$ is even. When $N$ is odd, for any even-sized subset of players, there are exactly two ways to eliminate exactly that subset. (These two ways have the same canonical form, except that the first coin is flipped.) $\endgroup$ – Lopsy Dec 29 '14 at 4:02
  • 1
    $\begingroup$ Lopsy, thanks for the correction. I've edited it. $\endgroup$ – Andy Lee Dec 29 '14 at 13:47
  • $\begingroup$ Lopsy, also note that the canonical form specifies the first coin so it uniquely specifies the sequence of coins. This doesn't affect the crux of your comment though. $\endgroup$ – Andy Lee Dec 29 '14 at 14:01
  • $\begingroup$ Sorry for the late acceptance; until recently I haven't been active here for quite a while. $\endgroup$ – Rand al'Thor Mar 12 '15 at 23:24
10
$\begingroup$

Lemma: On any given turn, an even number of players are eliminated.

Proof: Go around the circle, skipping every other coin. Every time the coin you see changes from tails to heads or vice versa, the person you skipped over gets eliminated. You must see an even number of changes before returning to the start, so there are an even number of eliminations in this cycle.

If there are an even number of players, there are two "skip every coin" cycles. If there are an odd number of players, there is one cycle which passes around the circle twice. Either way, since every cycle contains an even number of eliminations, an even number of players get eliminated.


By the lemma, if you start with 10 or 12 players, then you will always have an even number left, so you are screwed. Therefore, you should sit at the 11-seat table. There, you at least have a $9465137/134217728 \sim 7\%$ chance of winning that delicious spaghetti (src: computer program).

$\endgroup$
  • $\begingroup$ Great answer! How did you get 7% though? What would happen if I'd also included options for 9 or 13? $\endgroup$ – Rand al'Thor Dec 28 '14 at 18:05
  • $\begingroup$ I just wrote a computer program to enumerate all the possibilities. There may or may not be a clever mathematical recurrence. $\endgroup$ – Lopsy Dec 28 '14 at 18:55
  • $\begingroup$ To compute the probability of winning you don't need any fancy calculations. You just need the fact that all players have equal chances of winning, hence the probability is 1/N. So it should be 9%. $\endgroup$ – Bogdan Alexandru Oct 13 '16 at 13:57
2
$\begingroup$

I'll just start this off, to provide a springboard for somebody else...

If there are exactly 2 people left, nobody can win.
If there are exactly 3 people left, there's a 25% chance of each person winning and a 25% chance that nobody wins. (Note to self: clarify rules. If the toss is such that nobody wins, but it is possible for somebody to win with that number of players, do they keep tossing until somebody wins, or declare the game a tie? Now clarified! They declare the game a tie. I think this makes the problem better than the other alternative would.)
If there are exactly 4 people left, then either 0, 2, or 4 must be eliminated, so nobody can win.

Keep going, guys! :-)

$\endgroup$
0
$\begingroup$

This should really be a comment on Lopsy's answer:

By your Lemma, if you start with 11 players you will always have a winner, and since the game is symmetrical with respect to the players, why shouldn't the chance of winning be 1/n when n is odd?

$\endgroup$
  • 1
    $\begingroup$ Because there's also a chance of the game being a tie. Zero is an even number, so zero players could be eliminated in a round, at which point the game stops. $\endgroup$ – Rand al'Thor Dec 29 '14 at 11:46
  • 3
    $\begingroup$ I think mods have the power to convert answers to comments, so I just flagged this for their attention. $\endgroup$ – Rand al'Thor Dec 29 '14 at 11:47

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.