Project Euler Problem 938

Solution

Answer: 0.2928967987

Let $P(R,B)$ denote the probability that the final remaining colour is black.

At a state $(R,B)$, two cards are drawn:

RR with probability $\dfrac{R(R-1)}{(R+B)(R+B-1)}$, leading to $(R-2,B)$
BB with probability $\dfrac{B(B-1)}{(R+B)(R+B-1)}$, which returns to the same state
RB with probability $\dfrac{2RB}{(R+B)(R+B-1)}$, leading to $(R,B-1)$

Therefore,

$$P(R,B)= \frac{R(R-1)}{N(N-1)}P(R-2,B) +\frac{B(B-1)}{N(N-1)}P(R,B) +\frac{2RB}{N(N-1)}P(R,B-1),$$

where $N=R+B$.

Rearranging,

$$P(R,B)= \frac{R-1}{R+2B-1}P(R-2,B) + \frac{2B}{R+2B-1}P(R,B-1).$$

Boundary conditions:

$$P(0,B)=1,\qquad P(R,0)=0 \text{ for } R>0.$$

Since $R=24690=2\cdot12345$, define

$$f(k,b)=P(2k,b).$$

Then

$$f(k,b)= \frac{2k-1}{2k+2b-1}f(k-1,b) + \frac{2b}{2k+2b-1}f(k,b-1).$$

A simple $O(KB)$ dynamic program computes the answer.

Python code:

K = 12345
B = 12345

# dp[b] = current row values
dp = [1.0] * (B + 1)   # k = 0 => P(0,b)=1

for k in range(1, K + 1):
    dp[0] = 0.0        # P(2k,0)=0

    for b in range(1, B + 1):
        dp[b] = (
            (2*k - 1) * dp[b]
            + 2*b * dp[b - 1]
        ) / (2*k + 2*b - 1)

print(f"{dp[B]:.10f}")

This reproduces the given checks:

$P(2,2)=0.4666666667$
$P(10,9)=0.4118903397$
$P(34,25)=0.3665688069$

and yields

$$P(24690,12345)=0.2928967987\ldots$$

Answer: 0.2928967987