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

Detailed mathematical approach

Problem Summary

A printing shop runs \(16\) batches every week, and each batch needs one A5 sheet of special colour-proofing paper. On Monday the supervisor opens a new envelope that holds one A1 sheet, cuts it in half, cuts one of the two A2 halves in half again, and so on, until an A5 sheet is obtained for the first batch; the unused sheets go back into the envelope. At the start of every later batch the supervisor takes one sheet from the envelope at random, every sheet being equally likely. An A5 sheet is used as it is; a larger one is halved repeatedly until an A5 sheet is obtained, and the other pieces go back. We must find the expected number of times per week that the supervisor finds a single sheet in the envelope, excluding the first and the last batch, rounded to six decimal places. ^[1] The statement gives no intermediate values; Section 6 supplies a small check.

The whole solution in one sentence: after the first batch the envelope holds one sheet of each size from A2 to A5, so its content is just four small numbers, and a recurrence that averages over the next random sheet, evaluated once for each of the \(85\) contents that can occur, gives the expected number of single-sheet moments without any simulation.

Mathematical Approach

Two observations make the random week small: cutting a sheet down to A5 leaves one sheet of each smaller size, and every batch uses up exactly one A5 sheet of paper.

1. What cutting down to A5 leaves behind

Halving a sheet parallel to its shorter sides gives two sheets of the next size, as in the ISO 216 standard. ^[2] Take an A3 sheet: it gives two A4 sheets, one goes back and the other is cut into two A5 sheets, one used and one returned, so one A4 and one A5 sheet remain. In the same way a sheet of size \(\mathrm Ak\) with \(k\le4\) leaves exactly one sheet of each size from \(\mathrm A(k+1)\) to A5, because every cut returns one half and goes on with the other, until that half is the A5 sheet to be used; an A5 sheet leaves nothing. After the first batch the envelope therefore holds one A2, one A3, one A4 and one A5 sheet.

2. Counting paper in A5 sheets

Measure paper in A5 sheets: an A4 sheet is worth \(2\), an A3 sheet \(4\), an A2 sheet \(8\) and the A1 sheet \(16\). An envelope with \(a_k\) sheets of size \(\mathrm Ak\) for \(k=2,\dots,5\) is worth

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

A sheet worth \(2^j\) leaves pieces worth \(2^{j-1}+\dots+2+1=2^j-1\), so every batch removes exactly the one unit it uses. After the first batch \(W=15\), so at the start of batch \(b\ge2\)

$$W=17-b.$$

At the start of batch \(16\) a single A5 sheet is left, and after it the envelope is empty. The first and the last batch therefore always find a single sheet, and the statement leaves out these two certain moments.

3. The only batches that can count

A single sheet is worth \(8\), \(4\), \(2\) or \(1\), so by Section 2 it can only be found at the start of batch \(9\) (a single A2), batch \(13\) (a single A3), batch \(15\) (a single A4) or batch \(16\) (the excluded A5). Only one A2 sheet ever enters the envelope, so the moment at batch \(9\) happens exactly when that A2 sheet is not taken in batches \(2\) to \(8\).

4. Adding up three chances

Let \(X\) be the number of counted single-sheet moments in a week, and let \(J_b\) be \(1\) if the envelope holds a single sheet at the start of batch \(b\) and \(0\) otherwise. By Section 3, \(X=J_9+J_{13}+J_{15}\). The expected value of such an indicator is the probability of its event, and the expected value of a sum is the sum of the expected values, ^[3] so

$$\mathbb E[X]=p_9+p_{13}+p_{15},$$

where \(p_b\) is the probability of a single sheet at the start of batch \(b\). Linearity of expectation does not need the events to be independent; Section 6 shows a dependent pair in a smaller week.

5. The envelope as a state

Write the content at the start of a batch as \(s=(a_2,a_3,a_4,a_5)\), with \(T(s)=a_2+a_3+a_4+a_5\) sheets and worth \(W(s)\); the batch number need not be stored, as it is \(17-W(s)\). Every sheet is equally likely, so a sheet of size \(\mathrm Ak\) is taken with probability \(a_k/T(s)\), and by Section 1 the content then becomes

$$\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}$$

where \(s^{(k)}\) is possible only when \(a_k\ge1\). The next content depends only on the present one and on the random sheet, so the contents form a Markov chain. ^[4] Since \(W\) drops by one at every step, no content appears twice in a week, and the moves form a directed graph without cycles. The chances belong to sheets, not to sizes: choosing uniformly among the sizes present would give \(11/24\) instead of \(5/9\) in the small week of Section 6.

6. A smaller week by hand

Take a week of \(8\) batches that starts with one A2 sheet. After the first batch the envelope holds \((0,1,1,1)\), the A2 count staying \(0\), and at the start of batch \(b\) it is worth \(9-b\), so a single sheet can be found at batch \(5\) (an A3) and at batch \(7\) (an A4), while the lone A5 at batch \(8\) is excluded. Following the moves of Section 5 batch by batch gives the probabilities of the contents:

• batch \(2\): \((0,1,1,1)\) with probability \(1\);
• batch \(3\): \((0,0,2,2)\), \((0,1,0,2)\) and \((0,1,1,0)\), each with probability \(1/3\);
• batch \(4\): \((0,0,1,3)\) with \(5/18\), \((0,0,2,1)\) with \(1/3\), \((0,1,0,1)\) with \(7/18\);
• batch \(5\): \((0,0,0,4)\) with \(5/72\), \((0,0,1,2)\) with \(5/8\), \((0,0,2,0)\) with \(1/9\), \((0,1,0,0)\) with \(7/36\);
• batch \(6\): \((0,0,0,3)\) with \(5/18\), \((0,0,1,1)\) with \(13/18\);
• batch \(7\): \((0,0,0,2)\) with \(23/36\), \((0,0,1,0)\) with \(13/36\);
• batch \(8\): \((0,0,0,1)\) with probability \(1\).

Each entry adds the contributions of the contents that lead to it. For example, \((0,1,0,1)\) at batch \(4\) comes from \((0,1,0,2)\) when one of its two A5 sheets is taken and from \((0,1,1,0)\) when its A4 sheet is taken, so its probability is

$$\tfrac13\cdot\tfrac23+\tfrac13\cdot\tfrac12=\tfrac{7}{18}.$$

The value \(7/36\) at batch \(5\) can also be checked directly: the A3 sheet survives batches \(2\) to \(4\) when the sizes taken are A4, A5, A5 or A5, A4, A5, which have the probabilities

$$\tfrac13\cdot\tfrac23\cdot\tfrac12=\tfrac19,\qquad \tfrac13\cdot\tfrac12\cdot\tfrac12=\tfrac1{12},$$

together \(\tfrac19+\tfrac1{12}=\tfrac7{36}\). Hence the small week has

$$\mathbb E[X]=\frac{7}{36}+\frac{13}{36}=\frac59.$$

The two events are dependent: a single A3 sheet at batch \(5\) leaves \((0,0,1,1)\) at batch \(6\), and the A4 sheet is then alone at batch \(7\) with probability \(1/2\), so both occur with probability \(7/72\), not \(\frac{7}{36}\cdot\frac{13}{36}\). Still, their probabilities simply add.

7. The recurrence used by the programs

The programs compute the expectation backwards. Let \(E(s)\) be the expected number of counted moments from the current batch to the end of the week when the envelope holds \(s\) at the start of that batch. Let \(I(s)\) be \(1\) if \(s\) is a single A2, A3 or A4 sheet, that is \(T(s)=1\) and \(a_5=0\), and \(0\) otherwise. Then \(E(0,0,0,0)=0\), and for every other content

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

summing over the sizes with \(a_k\ge1\). Proof: the current moment contributes \(I(s)\); a sheet of size \(\mathrm Ak\) is taken with probability \(a_k/T(s)\), and by the Markov property the rest of the week then behaves like a week that starts from \(s^{(k)}\), so the law of total expectation ^[5] gives the sum. As \(W\) drops by one per step, induction on \(W(s)\) shows that the recurrence determines \(E\). The lone A5 sheet occurs only at batch \(16\), and the recursion starts after the first batch, at \(s_0=(1,1,1,1)\), so \(E(s_0)\) is the requested value.

In the small week, every content made only of A5 sheets has \(E=0\), and \(E(0,0,1,0)=1\), since a single A4 sheet counts once and leaves a lone A5 sheet. Then

$$\begin{aligned} E(0,0,1,1)&=\tfrac12E(0,0,0,2)+\tfrac12E(0,0,1,0)=\tfrac12,\\ E(0,1,0,0)&=1+E(0,0,1,1)=\tfrac32, \end{aligned}$$

and so on, up to

$$E(0,1,1,1)=\tfrac13\Bigl(\tfrac{23}{72}+\tfrac{25}{36}+\tfrac{47}{72}\Bigr)=\tfrac59,$$

where the bracket holds the values of \(E\) at the three contents of batch \(3\). Both directions evaluate the same sum over all weeks. In the language of absorbing Markov chains, \(E(s_0)\) adds three entries of the fundamental matrix, the expected numbers of visits to the single-sheet contents, ^[6] which equal \(p_9\), \(p_{13}\) and \(p_{15}\) because no content is visited twice.

8. Each content is evaluated once

Different orders of taking sheets often lead to the same content: from \((1,1,1,1)\), taking the A3 sheet and then an A5 sheet, or the other way round, gives \((1,0,2,1)\). A plain recursion would follow each of the \(40040\) possible sequences of sizes separately and make \(191169\) calls. Memoization, storing every value the first time it is computed, ^[7] avoids this: only \(85\) nonempty contents can occur, between \(1\) and \(11\) at each batch, with \(181\) moves between them and one last move to the empty envelope, so one evaluation from \((1,1,1,1)\) makes \(183\) calls and stores \(86\) values, the empty envelope included. Its depth is at most \(16\) calls.

9. Rounding to six decimals

Double-precision numbers carry \(15\) to \(17\) significant decimal digits. ^[8] Every \(E(s)\) is at most \(3\) and results from a few hundred operations on nonnegative numbers, with no cancelling subtraction, so the rounding error is tiny. Since even a tiny error could flip the sixth decimal next to a rounding midpoint, we also compared with exact fractions: they differ from the floating-point result by about \(10^{-17}\) and round to the same six decimals.

How the Code Works

The C++ program ^[9] stores a content as a State, a std::array<int, 4> with the counts of A2, A3, A4 and A5 sheets, and encode packs it into the key

$$((a_2\cdot16+a_3)\cdot16+a_4)\cdot16+a_5,$$

the counts written as digits in base \(16\); this is one-to-one because the counts never exceed \(1\), \(2\), \(4\) and \(8\). expected_single_envelopes implements Section 7 with an std::unordered_map<int, double> as the memo. After the memo lookup it computes total \(=T(s)\), returns \(0\) for the empty envelope and adds \(1\) when total == 1 and state[3] == 0, the indicator \(I(s)\). For each index i with a nonzero count it builds next as in Section 5, removing one sheet of that size and adding one of every smaller size, and adds the probability state[i] / total, computed in double, times the value of next to ans, which is stored before it is returned. solve starts at \((1,1,1,1)\).

main calls parse_arguments, which accepts only --skip-checkpoints and gives exit code \(1\) for any other argument. Unless that option is given, run_checkpoints requires the value \(1\), up to \(10^{-12}\), for the single A4 sheet \((0,0,1,0)\) of Section 7; on failure the exit code is \(2\). The result is printed with std::fixed and std::setprecision(6).

The Python solve defines dfs, which uses the tuple of counts itself as the key of a dictionary, and prints with the format .6f. The Java program keeps a static HashMap<Long, Double> whose key gives each count its own byte, a2 << 24 | a3 << 16 | a4 << 8 | a5, and prints with printf("%.6f%n", …). Both follow the C++ order of sizes and additions but run no checkpoint. Java's printf formats with the default locale, so under a German or Turkish locale the Java program prints a decimal comma, while the C++ stream and Python's .6f always print a point. ^[10]

Complexity and Verification

Within one evaluation from \((1,1,1,1)\) each of the \(86\) values is computed once and each of the \(182\) moves is followed once, with constant work per call apart from hash lookups, which take constant time on average. Time and memory are therefore proportional to the number of contents, and the program finishes instantly; the C++ checkpoint adds three calls with its own memo. The number of contents grows quickly with the first sheet: with one count per smaller size, first sheets worth \(8\), \(16\), \(32\), \(64\) or \(128\) A5 sheets give \(17\), \(86\), \(698\), \(9551\) or \(226592\) contents, the empty one included.

Besides the C++ checkpoint, we verified, separately from the published programs:

• the C++ program, built with GCC 16 and with Clang 22, the Python program and the Java program print the same six decimals;
• with exact fractions, the backward recurrence, the forward computation of Section 6 applied to the real week and a sum over all \(40040\) sequences of sizes, each weighted by its probability, give the same rational number, which rounds to the printed value; the forward computation also confirms the claims of Sections 2 and 3;
• a simulation of \(10^8\) weeks that takes and cuts individual sheets agrees with the exact value within \(1.4\) standard errors of \(6.5\cdot10^{-5}\);
• a copy of the C++ program started from \((0,1,1,1)\) prints \(5/9\) rounded to six decimals, the small week of Section 6;
• for the start \((1,1,1,1)\), an instrumented copy confirmed the counts of Section 8 in solve, apart from the three checkpoint calls.

Footnotes and References

The references below supply the background facts used above; the cutting rule, the count of paper, the recurrence and the small week are derived in this article.

1. Project Euler 151 — A Preference for A5. The official statement: an A1 sheet, halved on Monday until an A5 sheet is obtained, supplies 16 weekly batches, and each later batch takes a random sheet, cutting it down to A5 if needed. It asks for the expected number of times per week, excluding the first and last batch, that the envelope holds a single sheet, rounded to six decimal places.
2. Wikipedia — ISO 216. Each size of the A series halves the area of the preceding one, and the long side of A(n + 1) equals the short side of A(n).
3. Wikipedia — Expected value. Expectation is linear, E[X + Y] = E[X] + E[Y] whenever the right-hand side is well-defined, as it is for the bounded counts used here; the expectation of an indicator is the probability of its event.
4. Wikipedia — Markov chain. In a Markov chain, given the present state, the future and the past are independent: the probability of the next step depends only on the current state.
5. Wikipedia — Law of total expectation. For a partition of the sample space into events Aᵢ, E[X] = Σ E[X | Aᵢ] P(Aᵢ); in Section 7 the events are the possible sizes of the sheet taken.
6. Wikipedia — Absorbing Markov chain. Entry (i, j) of the fundamental matrix N = (I − Q)⁻¹ is the expected number of visits to the transient state j, starting from i, before absorption.
7. Wikipedia — Memoization. The results of calls to pure functions are stored and returned quickly when the same inputs occur again.
8. Wikipedia — Double-precision floating-point format. IEEE 754 binary64 numbers have a 53-bit significand, which gives 15 to 17 significant decimal digits.
9. C++ — Euler151.cpp. The linked immutable C++ revision contains encode, expected_single_envelopes, solve and run_checkpoints. It is the implementation record for this article.
10. Output formatting: by the Java PrintStream documentation printf uses the default format locale, and by the Java Formatter documentation the conversion f uses a locale-specific decimal separator. In Python's format specification only the type n is locale-aware.