Project Euler: Disc Game Prize Fund

Project Euler

Project Euler is a set of challenging problems that often require more than just mathematical rules to solve.

Problem statement

A bag contains one red disc and one blue disc. In a game of chance, a player takes a disc at random and notes its color. 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, 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.

Source of the problem: http://www.javaproblems.com/2013/12/project-euler-problem-121-disc-game.html

Solution

We know that for a single turn, we have 22 outcomes (22). For 2 turns, we have 66 outcomes (33). We can generalize it so that for nn turns, we have (n+1)(n+1) outcomes.

In the following graphs, the red lines represent picking red discs and the blue lines represent picking blue discs.

If we pick blue first, then there is a chance that we can draw another blue. In this scenario, we can draw 2 blues. Similarly, if we take red after picking the blue disc, we have 2 scenarios (out of three) from which we can pick red. Similarly, if we go on and start adding layers, we get the situation explained in the following graph.

For 4 turns:

using System;
using System.Diagnostics;
namespace Problem {
    class P {
        public static void Main(string[] args) {
            new P().Bruteforce();
        }
  
        public void Bruteforce() {
            // taking limit 15 because we are writing code for 15 turns
            int lim = 15;
            // creating a long array which will sotre the positive outcomes count
            long[] result = new long[lim+1];
            result[lim] = 1;
            result[lim-1] = 1;
                        
            for (int i = 2; i <= lim; i++) {
                for(int j = 0; j < result.Length-1; j++){
                    result[j] = result[j + 1];                    
                }
                result[lim] = 0;
                
                for (int j = result.Length-1; j > 0; j--) {
                    result[j] += result[j - 1] * i;
                }
            }
            // the results array gets all the positive outcomes and in the next 
            // step we are adding all the elements of results array
         
            long pos = 0;
            for (int i = 0; i < lim / 2+1; i++) {
                pos =pos + result[i];
            }
            // this is the code to find the total number of outcomes
            long tot = 1;
            for (int i = 2; i < lim + 2; i++) {
                tot *= i;
            }
            Console.WriteLine("prize allocation: {0}", tot/pos);
            
        }
    }
}

The code above gives the prize allocation of 2269.

Free Resources

License: Creative Commons-Attribution-ShareAlike 4.0 (CC-BY-SA 4.0)