# Coin Tossing Game Optimal Strategy

I was recently asked this question in an interview, but was completely stumped as to how to even begin answering it - it's been bugging me ever since, and I thought it was quite a nice question, so hopefully someone on here can help me out. Any help would be appreciated! Here goes:

You start off with £100 and you toss a coin 100 times. Before each toss you choose a stake $S$ which cannot be more than your current balance $x$ (so your maximum stake for the first toss is £100). If the coin comes up heads, you win $2S$ and your new balance is $x+2S$. If it comes up tails, you lose your stake and have $x-S$. How do you choose your stake so as to maximise your expected winnings from the game, not including the initial balance?

Cheers,

Boris

-
There was a Project Euler problem where your objective was to maximize the chance you finish with at least (as I recall) $10^9$. The thought process is different. –  Ross Millikan Nov 19 '12 at 15:41
It really is as simple as "the bet is in your favor-take it." $S=x$. You win $100(3^{100}-1)$ with probability $2^{-100}$ and lose $100$ with almost certainty. This presumes somebody can pay you that much. The expected win is then $\frac {3^{100}-1}{2^{100}}\cdot 100 -100(1-\frac 1{2^{100}})\approx 4\cdot 10^{19}$
To maybe make this less unbelievable, imagine a two round game. Clearly on the last throw, you want to bet all you have, increasing your expected fortune by $50\%$. On the first throw, then your expectation is $1.5(\frac {x-S}2+\frac {x+2S}2)=1.5(x+\frac S2)$ which (given the rules) is maximized when $S=x$. Alternately, your result is the same if you interchange the two flips. Since you should be all on the last flip, you should on the first as well.
@timboj: yes, it should be winning $100(3^{100}-1)$ You end with $100\cdot 3^{100}$ and started with $100$, so that is the profit. –  Ross Millikan May 23 '13 at 3:31