Project Euler Problem 661

Two friends A and B are great fans of Chess.

Project Euler Problem 661

Solution

Answer: 646231.2177

Let the score difference after $n$ games be

$$S_n = (#\text{wins by A})-(#\text{wins by B}).$$

Then after each game:

  • $S\to S+1$ with probability $a=p_A$,
  • $S\to S-1$ with probability $b=p_B$,
  • $S\to S$ with probability $d=1-a-b$.

Also, after every game the match stops with probability $p$, so it continues with probability

$$q=1-p.$$

We want

$$\mathbb E_A(a,b,p) =\sum_{n\ge1}\Pr(S_n>0,\text{ game }n\text{ is played}).$$

Since game $n$ is played iff the previous $n-1$ continuation tosses were tails,

$$\Pr(\text{game }n\text{ played})=q^{,n-1}.$$

Hence

$$\mathbb E_A(a,b,p) =\sum_{n\ge1} q^{n-1}\Pr(S_n>0).$$


1. Solving the random-walk recurrence

Define $F_i$ to be the expected future number of times A leads, starting from score difference $i$.

For $i\ge2$,

$$F_i =1+q(aF_{i+1}+bF_{i-1}+dF_i),$$

because after one more game A is certainly still leading.

For $i\le -1$,

$$F_i=q(aF_{i+1}+bF_{i-1}+dF_i),$$

since A is not currently leading.

At the boundary:

$$F_1=a(1+qF_2)+b(qF_0)+d(1+qF_1),$$

$$F_0=a(1+qF_1)+b(qF_{-1})+d(qF_0).$$


Homogeneous solution

The characteristic equation is

$$qa r^2-(1-qd)r+qb=0.$$

Let its roots be $\alpha,\beta$ with $\alpha<1<\beta$:

$$\alpha,\beta = \frac{1-qd\mp\sqrt{\Delta}}{2qa},$$

where

$$\Delta=(1-qd)^2-4q^2ab.$$

Using $d=1-a-b$,

$$\Delta = p^2+2pq(a+b)+q^2(a-b)^2.$$

The bounded solutions are

$$F_i= \begin{cases} \dfrac1p + B\alpha^i, & i\ge1,\[1ex] C\beta^i, & i\le -1. \end{cases}$$

Solving the boundary equations gives

$$F_0 = \frac{1-\alpha}{pq(\beta-\alpha)}.$$

Using

$$\beta-\alpha=\frac{\sqrt{\Delta}}{qa},$$

and simplifying,

$$\boxed{ \mathbb E_A(a,b,p) = \frac{\sqrt{\Delta}-p+q(a-b)} {2pq\sqrt{\Delta}} }$$

with

$$\Delta = p^2+2pq(a+b)+q^2(a-b)^2.$$


2. Apply to $H(50)$

We are given

$$a=\frac1{\sqrt{k+3}}, \qquad b=\frac1{\sqrt{k+3}}+\frac1{k^2}, \qquad p=\frac1{k^3}.$$

So

$$H(50) = \sum_{k=3}^{50} \mathbb E_A(a,b,p).$$


3. Python implementation

from math import sqrt

def EA(a, b, p):
    q = 1.0 - p

    Delta = (
        p * p
        + 2.0 * p * q * (a + b)
        + q * q * (a - b) * (a - b)
    )

    root = sqrt(Delta)

    return (root - p + q * (a - b)) / (2.0 * p * q * root)

H = 0.0

for k in range(3, 51):
    a = 1.0 / sqrt(k + 3)
    b = a + 1.0 / (k * k)
    p = 1.0 / (k ** 3)

    H += EA(a, b, p)

print("{:.10f}".format(H))

4. Verification against the examples

For

$$(a,b,p)=(0.25,0.25,0.5),$$

the formula gives

$$0.5857864376\ldots$$

matching the statement.

For

$$(a,b,p)=(0.47,0.48,0.001),$$

it gives

$$377.4717357\ldots$$

again matching the statement.

Finally,

$$H(50)=646231.2176705868\ldots$$

which rounds to 4 decimal places as

$$646231.2177.$$

Answer: 646231.2177