The following code solves Project Euler Problem 121. I will quote the description of the problem
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.
I will explain my reasoning using example provided by the Euler:
So we have 4 turns (N = 4). Problem specifies that we need to pick more blue discs than red discs. In other words, we need to pick either 3 blue discs of 4 blue discs in order to win.
If we pick 4 blue discs, calculating probability is simple: 1/2 * 1/3 * 1/4 * 1/5 = 1/120
However, with 3 blue discs, situation is slightly more complicated, because there 4 ways to pick 3 blue discs in 4 turns, i.e
Blue Blue Blue Red
Blue Blue Red Blue
Blue Red Blue Blue
Red Blue Blue Blue
And because for each turn we put an extra red disc into the bag, the probability of picking disc at attempt n will be different from picking disc at attempt n±1, hence we need to calculate probabilities for each variation separately.
After we calculated probabilities for 3 blue discs we end up with 10/120. Adding up probability of picking 4 blue discs, we have:
10/120 + 1/120 = 11/120
And to find the maximum prize fund, we divide 1 by 11/120:
1/(11/120) = 120/11 ~ 10.9
And take floor of that value:
floor(10.9) = 10. Which tallies with the Euler's answer.
The code is following:
import math from itertools import combinations import time start = time.time() def _121_(N): #N - number of turns TOTAL_PROBABILITY = 0 #Calclulate min number of blue discs you need to pick in order to win the game if N % 2 == 1: minimum_picks = int(math.ceil(N/2)) else: minimum_picks = int((N/2) +1) #Calculate probabilities for picking blue or red disc at nth attempt blue = [1/x for x in range(2,N+2)] red = [1-x for x in blue] #Calculate probabilities of all variations indeces_chain = set(range(N)) for V in range(minimum_picks,N+1): blue_indeces = list(combinations(indeces_chain,V)) for M in blue_indeces: cumul = 1 for blue_prob in M: cumul*= blue[blue_prob] for red_prob in indeces_chain.difference(set(M)): cumul*=red[red_prob] TOTAL_PROBABILITY+=cumul return TOTAL_PROBABILITY print(math.floor(1/(_121_(15)))) print(time.time() - start)
I suppose there are a lot of things that may be improved. Hence I'm glad to hear any suggestions/remarks. Thanks!
P.S I believe the part of the code after "#Calculate probabilities of all variations" is the most confusing. Because the post is already lengthy, I decided not to elaborate on that part. However, if you think that I must explain that too, I will edit my post to do so.