Detailed mathematical approach

Problem Summary

The weekly process begins with a single \(A1\) sheet, but after the first cut-and-use operation the envelope already contains exactly one sheet of each size \(A2,A3,A4,A5\). That is why the implementations start from the state \(s_0=(1,1,1,1)\): from that point onward, every job consists of drawing one sheet uniformly from the envelope, cutting it down if necessary, using one \(A5\), and returning the leftover smaller sheets.

The goal is to find the expected number of later occasions on which the envelope contains exactly one sheet. The state with a lone \(A5\) is excluded from the count, because it is the terminal last-job situation rather than an additional nontrivial single-sheet event.

Mathematical Approach

This is an exact finite-state expectation problem. Once the right state variables are chosen, the whole solution is a short Markov-style recurrence evaluated with memoization.

State Space After the First Job

Let

$s=(a_2,a_3,a_4,a_5),\qquad T(s)=a_2+a_3+a_4+a_5,$

where \(a_k\) is the number of \(A_k\)-sheets currently in the envelope. Only the sizes \(A2,A3,A4,A5\) can appear after the first job, so these four integers describe the process completely. The starting state is

$s_0=(1,1,1,1).$

The random choice at each step is uniform over sheets, not over sizes, so the probability of drawing size \(A_k\) is \(a_k/T(s)\).

The Exact Transition Law

If a chosen sheet is larger than \(A5\), it is halved repeatedly until one \(A5\) is used. The leftovers are precisely one copy of every intermediate smaller size. Therefore the four possible successors are

$\begin{aligned} s^{(2)}&=(a_2-1,\ a_3+1,\ a_4+1,\ a_5+1),\\ s^{(3)}&=(a_2,\ a_3-1,\ a_4+1,\ a_5+1),\\ s^{(4)}&=(a_2,\ a_3,\ a_4-1,\ a_5+1),\\ s^{(5)}&=(a_2,\ a_3,\ a_4,\ a_5-1). \end{aligned}$

These formulas are exactly what the implementations build when they remove one selected sheet and then add back all smaller leftovers created by the cutting chain.

A Useful Invariant: Remaining Area in \(A5\)-Units

A convenient way to see that the recursion must terminate is to measure the remaining paper in \(A5\)-equivalents:

$W(s)=8a_2+4a_3+2a_4+a_5.$

One \(A2\) contains the area of eight \(A5\) sheets, one \(A3\) contains four, and one \(A4\) contains two. Under any transition above, exactly one \(A5\)-worth of paper is consumed, so

$W\!\left(s^{(k)}\right)=W(s)-1\qquad\text{for every available }k\in\{2,3,4,5\}.$

Starting from \(s_0=(1,1,1,1)\), we have \(W(s_0)=15\). Hence the process can never cycle: every step moves to a strictly smaller value of \(W\), and after 15 jobs the envelope is empty. This turns the state graph into a small directed acyclic graph.

The Expected-Value Recurrence

Let \(E(s)\) be the expected number of future single-sheet occasions starting from state \(s\). The only single-sheet states that count are

$(1,0,0,0),\qquad(0,1,0,0),\qquad(0,0,1,0),$

because the terminal state \((0,0,0,1)\) must be excluded. Define the indicator

$I(s)=\begin{cases} 1, & T(s)=1\text{ and }a_5=0,\\ 0, & \text{otherwise.} \end{cases}$

Then the empty-envelope base case is

$E(0,0,0,0)=0,$

and for every nonempty state, the law of total expectation gives

$E(s)=I(s)+\sum_{k=2}^{5}\frac{a_k}{T(s)}\,E\!\left(s^{(k)}\right),$

where terms with \(a_k=0\) are simply absent. This formula already solves the problem: the desired answer is \(E(1,1,1,1)\).

Worked Examples

Take the state \(s=(0,0,1,0)\), meaning that the envelope contains only one \(A4\). This state counts once immediately, and the only possible next state is \((0,0,0,1)\). Therefore

$E(0,0,1,0)=1+E(0,0,0,1)=1.$

The initial state illustrates the probabilistic branching. Since \(T(1,1,1,1)=4\), each size is chosen with probability \(1/4\), so

$E(1,1,1,1)=\frac14E(0,2,2,2)+\frac14E(1,0,2,2)+\frac14E(1,1,0,2)+\frac14E(1,1,1,0).$

Every later expectation is obtained by repeating exactly the same recurrence on smaller states.

Why Memoization Is Enough

Because \(W(s)\) decreases by 1 at every step, \(E(s)\) only depends on states with smaller \(W\). There is no need for simulation, sampling, or solving a large linear system. Caching the value of each reached state once is sufficient to evaluate the entire recurrence exactly up to floating-point output formatting.

How the Code Works

State Encoding and Caching

The C++, Python, and Java implementations all store the four sheet counts as the complete state description and cache already computed expectations in a hash table. The C++ and Java versions pack the four counts into an integer-style key, while the Python version uses the tuple itself as the key, but mathematically they memoize the same function \(E(s)\).

Recursive Evaluation

For each state, the implementation first computes the total number of sheets \(T(s)\). If the envelope is empty, it returns 0. Otherwise it adds 1 exactly when the state is a counted single-sheet state, then loops over the available sizes, constructs the corresponding successor state, multiplies the recursive value by the probability \(a_k/T(s)\), and accumulates the result. Finally it starts from \((1,1,1,1)\) and prints the expectation rounded to six decimal places.

Complexity Analysis

Let \(S\) be the number of reachable states from \((1,1,1,1)\). Each state examines at most four outgoing transitions, so the running time is \(O(S)\) and the memory usage is also \(O(S)\).

For this problem \(S\) is tiny, because every state satisfies \(W(s)\le 15\) and every move decreases \(W\) by 1. The recursion depth is therefore at most 15, and the memo table remains small. The algorithm is fast because it replaces an exponentially branching random process by one evaluation of a compact acyclic state graph.

Footnotes and References

1. Problem page: Project Euler 151
2. ISO 216 paper sizes: Wikipedia - ISO 216
3. Expected value: Wikipedia - Expected value
4. Markov chains: Wikipedia - Markov chain
5. Memoization: Wikipedia - Memoization