Detailed mathematical approach

Problem Summary

Problem 938, Exhausting a Colour, asks for the value \(P(24690,12345)\). The three implementations make clear that the natural state is \(P(r,b)\), where \(r\) counts unresolved red objects and \(b\) counts unresolved blue pairs. The quantity being computed is the exact probability that red is the colour exhausted first.

The solution does not simulate randomness. Instead, it writes down the exact conditioning equation for each smaller state and builds the answer by dynamic programming. Once that structure is identified, the large target input becomes a straightforward table-filling problem.

Mathematical Approach

The whole derivation comes from choosing the right state description and conditioning on the next partner seen by one distinguished red object.

The state \(P(r,b)\)

Let \(P(r,b)\) denote the probability that red is eventually exhausted first when the unresolved part of the process contains \(r\) red objects and \(b\) blue pairs.

The boundary states are immediate. If no red objects remain, the desired event has already happened, so

$P(0,b)=1 \qquad (b\ge 0).$

If the blue pairs have all been consumed while red objects still remain, then red cannot be the first exhausted colour, so

$P(r,0)=0 \qquad (r>0).$

The code also encodes the relation

$P(1,b)=P(1,b-1).$

Since \(P(1,0)=0\), this forces

$P(1,b)=0 \qquad (b\ge 1).$

Condition on the partner of a red object

Now consider a state \((r,b)\) with \(r\ge 2\) and \(b\ge 1\), and expose one distinguished red object. The recurrence used in all three implementations shows that the next interaction has

$r-1+2b$

equiprobable possibilities.

There are \(r-1\) ways for the distinguished red object to meet another red object. In that branch, two red objects disappear from the unresolved configuration, so the state becomes \((r-2,b)\).

There are \(2b\) ways for it to meet one endpoint belonging to one of the blue pairs. In that branch, exactly one blue pair disappears from the remaining structure, while the reduced subproblem still has \(r\) red objects waiting to be exhausted, so the state becomes \((r,b-1)\).

Applying the law of total probability gives the central recurrence:

$P(r,b)=\frac{(r-1)P(r-2,b)+2b\,P(r,b-1)}{(r-1)+2b}, \qquad r\ge 2,\ b\ge 1.$

This formula is the mathematical heart of the solution. Every value needed for the final answer comes from repeated use of this identity together with the boundary states.

A parity invariant

The recurrence never changes the parity of \(r\): one branch replaces \(r\) by \(r-2\), and the other leaves \(r\) unchanged. Therefore an odd number of red objects can never reach \(0\).

By induction on \(b\), this yields the stronger statement

$P(r,b)=0 \qquad \text{for every odd } r.$

This explains the special handling of the \(r=1\) column in the implementations. It also shows why the target state is meaningful: \(24690\) is even, so the desired probability is not ruled out by parity.

Worked example: computing \(P(2,2)\)

A small example makes the recurrence concrete. First, from the boundary values,

$P(2,1)=\frac{1\cdot P(0,1)+2\cdot P(2,0)}{1+2}=\frac{1\cdot 1+2\cdot 0}{3}=\frac13.$

Now apply the same recurrence one row later:

$P(2,2)=\frac{1\cdot P(0,2)+4\cdot P(2,1)}{1+4}=\frac{1+4\cdot \frac13}{5}=\frac{7}{15}\approx 0.4666666667.$

This example already shows the full structure of the real computation: each state depends on one entry in the same row, one entry in the previous row, and the exact branch counts \(r-1\) and \(2b\).

How the Code Works

The C++, Python, and Java implementations evaluate the dynamic program row by row in increasing \(b\). For a fixed number of blue pairs, they sweep \(r\) from \(0\) to \(R\). That order is forced by the recurrence: \(P(r,b)\) needs \(P(r-2,b)\), which must already exist in the current row, and \(P(r,b-1)\), which comes from the previous row.

Each new row starts with \(P(0,b)=1\). The \(r=1\) entry is copied from the previous row, matching the relation \(P(1,b)=P(1,b-1)\). For every \(r\ge 2\), the implementation forms the weighted average from the recurrence and stores it immediately.

Only two one-dimensional buffers are necessary: one buffer holds the previous value of \(b\), and the other buffer is being filled for the current value of \(b\). After finishing a row, the buffers are swapped. This reduces memory from a full two-dimensional table to linear space while preserving exactly the same DP values. The final cell \(P(24690,12345)\) is then printed to 10 decimal places.

Complexity Analysis

The conceptual DP table has \((R+1)(B+1)\) states, and each non-boundary state is filled in constant time. Therefore the running time is

$O(RB).$

For the target input, that is about \(24690\times 12345 \approx 3.05\times 10^8\) simple updates, which is large but still practical for an iterative implementation.

A naive full table would require \(O(RB)\) memory, but the recurrence only refers to the current row and the previous row. The implementations therefore use

$O(R)$

memory. Numerically, every newly computed state is a convex combination of values already known to lie in \([0,1]\), so the computation is stable for the required 10-decimal output.

Footnotes and References

1. Problem page: Project Euler 938 - Exhausting a Colour
2. Dynamic programming: Wikipedia - Dynamic programming
3. Recurrence relation: Wikipedia - Recurrence relation
4. Law of total probability: Wikipedia - Law of total probability
5. Parity: Wikipedia - Parity
6. Mathematical induction: Wikipedia - Mathematical induction