Problem 151: Paper Sheets of Standard Sizes

Mathematical Development

Definition 1. A state is a tuple $\mathbf{s} = (a_2, a_3, a_4, a_5) \in \mathbb{Z}_{\ge 0}^4$, where $a_k$ denotes the number of A$k$ sheets in the envelope for $k \in \{2,3,4,5\}$. The A1 sheet is omitted because it is consumed in the first (excluded) batch.

Lemma 1 (State Transition Rules). When an A$k$ sheet ($k \in \{2,3,4,5\}$) is selected from the envelope, the state transition is:

• $k = 5$: $a_5 \mapsto a_5 - 1$; all other components unchanged.
• $k = 4$: $a_4 \mapsto a_4 - 1,\; a_5 \mapsto a_5 + 1$.
• $k = 3$: $a_3 \mapsto a_3 - 1,\; a_4 \mapsto a_4 + 1,\; a_5 \mapsto a_5 + 1$.
• $k = 2$: $a_2 \mapsto a_2 - 1,\; a_3 \mapsto a_3 + 1,\; a_4 \mapsto a_4 + 1,\; a_5 \mapsto a_5 + 1$.

Proof. An A$k$ sheet with $k < 5$ is cut by successive halving into sheets A$(k{+}1)$, A$(k{+}2)$, …, A$5$, A$5$. The final halving of an A$4$ produces two A$5$ sheets, so the cut of A$k$ yields one sheet of each size from A$(k{+}1)$ through A$4$, plus two A$5$ sheets. One A$5$ is consumed for the batch. The net effect is: remove one A$k$, add one each of A$(k{+}1)$, …, A$5$. For $k = 5$, the sheet is consumed outright. $\square$

Lemma 2 (Initial State). The state after the first batch (which deterministically consumes the lone A1 sheet) is $(1, 1, 1, 1)$.

Proof. Cutting A1 yields one each of A2, A3, A4, and two copies of A5. One A5 is consumed, leaving counts $(1, 1, 1, 1)$. $\square$

Lemma 3 (Finiteness of the State Space). The reachable state space satisfies $a_2 \le 1$, $a_3 \le 2$, $a_4 \le 4$, $a_5 \le 8$, subject to the invariant $8a_2 + 4a_3 + 2a_4 + a_5 \le 15$. In particular, the number of reachable states $|\mathcal{S}|$ is at most $2 \times 3 \times 5 \times 9 = 270$.

Proof. Define the A5-equivalent count $W(\mathbf{s}) = 8a_2 + 4a_3 + 2a_4 + a_5$, reflecting that each A$k$ sheet can be decomposed into $2^{5-k}$ sheets of A5. The initial state has $W = 8 + 4 + 2 + 1 = 15$. Each batch consumes exactly one A5-equivalent unit (one A5 is used), so $W$ decreases by 1 per batch. No transition creates additional A5-equivalent mass: when an A$k$ sheet ($k < 5$) is cut and one A5 consumed, the net change is $-2^{5-k} + (2^{5-(k+1)} + \cdots + 2^0 + 2^0) - 1 = 0 - 1 = -1$. Since no A2 is ever created (only removed), $a_2 \le 1$. Similarly, $a_3 \le 1 + a_2 \le 2$, $a_4 \le 1 + a_2 + a_3 \le 4$, and $a_5 \le 1 + a_2 + a_3 + a_4 \le 8$. $\square$

Theorem 1 (Expectation Recursion). Define $E(\mathbf{s})$ as the expected number of single-sheet encounters from state $\mathbf{s}$ onward, excluding the terminal batch. Let $T(\mathbf{s}) = a_2 + a_3 + a_4 + a_5$ be the total sheet count. Then $E(\mathbf{0}) = 0$ and for $\mathbf{s} \neq \mathbf{0}$:

where $\mathbf{s}_k$ denotes the state obtained by selecting an A$k$ sheet from state $\mathbf{s}$ (as defined in Lemma 1).

Proof. The process is a finite-state Markov chain on $\mathcal{S}$ with absorbing state $\mathbf{0}$. At each non-terminal state $\mathbf{s}$, the worker observes a single sheet if and only if $T(\mathbf{s}) = 1$. The problem excludes the first batch (state $(1,1,1,1)$, where $T = 4$) and the last batch. The last batch occurs at state $(0,0,0,1)$, which is the unique pre-terminal state; it transitions to $\mathbf{0}$ with certainty. We exclude this state from the single-sheet count by the indicator condition $\mathbf{s} \neq (0,0,0,1)$.

Each sheet of size $k$ is selected with probability $a_k / T(\mathbf{s})$ (uniform random draw). After selection, the state transitions to $\mathbf{s}_k$ and the process continues. By the tower property of conditional expectation:

The recursion terminates at $\mathbf{0}$ since no further batches occur. Since $W$ strictly decreases, there are no cycles, ensuring the recursion is well-founded. $\square$

Corollary. The answer to the problem is $E(1,1,1,1)$.

Editorial

We single-sheet indicator (exclude terminal state). Finally, recurse over each possible selection. We use dynamic programming over the state space implied by the derivation, apply each admissible transition, and read the answer from the final table entry.

Pseudocode

Single-sheet indicator (exclude terminal state)
Recurse over each possible selection

Complexity Analysis

• Time: $O(|\mathcal{S}|)$ where $|\mathcal{S}| \le 270$ is the number of reachable states. Each state is visited once (via memoization) and requires $O(1)$ work (at most 4 recursive lookups and arithmetic operations). Total: $O(270) = O(1)$.
• Space: $O(|\mathcal{S}|) = O(1)$ for the memoization table.

Answer

#include <bits/stdc++.h>
using namespace std;

map<tuple<int,int,int,int>, double> memo;

double E(int a2, int a3, int a4, int a5) {
    if (a2 == 0 && a3 == 0 && a4 == 0 && a5 == 0)
        return 0.0;
    auto key = make_tuple(a2, a3, a4, a5);
    auto it = memo.find(key);
    if (it != memo.end()) return it->second;

    int T = a2 + a3 + a4 + a5;
    double result = 0.0;

    // Single-sheet indicator, excluding terminal state (0,0,0,1)
    if (T == 1 && !(a2 == 0 && a3 == 0 && a4 == 0 && a5 == 1))
        result = 1.0;

    if (a2 > 0)
        result += (double)a2 / T * E(a2 - 1, a3 + 1, a4 + 1, a5 + 1);
    if (a3 > 0)
        result += (double)a3 / T * E(a2, a3 - 1, a4 + 1, a5 + 1);
    if (a4 > 0)
        result += (double)a4 / T * E(a2, a3, a4 - 1, a5 + 1);
    if (a5 > 0)
        result += (double)a5 / T * E(a2, a3, a4, a5 - 1);

    memo[key] = result;
    return result;
}

int main() {
    printf("%.6f\n", E(1, 1, 1, 1));
    return 0;
}

from functools import lru_cache

@lru_cache(maxsize=None)
def E(a2, a3, a4, a5):
    """Expected single-sheet encounters from state (a2,a3,a4,a5) onward,
    excluding the terminal pick at (0,0,0,1)."""
    if a2 == 0 and a3 == 0 and a4 == 0 and a5 == 0:
        return 0.0
    T = a2 + a3 + a4 + a5
    result = 0.0
    if T == 1 and not (a2 == 0 and a3 == 0 and a4 == 0 and a5 == 1):
        result = 1.0
    if a2 > 0:
        result += (a2 / T) * E(a2 - 1, a3 + 1, a4 + 1, a5 + 1)
    if a3 > 0:
        result += (a3 / T) * E(a2, a3 - 1, a4 + 1, a5 + 1)
    if a4 > 0:
        result += (a4 / T) * E(a2, a3, a4 - 1, a5 + 1)
    if a5 > 0:
        result += (a5 / T) * E(a2, a3, a4, a5 - 1)
    return result

print(f"{E(1, 1, 1, 1):.6f}")