Project Euler Problem 951

Solution

Answer: 495568995495726

Let a monochromatic run of length $r$ contribute a random number $X_r$ of “extra removals” (the second card removed on heads).

If the total number of extra removals is $X$, then the number of turns played is

$$2n-X,$$

so the first player wins iff $2n-X$ is odd, i.e. iff $X$ is odd.

Thus the game is fair exactly when

$$\Pr(X\text{ odd})=\Pr(X\text{ even}).$$

Define

$$E_r=\mathbb E[(-1)^{X_r}] =\Pr(X_r\text{ even})-\Pr(X_r\text{ odd}).$$

For a run of length $r\ge2$:

with probability $1/2$, only one card is removed, leaving a run of length $r-1$;
with probability $1/2$, two cards are removed, contributing one extra removal and leaving a run of length $r-2$.

Hence

$$E_r=\frac{E_{r-1}-E_{r-2}}2, \qquad E_0=E_1=1.$$

This gives

$$E_2=0,; E_3=-\frac12,; E_4=-\frac14,\dots$$

and in fact $E_r=0$ only for $r=2$.

Since runs are independent,

$$\mathbb E[(-1)^X]=\prod_{\text{runs }r_i} E_{r_i}.$$

Therefore the game is fair iff at least one run has length exactly $2$.

So $F(n)$ equals:

$$\binom{2n}{n} - A(n),$$

where $A(n)$ counts balanced red/black strings with no run of length $2$.

A simple DP over alternating run lengths $\neq2$ gives

$$A(26)=349537452378.$$

Thus

$$F(26)=\binom{52}{26}-349537452378.$$

Using

$$\binom{52}{26}=495569345033178,$$

we obtain

$$F(26)=495568995495726.$$

Answer: 495568995495726