Project Euler Problem 815

Solution

Answer: 54.12691621

Let the state of the process be described by

• $u$: number of values not yet seen,
• $a$: number of piles of size $1$,
• $b$: number of piles of size $2$,
• $c$: number of piles of size $3$.

Then the current number of nonempty piles is

$$s=a+b+c.$$

Initially the state is

$$(u,a,b,c)=(n,0,0,0).$$

A pile disappears when it reaches size $4$.

---

1. Mathematical analysis

At state $(u,a,b,c)$, the remaining cards are

$$4u+3a+2b+c.$$

Indeed:

• each unseen value contributes $4$ cards,
• each size-1 pile contributes $3$ remaining cards,
• each size-2 pile contributes $2$,
• each size-3 pile contributes $1$.

The transitions are:

Draw a new value

Probability

$$\frac{4u}{4u+3a+2b+c}.$$

State changes:

$$(u,a,b,c)\to(u-1,a+1,b,c).$$

The number of piles increases by $1$.

---

Extend a size-1 pile

Probability

$$\frac{3a}{4u+3a+2b+c}.$$

Transition:

$$(u,a,b,c)\to(u,a-1,b+1,c).$$

Number of piles unchanged.

---

Extend a size-2 pile

Probability

$$\frac{2b}{4u+3a+2b+c}.$$

Transition:

$$(u,a,b,c)\to(u,a,b-1,c+1).$$

Number of piles unchanged.

---

Complete a size-3 pile

Probability

$$\frac{c}{4u+3a+2b+c}.$$

Transition:

$$(u,a,b,c)\to(u,a,b,c-1).$$

Number of piles decreases by $1$.

---

We must compute the expected maximum number of simultaneous piles during the whole process.

The cleanest approach is dynamic programming over:

$$(u,a,b,c,m),$$

where $m$ is the maximum number of piles seen so far.

We propagate probabilities through all $4n$ card draws.

At the end, all states are $(0,0,0,0,m)$, so

$$E(n)=\sum_m m\Pr(M=m).$$

---

2. Python implementation

from collections import defaultdict

def expected_max_piles(n):
    # state = (u, a, b, c, m)
    # u = unseen values
    # a = piles of size 1
    # b = piles of size 2
    # c = piles of size 3
    # m = maximum number of piles seen so far

    dp = {(n, 0, 0, 0, 0): 1.0}

    # There are exactly 4n card draws
    for _ in range(4 * n):

        nxt = defaultdict(float)

        for (u, a, b, c, m), prob in dp.items():

            remaining = 4*u + 3*a + 2*b + c
            piles = a + b + c

            # Draw a new value
            if u:
                new_piles = piles + 1
                nxt[(u-1, a+1, b, c,
                     max(m, new_piles))] += prob * (4*u / remaining)

            # Extend a size-1 pile
            if a:
                nxt[(u, a-1, b+1, c, m)] += prob * (3*a / remaining)

            # Extend a size-2 pile
            if b:
                nxt[(u, a, b-1, c+1, m)] += prob * (2*b / remaining)

            # Complete a size-3 pile
            if c:
                nxt[(u, a, b, c-1, m)] += prob * (c / remaining)

        dp = nxt

    # Expected value of the maximum
    ans = 0.0

    for (u, a, b, c, m), prob in dp.items():
        ans += m * prob

    return ans

# Check the example
print(f"{expected_max_piles(2):.8f}")

# Compute E(60)
print(f"{expected_max_piles(60):.8f}")

---

3. Code walkthrough

Initialization

dp = {(n, 0, 0, 0, 0): 1.0}

Initially:

• all $n$ values are unseen,
• no piles exist,
• maximum pile count so far is $0$.

---

State transitions

For each state we compute:

remaining = 4*u + 3*a + 2*b + c

which is the number of cards left in the deck.

Then we distribute probability mass according to the four possible card types.

---

Tracking the maximum

When a new pile is created:

new_piles = piles + 1
max(m, new_piles)

updates the running maximum.

---

Final expectation

After all $4n$ cards are processed, every path has ended.

We compute:

ans += m * prob

which is exactly

$$E(M)=\sum_m m,P(M=m).$$

---

4. Verification

For $n=2$, the program gives

$$E(2)=1.97142857,$$

matching the value given in the problem statement.

For $n=60$, the computation is stable and produces a value slightly below $60$, as expected.

---

Answer: 54.12691621