Statement

A printing shop runs 16 batches (jobs) every week and each batch requires a sheet of special colour-proofing paper of size A5.

Every Monday morning, the foreman opens a new envelope, containing a large sheet of the special paper with size A1.

He proceeds to cut it in half, thus getting two sheets of size A2. Then he cuts one of them in half to get two sheets of size A3 and so on until he obtains the A5-size sheet needed for the first batch of the week.

All the unused sheets are placed back in the envelope.

At the beginning of each subsequent batch, he takes from the envelope one sheet of paper at random. If it is of size A5, he uses it. If it is larger, he repeats the 'cut-in-half' procedure until he has what he needs and any remaining sheets are always placed back in the envelope.

Excluding the first and last batch of the week, find the expected number of times (during each week) that the foreman finds a single sheet of paper in the envelope.

Give your answer rounded to six decimal places using the format x.xxxxxx .

Solution

In order to solve this problem I used a DP solution, using a top-down model with memorization.

The first thing to do when designing any DP solution is to find the base-case, in this problem the base case is when there's just one sheet remaining and it's an A5. The expected number of times to find a single page in the envelope for this case is 0, as the problem states.

For the other non-base cases the result of it consists of 1 or 0, depending if there's one sheet in the envelope or not, and the sum of the expected number of times of the possible sub-cases multiplied by the probability of each sub-case (1 / number of sheets).

Then we launch the algorithm for the starting envelope (A2, A3, A4, A5) and not (A1), because this case doesn't count either.

Using the previous description I wrote a program in python to do that:

from decimal import *
 
d = {
    (5,) : Decimal(0)
}
 
def solve(curr_size):
    if curr_size in d:
        return d[curr_size]
 
    result = Decimal(0)
 
    if len(curr_size) == 1:
        result += Decimal(1)
 
    p = Decimal(1) / Decimal(len(curr_size))
    for i in curr_size:
        tmp_curr = list(curr_size)
        tmp_curr.remove(i)
        while (i < 5):
            tmp_curr.append(i + 1)
            i += 1
        tmp_curr = tuple(sorted(tmp_curr))
        result += p * solve(tmp_curr)
 
    d[curr_size] = result
    return result
 
if __name__ == '__main__':
    result = solve((2,3,4,5))
    getcontext().prec = 6
    result = +result
    print("The result is:", result)

The Python file is available for download here.