Project Euler Problem 783
Given n and k two positive integers we begin with an urn that contains kn white balls.
Solution
Answer: 136666597
Let $X_t$ be the number of black balls remaining in the urn just before turn $t$. Initially $X_1=0$.
On turn $t$:
- Total balls before adding black balls:
$$k(n-t+1)$$
- After adding $k$ black balls:
$$N_t = k(n-t+2)$$
- Black balls present before removal:
$$M_t = X_t + k$$
We remove $2k$ balls uniformly at random. Thus
$$B_t \sim \text{Hypergeometric}(N_t,M_t,2k)$$
and
$$\mathbb E[B_t\mid M_t] = 2k\frac{M_t}{N_t}$$
$$\mathbb E[B_t^2\mid M_t] = \operatorname{Var}(B_t\mid M_t) + \mathbb E[B_t\mid M_t]^2$$
Using the hypergeometric variance,
$$\operatorname{Var}(B_t\mid M_t) = 2k\cdot \frac{M_t}{N_t} \left(1-\frac{M_t}{N_t}\right) \frac{N_t-2k}{N_t-1}$$
we can propagate only the first two moments of $X_t$:
$$\mathbb E[X_t],\qquad \mathbb E[X_t^2]$$
which gives an $O(n)$ dynamic program.
A correctness check:
$$E(2,2)=9.6$$
matching the problem statement.
Running the recurrence for $(n,k)=(10^6,10)$ gives
$$E(10^6,10)=136666597.00006783\ldots$$
Rounded to the nearest whole number:
Answer: 136666597