Project Euler 151 - Paper sheets of standard sizes: an expected value problem

Official link:

Thought Process

My first thought process was to build a Monte Carlo Simulation which I did, but it took me about 15 mins to get the correct answer and it was quite lucky, I will include my code below so that you can see it.

The smarter way is to build up the probabilities of each scenario

Begin with [1,1,1,1] where the numbers represent the amount of A2, A3, A4, A5 papers respectively

After the first iteration, we are left with 4 possibilities: [0,2,2,2], [1,0,2,2], [1,1,0,2], or [1,1,1,0] each with a probability of 0.25

Now lets take an example from the next iteration [0,1,3,3], we can either:

(1) take an A3 from [0,2,2,2], this is a 1/4 * 2/6 chance

(2) take an A2 from [1,0,2,2], this is a 1/4 * 1/5 chance

So the total is (1/3+1/5)/4 = 0.1333

Like this we can build the probability for every scenario, and of course the scenarios we are interested in are [0,1,0,0], [0,0,1,0], and [0,0,0,1]

You can program this using a Stack

Interactive Code

Enter the number of A2, A3, A4, A5 papers

Code will output the probability of the scenario occuring