Project Euler Problem 121

Statement

A bag contains one red disc and one blue disc. In a game of chance a player takes a disc at random and its colour is noted. After each turn the disc is returned to the bag, an extra red disc is added, and another disc is taken at random.

The player pays £1 to play and wins if they have taken more blue discs than red discs at the end of the game.

If the game is played for four turns, the probability of a player winning is exactly 11/120, and so the maximum prize fund the banker should allocate for winning in this game would be £10 before they would expect to incur a loss. Note that any payout will be a whole number of pounds and also includes the original £1 paid to play the game, so in the example given the player actually wins £9.

Find the maximum prize fund that should be allocated to a single game in which fifteen turns are played.

Solution

My approach was basically find all winning combinations and add its probability to the result.

In order to do that, first I create a list of the probabilities: [1/2, 1/3, …, 1/16]. Then, for each number of blue disks that would give a win, in this case for 8, 9, …, 16. I get all possible combinations of probabilities taken by this numbers. I complete the rest of the combinations with 1 - (missing combination). To get the probability of this combination I multiply the probabilities, finally I add this to the result.

from fractions import Fraction
from itertools import combinations, chain
from functools import reduce
 
turns = 15
 
if __name__ == '__main__':
    result = 0
    prob = [Fraction(1, x) for x in range(2, 2 + turns)]
    for cant in range(len(prob) // 2 + 1, len(prob) + 1):
        for comb in combinations(prob, cant):
            probabilites_per_turn = chain((Fraction(n-1, n) for n in range(2, 2+turns) if Fraction(1, n) not in comb), comb)
            result += reduce(lambda x,y: x*y, probabilites_per_turn)
    print("The result is:", result.denominator // result.numerator)

The Python file is available for download here.

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License