Detailed mathematical approach

Problem Summary

There are \(n\) labeled participants and initially two slips carrying each label. The participants act in the order \(1,2,\dots,n-1\). When participant \(k\) acts, every remaining slip labeled \(k\) is forbidden to that participant, and then two admissible slips are drawn uniformly without replacement. The quantity \(q(n)\) is the probability that when the final participant is reached, at least one slip carrying label \(n\) is still present.

A direct history-by-history simulation would branch far too much, because the exact identity of many remaining slips quickly stops mattering. The key idea is to replace the full multiset of labels by a symmetry-reduced state that remembers only the information relevant for future exclusions and for the survival of label \(n\).

Mathematical Approach

Let \(\mathcal{F}_k(\rho,\mu,\sigma_1,\sigma_2)\) be the success probability from stage \(k\), where the state variables mean:

\(\rho\): how many slips labeled \(k\) are still present, so they are forbidden at the current stage;

\(\mu\): how many slips labeled \(n\) are still present;

\(\sigma_1\): how many future intermediate labels currently have exactly one self-labeled slip left;

\(\sigma_2\): how many future intermediate labels currently have exactly two self-labeled slips left.

Step 1: Compress the Remaining Box by Symmetry

At stage \(k\), the total number of remaining slips is

$T_k=2(n-k+1).$

We do not need to remember every label separately. For any future intermediate participant, only the number \(0\), \(1\), or \(2\) of remaining self-labeled slips matters, because that number determines how many slips will be forbidden when that participant later becomes current. All labels in the same class are interchangeable.

The box therefore splits into four groups: the \(\rho\) forbidden slips of the current participant, the \(\mu\) slips of the final participant, the \(\sigma_1\) tracked slips belonging to class-1 future labels, and the \(2\sigma_2\) tracked slips belonging to class-2 future labels. Every other remaining slip can be merged into one generic pool. Its size is forced to be

$\gamma=T_k-\rho-\mu-\sigma_1-2\sigma_2.$

This generic pool contains slips whose exact labels no longer matter individually: slips of already processed participants, and also non-critical slips from future labels whose exclusion status is already encoded by \(\sigma_1\) and \(\sigma_2\).

Step 2: Describe One Stage as Two Draws Without Replacement

The current participant may draw from all slips except the \(\rho\) forbidden ones, so the admissible total is

$A=T_k-\rho.$

The four drawable categories have counts

$c_0=\gamma,\qquad c_1=\mu,\qquad c_2=\sigma_1,\qquad c_3=2\sigma_2.$

If the first draw uses category \(u\) and the second uses category \(v\), then the ordered probability is

$\Pr(u,v)=\frac{c_u}{A}\cdot\frac{c_v^{(u)}}{A-1},$

where \(c_v^{(u)}\) is the updated count after the first draw. Ordered pairs are necessary, because the second draw sees a different box.

Step 3: Update the Compressed Counts After a Draw

The effect of one draw depends only on its category:

$\begin{aligned} \text{generic draw} &:\quad \gamma\to\gamma-1,\\ \text{final-label draw} &:\quad \mu\to\mu-1,\\ \text{class-1 draw} &:\quad \sigma_1\to\sigma_1-1,\\ \text{class-2 draw} &:\quad \sigma_2\to\sigma_2-1,\qquad \sigma_1\to\sigma_1+1. \end{aligned}$

The last line reflects a future label that used to have two self-labeled slips and now has only one. After two draws we obtain updated values \(\mu',\sigma_1',\sigma_2'\), while \(\gamma\) can always be recomputed from the conservation formula.

Step 4: Average Over the Next Participant

After stage \(k\), the next current participant is \(k+1\). The compressed state does not record which future label is \(k+1\); it records only how many future labels lie in class \(0\), \(1\), or \(2\). By symmetry, \(k+1\) is uniformly distributed over those future labels.

Let

$N_f=n-k-1,\qquad \tau_1=\sigma_1',\qquad \tau_2=\sigma_2',\qquad \tau_0=N_f-\tau_1-\tau_2.$

If \(k=n-1\), there is no intermediate participant left, so the continuation is simply success or failure according to whether \(\mu'>0\).

Otherwise the continuation value is

$\frac{\tau_0}{N_f}\mathcal{F}_{k+1}(0,\mu',\tau_1,\tau_2)+\frac{\tau_1}{N_f}\mathcal{F}_{k+1}(1,\mu',\tau_1-1,\tau_2)+\frac{\tau_2}{N_f}\mathcal{F}_{k+1}(2,\mu',\tau_1,\tau_2-1).$

This is the central symmetry step: instead of tracking identities, we average over the three possible classes of the next participant.

Step 5: Boundary Condition and Initial State

When the process reaches stage \(n\), the only question left is whether at least one slip labeled \(n\) survived. Therefore

$\mathcal{F}_n(\rho,\mu,\sigma_1,\sigma_2)= \begin{cases} 1,& \mu>0,\\ 0,& \mu=0. \end{cases}$

At the start, participant \(1\) has both self-labeled slips still present, the final participant also has both of theirs, and every intermediate future participant starts in class \(2\). Hence

$q(n)=\mathcal{F}_1(2,2,0,n-2).$

Worked Example: \(n=3\)

The initial state is \(\mathcal{F}_1(2,2,0,1)\). Participant \(1\) cannot draw the two slips labeled \(1\), so the admissible box contains exactly four slips: two labeled \(2\) and two labeled \(3\).

If both draws remove label \(3\), the probability is

$\frac{2}{4}\cdot\frac{1}{3}=\frac{1}{6},$

and the process fails immediately because no slip labeled \(3\) remains.

If one draw removes label \(2\) and the other removes label \(3\), the total probability is

$2\cdot\frac{2}{4}\cdot\frac{2}{3}=\frac{2}{3}.$

Then participant \(2\) reaches stage \(2\) with one forbidden self-slip and one surviving slip labeled \(3\). Among the three admissible slips, only one carries label \(3\), so participant \(2\) leaves that slip untouched with probability \(1/3\).

If both draws remove label \(2\), the probability is again \(1/6\). Then participant \(2\) faces four admissible slips, two of which are labeled \(3\); the only failure is drawing both of them, so the continuation probability is \(1-1/6=5/6\).

Combining the three cases gives

$q(3)=\frac{1}{6}\cdot 0+\frac{2}{3}\cdot\frac{1}{3}+\frac{1}{6}\cdot\frac{5}{6}=\frac{13}{36}=0.361111\ldots,$

which matches the checkpoint used by the implementation.

How the Code Works

The C++, Python, and Java implementations all memoize the same five-parameter dynamic-programming state. The dense versions store values in a flattened table indexed by the stage and the four compressed counters, while the Python version uses a dictionary keyed by the same tuple. In every state, the implementation reconstructs the generic pool size from the conservation equation, computes the admissible total, and then loops over the \(4\times 4\) ordered category pairs for the two draws.

Pairs with zero count are skipped immediately. For each valid pair, the implementation applies the category updates twice, computes the continuation mixture over the three possible classes of the next participant, and adds the weighted contribution to the memoized answer. Because all symmetric labels are merged from the start, the program never needs to enumerate actual names or explicit draw histories.

Complexity Analysis

The stage index contributes \(O(n)\) possibilities, the two slip counters \(\rho\) and \(\mu\) each range over \(\{0,1,2\}\), and the two future-class counters range up to \(n\). Therefore the worst-case state space is \(O(n^4)\). Each state performs at most \(16\) ordered draw transitions and a constant-size continuation mixture, so the running time is \(O(n^4)\) with a moderate constant factor. The dense table versions use \(O(n^4)\) memory, while the memoized dictionary version stores only the reachable subset, though the same worst-case bound still applies.

Footnotes and References

1. Problem page: https://projecteuler.net/problem=740
2. Secret Santa: Wikipedia - Secret Santa
3. Dynamic programming: Wikipedia - Dynamic programming
4. Hypergeometric distribution: Wikipedia - Hypergeometric distribution
5. Memoization: Wikipedia - Memoization