Suppose Alice and Bob want to play a game sharing an unbiased coin.

In her turn, Alice flips the coin only once. If she gets heads she sums one point, none otherwise. Then she hands the coin to Bob.

To make things more interesting, each turn he chooses how many times he'll flip the coin beforehand. If he decides to flip $k$ times and he gets heads $k$ times in a row he sums $2^{k-1}$ points.

\begin{array}{|c|c|} \hline \text{Times he flips the coin} & \text{Probability of getting all heads in a row}& \text{Points} \\ \hline 1 & \frac{1}{2} & 1 \\ \hline 2 & \frac{1}{4} & 2\\ \hline 3 & \frac{1}{8} & 4\\ \hline \vdots & \vdots & \vdots \\ \hline k & \frac{1}{2^{k}} & 2^{k-1} \\ \hline \end{array}

If he gets tails anytime, his turn is over and he doesn't sum points.

The player who reachs 1000 points first is the winner.

Bob knows his maths, so he always chooses k to be the number that maximises his chances of winning.

What is the probability of Bob winning the game?


closed as off-topic by Saad, ancientmathematician, Gibbs, Jose Arnaldo Bebita-Dris, Mark S. Sep 22 '18 at 11:58

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "This question is missing context or other details: Please improve the question by providing additional context, which ideally includes your thoughts on the problem and any attempts you have made to solve it. This information helps others identify where you have difficulties and helps them write answers appropriate to your experience level." – Saad, ancientmathematician, Gibbs, Jose Arnaldo Bebita-Dris, Mark S.
If this question can be reworded to fit the rules in the help center, please edit the question.

  • $\begingroup$ Can Bob choose a different $k$ each turn? $\endgroup$ – Mike Earnest Sep 21 '18 at 17:34
  • $\begingroup$ Yes. I've missed that detail. $\endgroup$ – Luciano Arlandis Sep 21 '18 at 17:41
  • 1
    $\begingroup$ Project Euler asks that you not solicit help for their problems. $\endgroup$ – Ross Millikan Sep 21 '18 at 20:54

A will take about 2000 turns.
Going all-out $k=11$ every time gives B around $1/e$ chance of losing, compared with $3/e^2$ for $k=10$, and $71/3e^4$ for $k=9$. So choose $k=11$.


What a coincidence, I just solved this ProjectEuler problem 232 yesterday. Not giving out the answer :D, but here's a:

Hint: Make a $1000\times 1000$-table containing at the index (i, j) the probability that Bob will win when Alice has i points and Bob has j points, and it is Bob's turn. And maybe another table storing what is the best move for Bob in each situation. Then start to calculate the table from the end, so you can utilize the previously calculated probabilities in the calculations for smaller $i$ and $j$. Also, find the $k$ ($T$ in ProjectEuler's notation) that maximizes the probability.


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