Problem 151: Paper Sheets of Standard Sizes: An Expected-Value Problem

Project Euler Problem 151 Solution

EulerSolve provides an optimized solution for Project Euler Problem 151, Paper Sheets of Standard Sizes: An Expected-Value Problem, with C++, Python, Java, and a step-by-step mathematical explanation.

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)$....

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

Problem page: Project Euler 151
ISO 216 paper sizes: Wikipedia - ISO 216
Expected value: Wikipedia - Expected value
Markov chains: Wikipedia - Markov chain
Memoization: Wikipedia - Memoization

Problem 151 source code

C++

#include <array>
#include <iomanip>
#include <iostream>
#include <string>
#include <unordered_map>

namespace {

struct Options {
    bool run_checkpoints = true;
};

using State = std::array<int, 4>;  // A2,A3,A4,A5 counts

bool parse_arguments(int argc, char** argv, Options& options) {
    for (int i = 1; i < argc; ++i) {
        const std::string arg(argv[i]);
        if (arg == "--skip-checkpoints") {
            options.run_checkpoints = false;
            continue;
        }

        std::cerr << "Unknown argument: " << arg << '\n';
        return false;
    }

    return true;
}

int encode(const State& s) {
    return (((s[0] * 16 + s[1]) * 16 + s[2]) * 16 + s[3]);
}

double expected_single_envelopes(const State& state, std::unordered_map<int, double>& memo) {
    const int key = encode(state);
    auto it = memo.find(key);
    if (it != memo.end()) {
        return it->second;
    }

    const int total = state[0] + state[1] + state[2] + state[3];
    if (total == 0) {
        memo[key] = 0.0;
        return 0.0;
    }

    double ans = 0.0;

    // Count single-sheet states except the terminal single A5 case.
    if (total == 1 && state[3] == 0) {
        ans += 1.0;
    }

    for (int i = 0; i < 4; ++i) {
        if (state[static_cast<std::size_t>(i)] == 0) {
            continue;
        }

        State next = state;
        --next[static_cast<std::size_t>(i)];
        for (int j = i + 1; j < 4; ++j) {
            ++next[static_cast<std::size_t>(j)];
        }

        const double probability = static_cast<double>(state[static_cast<std::size_t>(i)]) /
                                   static_cast<double>(total);
        ans += probability * expected_single_envelopes(next, memo);
    }

    memo[key] = ans;
    return ans;
}

double solve() {
    std::unordered_map<int, double> memo;
    const State start = {1, 1, 1, 1};
    return expected_single_envelopes(start, memo);
}

bool run_checkpoints() {
    std::unordered_map<int, double> memo;
    const State single_a4 = {0, 0, 1, 0};
    const double value = expected_single_envelopes(single_a4, memo);
    if (std::abs(value - 1.0) > 1e-12) {
        std::cerr << "Checkpoint failed for single A4 state" << '\n';
        return false;
    }

    return true;
}

}  // namespace

int main(int argc, char** argv) {
    Options options;
    if (!parse_arguments(argc, argv, options)) {
        return 1;
    }
    if (options.run_checkpoints && !run_checkpoints()) {
        return 2;
    }

    std::cout << std::fixed << std::setprecision(6) << solve() << '\n';
    return 0;
}

Python

# Problem 151: Paper sheets of standard sizes (expected single-sheet picks)

def solve():
    memo = {}
    def dfs(state):
        key = state
        if key in memo: return memo[key]
        total = sum(state)
        if total == 0:
            memo[key] = 0.0
            return 0.0
        ans = 0.0
        # Count single-sheet states (but not the final A5 if it's the only one)
        if total == 1 and state[3] == 0:
            ans += 1.0
        for i in range(4):
            if state[i] == 0: continue
            prob = state[i] / total
            nxt = list(state)
            nxt[i] -= 1
            for j in range(i+1, 4):
                nxt[j] += 1
            ans += prob * dfs(tuple(nxt))
        memo[key] = ans
        return ans
    result = dfs((1, 1, 1, 1))
    print(f"{result:.6f}")

solve()

Java

import java.util.*;

public class Euler151 {
    static Map<Long, Double> memo = new HashMap<>();

    static double dfs(int a2, int a3, int a4, int a5) {
        long key = ((long) a2 << 24) | ((long) a3 << 16) | ((long) a4 << 8) | a5;
        if (memo.containsKey(key))
            return memo.get(key);
        int total = a2 + a3 + a4 + a5;
        if (total == 0) {
            memo.put(key, 0.0);
            return 0.0;
        }
        double ans = 0;
        if (total == 1 && a5 == 0)
            ans += 1.0;
        int[] s = { a2, a3, a4, a5 };
        for (int i = 0; i < 4; i++) {
            if (s[i] == 0)
                continue;
            double prob = (double) s[i] / total;
            int[] n = s.clone();
            n[i]--;
            for (int j = i + 1; j < 4; j++)
                n[j]++;
            ans += prob * dfs(n[0], n[1], n[2], n[3]);
        }
        memo.put(key, ans);
        return ans;
    }

    public static void main(String[] args) {
        System.out.printf("%.6f%n", dfs(1, 1, 1, 1));
    }
}