17
$\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.

Improve this question
$\endgroup$

3 Answers 3

Reset to default
38
$\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%.

Improve this answer
$\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
    Apr 3 at 15:57
  • 1
    $\begingroup$ @FlorianF it is still best. Equally best among any other non-self-defeating strategy. $\endgroup$
    – justhalf
    Apr 4 at 12:48
  • 1
    $\begingroup$ I meant the best. But technically, yes. $\endgroup$
    – Florian F
    Apr 4 at 13:45
  • 2
    $\begingroup$ Yes, in the case you get all heads, you must fix all coins. $\endgroup$
    – Florian F
    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$
    – GoblinGuide
    Apr 4 at 14:35
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

Improve this answer
$\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$
    – Jason Goemaat
    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
    Apr 5 at 19:19
  • $\begingroup$ It's not that drastically, but it drops by 1/(2^(N+1)) $\endgroup$
    – LeppyR64
    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%.

Improve this answer
$\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
    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
    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.