Project Euler 121: Investigate the game of chance involving colored discs

Problem Description

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.

Analysis

This problem, a series of independent events, can be solved by an ordinary generating function for the numerators of the respective probabilities. The nth coefficients of (x+1)(x+2)(x+3)…(x+15) are the sum of the products taken n at a time. We are only concerned with a winning scenario, which, for this problem, would be selecting 8 or more blue disks. Therefore, only the top eight coefficients are required.

What’s left is to take the reciprocal of the sum of the eight coefficients divided by (n+1)!.

Example: for n=7, the equation is (x+1)(x+2)(x+3)(x+4)(x+5)(x+6)(x+7) because we keep adding a red disk after each turn leaving 1 blue disk and 7 red disks for a total of 8 disks by the end of the game. This equation expands to:
x⁷ + 28x⁶ + 322x⁵ + 1960x⁴ + 6769x³ + 13132x² + 13068x + 5040.
A winning scenario is selecting the blue disk 4 or more times (7 times out of 7 tries, 6 out of 7, 5 out of 7 or 4 out of 7) with the respective sum of the coefficients 1 + 28 + 322 + 1960 = 2311. The probability of winning is 2311/8! = 2311/40320. The prize fund would have to be the reciprocal of the winning probability, 40320/2311 ≈ £17.

Project Euler 121 Solution

Afterthoughts

• for n=100 the value (34316…) is calculated less than 1 second.