Project Euler 121 - Disc Game Prize Fund

Official link: https://projecteuler.net/problem=121

Thought Process

For problems like this I always try to map out the base case:

Bag at Round 1 [R, B] = 1/2Bag at Round 2 [R, B, R] = 1/3Bag at Round 3 [R, B, R, R] = 1/4Bag at Round 4 [R, B, R, R, R] = 1/5

From this the probability that a player wins is the probability that the player gets 3 or 4 blue discs

4 blue is simple 1/2 * 1/3 * 1/4 * 1/5 = 1/120

3 blue is trickier

Scenario 1: Draw B from round 1, 2, 3 = 1/2 * 1/3 * 1/4 * 4/5 = 4/120Scenario 2: Draw B from round 1, 2, 4 = 1/2 * 1/3 * 3/4 * 1/5 = 3/120Scenario 3: Draw B from round 1, 3, 4 = 1/2 * 2/3 * 1/4 * 1/5 = 2/120Scenario 4: Draw B from round 2, 3, 4 = 1/2 * 1/3 * 1/4 * 4/5 = 1/120

Total = 11/120

Now we can generalise this lets consider a tree, let P(xA) = probability of getting x number of A colour discs, for example P(1B) = probability of getting 1 blue disc and let Pcr(A) = probability of getting A colour disc from current row

Row 1 [P(1B), P(1R)] = [1/2, 1/2]

Row 2 [P(2B), P(1B + 1R), P(2R)] = [P(1B) * Pcr(B), (P(1B) * Pcr(R)) + (P(1R) * Pcr(B)), P(1R) * Pcr(R)]

Row 4 [P(4B), P(3B + 1R), P(2B + 2R), P(3R + 1B), P(4R)]

The solution is P(4B) + P(3B + 1R) = 11/120

So given n turns we are looking for the sum of the of the floor(n/2) entries of the last row, and then we take the inverse.

I used dynamic programming to solve this problem, using a very similar algorithm I used in Problem 67

Interactive Code

Input an integer (yourinput)

Code will output the maximum prize fund that should be allocated to a single game in which yourinput turns are played