Results 1 to 5 of 5

Thread: Program required to solve this puzzle.

  1. #1

    Thread Starter
    Frenzied Member
    Join Date
    Jul 1999
    Location
    Huntingdon Valley, PA 19006
    Posts
    1,151

    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?
    Live long & prosper.

    The Dinosaur from prehistoric era prior to computers.

    Eschew obfuscation!
    If a billion people believe a foolish idea, it is still a foolish idea!
    VB.net 2010 Express
    64Bit & 32Bit Windows 7 & Windows XP. I run 4 operating systems on a single PC.

  2. #2
    Addicted Member
    Join Date
    Mar 2001
    Posts
    157
    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.

  3. #3
    Frenzied Member
    Join Date
    Mar 2000
    Posts
    1,089
    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


    And if we loose we get.


    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.
    Last edited by Sam Finch; Jul 23rd, 2001 at 03:35 PM.
    If it wasn't for this sentence I wouldn't have a signature at all.

  4. #4
    Frenzied Member
    Join Date
    Mar 2000
    Posts
    1,089
    An extra atatchment
    If it wasn't for this sentence I wouldn't have a signature at all.

  5. #5

    Thread Starter
    Frenzied Member
    Join Date
    Jul 1999
    Location
    Huntingdon Valley, PA 19006
    Posts
    1,151

    Good Work!

    Chrisf and SamFinch: You guys are good.
    Live long & prosper.

    The Dinosaur from prehistoric era prior to computers.

    Eschew obfuscation!
    If a billion people believe a foolish idea, it is still a foolish idea!
    VB.net 2010 Express
    64Bit & 32Bit Windows 7 & Windows XP. I run 4 operating systems on a single PC.

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  



Click Here to Expand Forum to Full Width