News for hackers. Stuff that matters.
Re:Project Euler by BenoitP on Wednesday January 15, 2014 @06:24AM (#7062734)
My solution would be:

For one coint toss, I get:

(previous winnings) x (1+f) if I win

(previous winnings) x (1-f) if I lose

Thus, w being the number of times I win, I get the total $$ we would have:

(1+f)^w x (1-f)^(1000-w)

But those cases are not equally likely, so we have to ponderate them with a normal law centered at 1000/2, variance at sqrt(1000/4):

(1/(sqrt(2xPi)xsqrt(250))) x exp(-(500-w)^2/500)

So, now we can take an f, calculate the number of w's that put us above 1B$, and sum up the ponderation for each case. Then find the right f that optimized the chance of being a billionaire. This chance is the solution.

Re:Project Euler by opk on Wednesday January 15, 2014 @10:59AM (#7064039)
I get 1/4 as the optimal value for f. Given a 500/500 win lose, then final money = (1-f)^500*(1+2f)^500 = (-2f^2+f+1)^500. To find the maximum, the ^500 is irrelevant. Differentiating and finding a gradient of 0 gives: -4f+1=0 or f=1/4. Just by checking values, it seems I need to lose more than 555 times before I finish with less then 1 billion. I'm not sure how to calculate the probability of that, your formula doesn't seem to work. In any case, the problem seems to be purely mathematical rather than requiring code to be written.
Re:Project Euler by anonymoushn on Friday January 17, 2014 @12:16AM (#7074427)
I have a different f that can win with only 433 heads.
Re:Project Euler by gjm11 on Wednesday January 15, 2014 @07:49AM (#7063019)
It's actually 1+2f versus 1-f. (I agree that the wording is not very clear. I misinterpreted it too at first and was very confused at how my solution was being rejected. If you look at the short worked example they give, though, it's unambiguous.)

You're using the normal approximation to the binomial distribution. It may or may not be a good enough approximation. Better to do the binomial thing exactly. This requires arbitrary-precision integer arithmetic, but that's pretty easily available.