Euler Solution 121

From ProgSoc Wiki

Jump to: navigation, search

Solutions for Problem 121

There is a game played with coloured disks. The first turn starts with one blue and one red disc in a bag. The player picks a disc at random and then places it back in the bag along with another red disc for the next turn. The player wins if they pick more blue discs than red discs.

The probability of winning over 4 turns is exactly 11/120. If the player pays $1 to play, the maximum payout the casino should pay is $10 (including the initial $1) before they incur a loss.

What is the maximum payout for a game played over 15 turns?

Haskell by SanguineV

Runtime: 9.145 ms

{- Calculate the probability that the player wins over a number of turns. -}
pnt :: Int -> Double
pnt t = inner t (div t 2 + 1) 2
  where
    inner :: Int -> Int -> Double -> Double
    inner t w _ | t < w = 0
    inner 0 _ _ = 1
    inner _ 0 _ = 1
    inner t w d = ((1/d) * (inner (t - 1) (w - 1) (d + 1))) 
                       + (((d - 1)/d)*(inner (t - 1) w (d + 1)))

{- Calculate the maximum payout for a game with a given number of turns before
 - the house incurs a loss. -}
payout :: Int -> Integer
payout turns = last (takeWhile (\x -> (fromIntegral x) * win < lim) [1..]) + 1
  where
    win = pnt turns
    lim = 1 - win

{- Calculuate the result for a game of 15 turns. -}
main = print (payout 15)

I am not sure why this is rated so hard, the probability is not overly tricky (and that is the hardest part). I await a blindingly fast version in C Java!

Personal tools