Program required to solve this puzzle.

The August issue of Scientific American presented a cute mathematical problem which is very difficult unless you write a program to solve it. It does not look trivially easy with a computer, although I am sure that there are those at this forum who could solve it by writing a VB program.

If I tried to do it with pencil & paper or using a non-programmable calculator, I am sure that I would either lose interest or make a mistake before getting the correct answer.

I will describe the problem in this post, and provide the general method for solving the problem in my next post. I have not written a program to solve it, but have solved trivial variations by hand.

The idea is that you can bet on the flip of a coin at even money, and you have $100.00 available for betting. You can bet all that you have, nothing, or any amount in between on any given coin toss.

There is a predictor who is in fallible at predicting the next coin flip. After telling him how much you want to bet, he makes the bet for you. He will deliberately lose exactly once, so you can rely on winning all but one bet.

He will try to minimize your winnings. Until you lose one bet you dare not risk everything.

First some warmup problems to make sure you understand the game. The solutions to these trivial variations are below. Do not look if you want to try it on your own.

• Decide how to bet if the game consists of only one bet on one coin flip.
  
• Decide how to bet if the game consists of two bets on two coin flips.
  
• Decide how to bet if the game consists of three bets on three coin flips.

The above are easy, with solutions at the end of this post if you want to look now without trying it first.

The real problem is to decide on how to bet if the game consists of ten bets on ten coin flips. Do not try to solve this without a computer. It is too tedious.

The following are solutions for the 3 easy games above.

• If only allowed to make one bet, you must bet nothing. The Ba****rd predictor is out to hurt you and will lose the one and only bet.
  
• If allowed two bets, bet $33.33 (as close as possible to 1/3) on the first flip. If you win, you know that the ba****rd will lose the next bet, so bet nothing on the second coin toss. If you lose the first bet, bet the remaining 2/3 of your money. In either case, you will gain 1/3 of your original bankroll.
  
• If allowed three bets, bet $50.00 or half your money on the first toss. If you lose, bet all on the next two tosses, doubling your original bankroll. If you win the first toss, you now have $150.00 and should bet $50.00 (or 1/3 of your current bankroll) on the second toss. If you win, you have doubled your money and should bet nothing on the third toss (you would lose that final bet). If you lose the second toss, you are guaranteed to win the third, so bet your remaining $100.00, again doubling your original bankroll.

Now are you prepared to deal with ten bets, with nine wins and one loss guaranteed?

It look like if you have n bets remaining and you have not already lost a bet, bet (n-1)/(n+1) of your remaining amount.
You should be left with $9309.

Chrisf has got it, and it's not that hard to prove it.

Say we have a game G(n) where there are n+1 bets remaining and you have not lost yet (we do it this way so that G(0) is the trivial game where you will always loose so don't bet)

Now We Define 2 Functions, based on Chris's strategy.

B(n)
The amount of your money chris would advise you to bet on the first bet of game G(n) it returns a number between 0 and 1, one being all your money and 0 being nothing.

B(n) = n/(n+2)

R(n)
The Amount you will get if you use Chris's Strategy in Game n, as a fraction of your initial investment. (2 you double your money, 1 you break even, 0 you go home broke)

We now propose that R(n) = (2^(n+1)) / (n+2)) and is the best return you can get from game G(n)

So let's test this for game 0.

Using chris's strategy for G(0) we bet B(0) = (0/2) = 0
Which is the best we can get because we will always loose.

R(0) = (2^(0+1))/(0+2) = 2/2 = 1, which is what we would get if we didn't bet anything.



Now we consider the game G(n+1), assuming that Chris's strategy is optimal for Game G(n) and will get us R(n)

So we bet B(n), if we win we get
http://161.58.186.97/attachment.php?s=&postid=444355

And if we loose we get.
http://161.58.186.97/attachment.php?s=&postid=444359

Consider on game G(n+1) we bet more than B(n+1) If we loose we have less than 1-B(n+1) so would make less than if we bet B(n+1) and lost. (ie less than R(n+1)

Consider on Game G(n+1) we bet less than B(n+1) If we win we enter game G(n) with less than 1+B(n+1) and hence make less than R(n+1)

So I'll Sum Up what we have proved so Far.

If for a Game G(n) We Can Make a Maximum of R(n) then...

In Game G(n+1) We will make R(n+1) by betting B(n+1).
But if we bet more or less than B(n+1) the B*stard can make us win less than R(n+1), so there's no way he will let us win R(n+1) or greater.

We have also Proved that chris's strategy is best for game G(0), and will make us R(0) if we use it.

Using the above 2 Statements we see that chris's strategy is also optimal for game G(1) (by putting n=0) and will make us R(1)

And as we have proved the assumption is true for n=1, it is also true for n=2.

in fact by increasing n 1 step at a time we can see that the strategy will be optimal for all n, and we can make a maximum of R(n) on any G(n).



So for Guv's game G(9) we should bet B(9) = 9/11 ($81.82 if we start with 100)
and should in theory make R(9) = 1024/11 ($9309.10) but as we rounded to the nearest penny then we'll make just a tiny bit less.

An extra atatchment

Chrisf and SamFinch: You guys are good.