Project Euler Problem 151

Solution

Answer: 0.464399

Let the state of the envelope be

$$(a_2,a_3,a_4,a_5)$$

where $a_k$ is the number of sheets of size $A_k$ currently in the envelope.

After the very first batch (Monday morning), the initial $A1$ sheet has been repeatedly cut down to obtain one $A5$ sheet for printing. The unused sheets returned to the envelope are:

$${A2,A3,A4}$$

so the initial state is

$$(1,1,1,0).$$

We must compute the expected number of times, excluding the first and last batch, that the envelope contains exactly one sheet before a batch begins.

---

1. State transitions

Suppose the current state is

$$(a_2,a_3,a_4,a_5).$$

The total number of sheets is

$$N=a_2+a_3+a_4+a_5.$$

A sheet is selected uniformly at random.

---

If an $A5$ is selected

Probability:

$$\frac{a_5}{N}.$$

It is simply used, so:

$$(a_2,a_3,a_4,a_5)\to(a_2,a_3,a_4,a_5-1).$$

---

If an $A4$ is selected

Probability:

$$\frac{a_4}{N}.$$

An $A4$ is cut into two $A5$ sheets; one $A5$ is used, the other is returned.

Net effect:

• remove one $A4$
• add one $A5$

So:

$$(a_2,a_3,a_4,a_5)\to(a_2,a_3,a_4-1,a_5+1).$$

---

If an $A3$ is selected

Probability:

$$\frac{a_3}{N}.$$

Cutting process:

$$A3 \to 2A4,\quad A4 \to 2A5,$$

one $A5$ is used.

Returned sheets:

• one $A4$
• one $A5$

Thus:

$$(a_2,a_3,a_4,a_5)\to(a_2,a_3-1,a_4+1,a_5+1).$$

---

If an $A2$ is selected

Probability:

$$\frac{a_2}{N}.$$

Similarly:

Returned sheets:

• one $A3$
• one $A4$
• one $A5$

Thus:

$$(a_2,a_3,a_4,a_5)\to(a_2-1,a_3+1,a_4+1,a_5+1).$$

---

2. Which states count?

We count mornings where the envelope contains exactly one sheet.

The possible single-sheet states are:

$$(1,0,0,0),\quad (0,1,0,0),\quad (0,0,1,0),\quad (0,0,0,1).$$

However:

• the very first batch is excluded,
• the very last batch is excluded.

The final state $(0,0,0,1)$ corresponds to the last batch, so it must not be counted.

Therefore the only counted singleton states are:

$$(1,0,0,0),\quad (0,1,0,0),\quad (0,0,1,0).$$

The expected value is therefore

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

where these probabilities are the probabilities of reaching those states before a batch begins.

---

3. Exact probability computation

We propagate probabilities through all reachable states.

Starting state:

$$(1,1,1,0)$$

with probability $1$.

Because the total number of sheets decreases by exactly one each batch, the process is finite and small enough for exact rational computation.

---

4. Python implementation

from fractions import Fraction
from collections import defaultdict

# ------------------------------------------------------------
# Transition function
# ------------------------------------------------------------

def transitions(state):
    a2, a3, a4, a5 = state
    total = a2 + a3 + a4 + a5

    result = []

    # choose A2
    if a2:
        p = Fraction(a2, total)
        nxt = (a2 - 1, a3 + 1, a4 + 1, a5 + 1)
        result.append((p, nxt))

    # choose A3
    if a3:
        p = Fraction(a3, total)
        nxt = (a2, a3 - 1, a4 + 1, a5 + 1)
        result.append((p, nxt))

    # choose A4
    if a4:
        p = Fraction(a4, total)
        nxt = (a2, a3, a4 - 1, a5 + 1)
        result.append((p, nxt))

    # choose A5
    if a5:
        p = Fraction(a5, total)
        nxt = (a2, a3, a4, a5 - 1)
        result.append((p, nxt))

    return result

# ------------------------------------------------------------
# Dynamic probability propagation
# ------------------------------------------------------------

start = (1, 1, 1, 0)

dist = defaultdict(Fraction)
dist[start] = Fraction(1, 1)

expected = Fraction(0, 1)

while dist:
    new_dist = defaultdict(Fraction)

    for state, prob in dist.items():

        total_sheets = sum(state)

        # Count singleton states excluding final A5 state
        if total_sheets == 1 and state != (0, 0, 0, 1):
            expected += prob

        # Continue transitions unless terminal
        if state == (0, 0, 0, 0):
            continue

        for p, nxt in transitions(state):
            new_dist[nxt] += prob * p

    dist = new_dist

# ------------------------------------------------------------
# Output
# ------------------------------------------------------------

value = float(expected)

print(expected)
print(f"{value:.6f}")

---

5. Code walkthrough

Transition generator

The function:

transitions(state)

enumerates every possible random sheet selection and returns:

(probability, next_state)

pairs.

For example:

(a2,a3,a4,a5)

choosing an $A3$ gives:

(a2, a3-1, a4+1, a5+1)

because cutting an $A3$ produces one leftover $A4$ and one leftover $A5$.

---

Probability propagation

We maintain a probability distribution over all reachable states:

dist[state] = probability

At each step we:

1. add singleton-state probability into the expectation,
2. propagate probability mass to successor states.

Because every batch removes exactly one eventual $A5$, the process terminates naturally.

---

6. Verification

The singleton states that can occur before the last batch are:

• only $A2$,
• only $A3$,
• only $A4$.

These are fairly rare events, so the expectation should be well below $1$, which matches the final value:

$$0.464399\ldots$$

This is exactly the known Project Euler result.

---

Answer: 0.464399