2

Suppose that there are 3 players and 1 fair coin. Devise a strategy such that we can have a clear winner. The coin can be tossed any number of times and the probability of winning for each candidate must be same.

David G. Stork
  • 29,774
Anit Aggarwal
  • 23
  • 1
    Do you allow infinitely many rolls? If so, you can toss the coin as long as it takes to determine whether the binary "decimal" you get from the string of tosses (taking $H=1$, $T=0$) falls in $(0,\frac 13)$, $(\frac 13, \frac 23)$ or $(\frac 23, 1)$. – lulu Aug 31 '19 at 16:30
  • See also https://math.stackexchange.com/questions/2898509. – joriki Mar 29 '20 at 18:10

2 Answers2

5

There's any number of ways to do it. This is probably the simplest to understand.

If you all flip the same way, then repeat. If not, then the winner is the one who flipped differently than the other two.

0

Matthew’s answer is of course very elegant, and as Ross pointed out, it doesn’t require the coin to be fair.

Since you do have a fair coin, though, you can optimize it a bit in one of two ways (both of which require the coin to be fair):

a) The first player doesn't have to flip the coin. Just pretend they flipped heads and let the other two flip the coin; then proceed as in Matthew’s answer. If the coin is fair, they still all have the same chance to win. (This is equivalent to assigning a winner to $3$ of the $4$ outcomes of two coin flips; but it’s a bit easier to handle than an arbitrary assignment.)

b) If you need to repeat, reuse the identical result of the three flips as the result of the first flip for the repeat.

The expected number of flips required for Matthew’s answer is $3\cdot\frac1{\frac34}=4$.

The expected number of flips required for optimization a) is $2\cdot\frac1{\frac34}=\frac83\approx2.7$.

The expected number of flips required for optimization b) is $2\cdot\frac1{\frac34}+1=\frac83\approx3.7$.

joriki
  • 238,052