20
$\begingroup$

A player plays the following solitaire game. The game consists of as many rounds as are needed to produce a result. They have 20 fair coins, which may in any round be live or fixed; each coin starts the game live. In each round, the player tosses all the coins which are live, and must then fix at least one of them. The game continues until all coins are fixed.

The player wins if all coins are heads once they are all fixed. What is the probability that the player wins, if they adopt optimal strategy?

My thanks to user joriki for this answer, which contained the essential idea.

$\endgroup$

3 Answers 3

40
$\begingroup$

No matter how many coins are currently live the game only ends on the current flip if we flip all heads, and thus we win, or all tails, and thus we lose. Otherwise we fix some number of heads and continue with a lesser amount of coins. Since, at every step, the probability of all heads is the same as all tails the probability of winning is 50%.

$\endgroup$
8
  • 8
    $\begingroup$ Interesting. My intuition was that "obviously" it is best to fix all the heads you get. But it seems it doesn't matter. $\endgroup$
    – Florian F
    Commented Apr 3 at 15:57
  • 1
    $\begingroup$ @FlorianF it is still best. Equally best among any other non-self-defeating strategy. $\endgroup$
    – justhalf
    Commented Apr 4 at 12:48
  • 2
    $\begingroup$ Yes, in the case you get all heads, you must fix all coins. $\endgroup$
    – Florian F
    Commented Apr 4 at 14:22
  • 2
    $\begingroup$ Yeah, my answer does assume that if you can win on the current throw you do so. Other than that it doesn't matter how many heads you fix each turn. $\endgroup$ Commented Apr 4 at 14:35
  • 2
    $\begingroup$ @NuclearHoagie Fixing all the heads you can is going to end the game in less rounds. fixing all heads = O(log n), fixing only one head O(n). but either stratergy has the same 50% chance of winning. $\endgroup$
    – Nath
    Commented Apr 4 at 22:23
6
$\begingroup$

This is not nearly as elegant as GoblinGuide's simple answer: https://puzzling.stackexchange.com/a/126192/1777

The probability of winning is always:

50%

Strategy:

Strategy:
1) Never fix a tails, if done, then a loss occurs
2) If there are no live coins left, a win occurs
3) Fix some non-zero number of heads, and continue

For any given N coins, there is:

1) exactly one way to immediately lose (flip all tails)
2) exactly one way to immediately win (flip all heads)
3) 2^N - 2 options that allow to fix a number of heads.

The probability of winning with zero live coins is 100%.

The probability of winning with one live coin is 50%, either a heads is flipped and a win occurs, or a tails is flipped and a loss occurs.

The probability of winning with two live coins is also 50%. 25% of the time, two heads are flipped and a win occurs. 25% of the time, two tails are flipped and a loss occurs. The other 50% of the time, we lock one heads and continue with one coin, which has been illustrated to win 50% of the time.

The probability of winning with three live coins is also 50%. 12.5% of the time three heads are flipped and a win occurs. 12.5% of the time, three tails are flipped and a loss occurs. The other 75% of the time, we lock one or two heads and continue with those fewer coins and this has been illustrated to be 50%.

This generalizes to:

Pwin(N live coins) = ((1.0) + 0.5 * (2^N - 2)) / 2^N
Pwin = (1 + 2^(N-1) - 1) / 2^N
Pwin = 2^(N-1) / 2^N
Pwin = 2^(N-1) / (2 * 2^(N-1))
Pwin = 1 / 2

$\endgroup$
3
  • 1
    $\begingroup$ +1 for making me think, but there is a mistake or at least it is unclear if you are forced to keep all heads if they turn up. With two coins there are 4 options, HH, HT, TH, and TT. 2/4 is HT and TH which force you to freeze a single coin and your remaining odds are 50%. But TT is 1/4 loss so with HH you must counter that by always freezing both heads or it turns a win into a 50% chance. $\endgroup$ Commented Apr 5 at 19:06
  • $\begingroup$ If the player doesn't freeze all of the coins when they all come up heads then the probability of winning drops drastically. If it's not all heads, the probability does not depend on how many coins are frozen, but it does lengthen the game if the maximum are not frozen. $\endgroup$
    – LeppyR64
    Commented Apr 5 at 19:19
  • $\begingroup$ It's not that drastically, but it drops by 1/(2^(N+1)) $\endgroup$
    – LeppyR64
    Commented Apr 5 at 19:57
-3
$\begingroup$

Maybe I misunderstood the rules, but I see no need to reach the lose condition.

"They have 20 fair coins, which may in any round be live or fixed": So just never fix any coins except the one you have to fix for every round, until you get all heads.

Therefore the chance to win is 100%.

$\endgroup$
2
  • 10
    $\begingroup$ In case all live coins happen to result in tails you have to fix one tails. And you can't win any more. $\endgroup$
    – Florian F
    Commented Apr 3 at 23:20
  • 5
    $\begingroup$ The idea is that once you fix a coin, it cannot be made live again. Otherwise, as you pointed out, you would never lose. $\endgroup$
    – SQLnoob
    Commented Apr 4 at 1:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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