Project Euler Problem 605

Solution

Answer: 59992576

Let $T$ be the round at which the game ends.

A player wins if they win two consecutive rounds involving them. Encode round $r$ by a bit:

$b_r = 0$: the first player in round $r$ wins,
$b_r = 1$: the second player wins.

For rounds

$$(i,i+1),\ (i+1,i+2),$$

player $i+1$ wins both iff the outcomes are

$$(1,0).$$

So the game ends at the first occurrence of the pattern $10$ in the infinite fair coin sequence $(b_r)$.

Step 1: Distribution of the first $10$

Suppose the first $10$ occurs ending at round $r$. Then:

no earlier $10$ appears in $b_1,\dots,b_{r-1}$,
$b_{r-1}=1,\ b_r=0$.

A binary string avoiding $10$ must be of the form

$$0^a1^b$$

(monotone: once a $1$ appears, no later $0$ can appear).

To end with the first $10$ at round $r$, the first $r-1$ bits must be

$$0^a1^{r-1-a},$$

ending in $1$, and there are exactly $r-1$ choices for $a$.

Hence

$$\Pr(T=r)=\frac{r-1}{2^r}.$$

Step 2: Which player wins?

Player $k$ wins when the first $10$ ends at a round

$$r \equiv k \pmod n.$$

Since $k=10^4+7>1$, valid rounds are

$$r = k + mn,\qquad m\ge0.$$

Thus

$$P_n(k) = \sum_{m\ge0} \frac{k+mn-1}{2^{k+mn}}.$$

Let

$$A=2^n-1.$$

Using geometric series,

$$P_n(k) = 2^{-k} \left( \frac{k-1}{1-2^{-n}} + \frac{n,2^{-n}}{(1-2^{-n})^2} \right).$$

Since

$$1-2^{-n}=\frac{A}{2^n},$$

this simplifies to

$$P_n(k) = \frac{2^{,n-k}\big((k-1)A+n\big)}{A^2}.$$

For $k>1$, the fraction is already reduced because:

$A=2^n-1$ is odd,
$\gcd((k-1)A+n,A)=\gcd(n,A)=1$.

Therefore

$$M_n(k) = 2^{,n-k} \big((k-1)A+n\big) A^2.$$

We only need the last $8$ digits, i.e. modulo $10^8$.

Python code:

MOD = 10**8

n = 10**8 + 7
k = 10**4 + 7

# A = 2^n - 1 (mod 10^8)
A = (pow(2, n, MOD) - 1) % MOD

# B = (k - 1)A + n (mod 10^8)
B = ((k - 1) * A + n) % MOD

# M_n(k) mod 10^8
answer = (
    pow(2, n - k, MOD)
    * B
    * A
    * A
) % MOD

print(answer)

This evaluates to:

$$59992576.$$

Quick verification:

For $n=6,k=2$, the formula gives

$$P_6(2)=\frac{368}{1323},$$

matching the problem statement.

Therefore the required last $8$ digits are:

Answer: 59992576