Edit: I started out trying to get a formal proof of optimality, but abandonded that. I leave the work here for someone else to continue if they see any merit. I did run some simulations if anyone wants to come up with a strategy they will have to do better than this.
There are two ways to win as stated in the puzzle;
- Everyone wins if you get 100 coins
- If one person loses by running out of coins on their turn, then the other two win.
Win By Knockout
This happens when one person bets all the remaining coins and loses. Obviously, if there is more than 1 coin, it would be silly to bet it all because you'd have a 50% chance of losing outright.
Betting all but one seems like a good choice. It maximises the chances of a quick win because if you lose, the next person losing means the game is over. If you win, and the next two people lose, then you also win. The only time you lose is if there is a Win-Loss right before your turn, and you throw a tails. In fact, we can easily enumerate the possibilities of the next three tosses.
For the following, $P_X(N)$ is the probability of $X$ winning on Alice's turn with $N$ coins in the pot.
A B C P_A P_B P_C
T T T Win Lose Win
T T H Win Lose Win
T H T P(1)
T H T P(N)
H T T Win Win Lose
H T H P(N)
H H T P(1)
H H H P(N)
- 3/8 times Alice wins, 1/8 Bob wins, and 2/8 Carole wins
- 3/8 times it is Alice's turn again with multiple coins
- 2/8 times Alice is faced with a potentially losing toss because she has only 1 coin left in the pot
This gives:
$$P_A(N)= \frac{3}{8} + \frac{3}{8}P_A(N) + \frac{2}{8}P_A(1)$$
$$8P_A(N) = 3 + 3P_A(N) + 2P_A(1)$$
We can also get Bob and Carole's chances too.
$$P_B(N) = \frac{1}{8} + \frac{3}{8}P_B(N) + \frac{2}{8}P_B(1)$$
$$5P_B(N) = 1 + 2P_B(1)$$
$$P_C(N) = \frac{2}{8} + \frac{3}{8}P_C(N) + \frac{2}{8}P_C(1)$$
$$5P_C(N) = 2 + 2P_C(1)$$
Lets explore $P_A(1)$. If she throws tails, then she loses. If not, then the game continues. Lets do the next three throws;
A B C P_A P_B P_C
T T T Lose Win Win
T T H Lose Win Win
T H T Lose Win Win
T H H Lose Win Win
H T T Win Win Lose
H T H P(N)
H H T P(1)
H H H P(N)
Thus:
$$P_A(1)= \frac{1}{8} + \frac{1}{8}P_A(1) + \frac{2}{8}P_A(N)$$
$$7P_A(1) = 1 + 2P_A(N)$$
$$P_B(1)= \frac{5}{8} + \frac{1}{8}P_B(1) + \frac{2}{8}P_B(N)$$
$$7P_B(1) = 5 + 2P_B(N)$$
$$P_C(1)= \frac{4}{8} + \frac{1}{8}P_C(1) + \frac{2}{8}P_C(N)$$
$$7P_C(1) = 4+2P_C(N)$$
Substituting back in, we can solve for both $P_A(1)$ and $P_A(N)$.
$$P_A(1) = \frac{11}{31}, P_A(N) = \frac{23}{31}$$
Thus, Alice will have a 71% chance of winning using this strategy from the start.
We can work out the chances for Bob and Carole as well.
$$P_B(N) = \frac{17}{31}, P_B(1) = \frac{27}{31}$$
$$P_C(N) = \frac{22}{31}, P_C(1) = \frac{24}{31}$$
So when it is Alice's turn with a single coin, she has the lowest chance of winning ($\frac{11}{31}$) while the other two have greater chances. Bob, in fact, has only a $\frac{4}{31}$ chance of losing at this point! It makes sense because there is a 50-50 chance of Bob winning right away, and even if Alice stays alive with heads, Bob still gets a chance to force Carole into a bad spot. It takes 4 turns before there is even a possibility of Bob losing.
However, when it is Alice's turn with multiple coins, you can see she has the best chance of winning. Bob has the worst because he may be forced to bet everything on his turn. Carole is only marginally worse, likely because there is a chance she could lose before Alice gets a second turn.
CAVEAT This does not take into account the pot doubling on each heads toss and exceeding 100, which also counts as a win.
Other strategies
There is some merit to say leaving 2 coins for the next player. If the others follow the same strategy, you are guaranteed to not lose on your next turn, but you may be left with only 2 coins, and potentially forcing the next player into the tough spot. It is easy to see that this strategy makes the game last longer, and the longer it is, the more random chance is involved. Perfectly random length games will favour each player the same, so your chances should tend towards $\frac{2}{3}$. However, here is the analysis to show this strategy isn't as good as the other.
We need three tables, one for $P(N)$, $P(2)$, and $P(1)$.
Lets start with $P(N)$.
A B C P_A P_B P_C
T T T Win Win Lose
T T H P(2)
T H T P(2)
T H H P(N)
H T T P(1)
H T H P(N)
H H T P(2)
H H H P(N)
So we get the following three equations:
$$5P_A(N) = 1 + P_A(1) + 3P_A(2)$$
$$5P_B(N) = 1 + P_B(1) + 3P_B(2)$$
$$5P_C(N) = P_C(1) + 3P_C(2)$$
Now lets look at $P(2)$.
A B C P_A P_B P_C
T T T Win Lose Win
T T H Win Lose Win
T H T P(1)
T H H P(N)
H T T P(1)
H T H P(N)
H H T P(2)
H H H P(N)
Yielding:
$$7P_A(2) = 2 + 2P_A(1) + 3P_A(N)$$
$$7P_B(2) = 2P_B(1) + 3P_B(N)$$
$$7P_C(2) = 2 + 2P_C(1) + 3P_C(N)$$
Lastly, $P(1)$.
A B C P_A P_B P_C
T T T Lose Win Win
T T H Lose Win Win
T H T Lose Win Win
T H H Lose Win Win
H T T Win Win Lose
H T H P(2)
H H T P(2)
H H H P(N)
Which gives:
$$8P_A(1) = 1 + 2P_A(2) + P_A(N)$$
$$8P_B(1) = 5 + 2P_B(2) + P_B(N)$$
$$8P_C(1) = 4 + 2P_C(2) + P_C(N)$$
Solving, we get the following:
$$P_A(1)=\frac{5}{13}, P_A(2)=\frac{9}{13}, P_A(N)=\frac{9}{13}$$
$$P_B(1)=\frac{11}{13}, P_B(2)=\frac{9}{13}, P_B(N)=\frac{7}{13}$$
$$P_C(1)=\frac{10}{13}, P_C(2)=\frac{8}{13}, P_C(N)=\frac{10}{13}$$
Since $\frac{9}{13} \lt \frac{23}{31}$, this strategy is inferior for Alice to use on her turn when she has more than 2 coins.
Winning Co-operatively
There is another way to win. If there are sufficient coins, then they can work together to bet the minimum each time. For example, if there are 95 coins, Alice can bet 5, and everyone wins on heads. If not, then Bob can bet 10 and everyone wins. There would need to be 4 failures in a row before there wouldn't be a chance to win again. In fact, if there was a strategy to guarantee this method, then everyone would use it because there is no way anyone can lose with it.
So the question becomes, at what point does this strategy win out over the previous?
Well, lets say that if Alice loses her current toss, then Bob player cannot win co-operatively. Bob would revert to the other strategy and bet all but 1 coin. If Bob loses, Alice has a decent shot at winning because Carole will be betting the last coin. If Bob wins, then he would put the pot higher than the original amount, and thus Carole would be playing the co-operative strategy again. So there isn't much downside to playing co-operatively.
This yields the following strategy:
- If the pot has 51 coins or more, then bet $100-pot$.
- Otherwise, bet $pot-1$
Results
Simulations show that the competitive strategy of always betting all but 1 coin gives Alice a 77.6% chance of winning. Of all the games, only 13.2% of them result in everyone winning.
However, the composite strategy of playing cooperatively and only betting enough to win when there are lots of coins yeilds a much better result for Alice at 84%. The number of games where everyone wins also increases to 20%.
Python Code
import sys
import random
import math
WINS=[0,0,0]
POT = 20
TRIALS = int(sys.argv[1])
losses = 0
for trial in range(TRIALS):
# We will run a simulation of the game.
pot = POT
turn = 2
while pot > 0 and pot < 100:
# Advance to the next turn.
turn = (turn + 1) % 3
# The bet will be just enough to win, otherwise all but 1.
bet = max(min(100-pot, pot-1),1)
if random.getrandbits(1):
# The bet was a win!
pot += bet
else:
# The bet was a loss.
pot -= bet
# Everyone gets a win...
WINS[:]=[wins+1 for wins in WINS]
if pot == 0:
losses += 1
# ...except whoever just lost
WINS[turn] -= 1
# Display the wins
print(f"The wins are: {WINS} and losses are {losses}.")