Solution

Answer: 5000624921.38

Let $X_i$ be the indicator random variable that disk $i$ is white after $M$ turns.

Then

$$E(N,M)=\sum_{i=1}^N \mathbb E[X_i].$$

So we only need the probability that a single disk is white after $M$ random flips.

1. Probability that disk $i$ is flipped in one move

A move chooses ordered integers $A,B\in{1,\dots,N}$ uniformly.

Disk $i$ is flipped iff $i$ lies between $A$ and $B$, i.e.

$$(A\le i\le B)\quad\text{or}\quad(B\le i\le A).$$

It is not flipped only if both endpoints are strictly left of $i$, or both strictly right of $i$.

Number of ordered pairs not flipping $i$:

$$(i-1)^2 + (N-i)^2.$$

Hence

$$p_i =1-\frac{(i-1)^2+(N-i)^2}{N^2}.$$

After simplification,

$$p_i=\frac{2i(N-i+1)-1}{N^2}.$$

2. White/black parity

Each flip toggles the color.

If a disk is flipped with probability $p_i$ independently each turn, then after $M$ turns:

$$P(\text{white}) = \frac{1+(1-2p_i)^M}{2}.$$

Define

$$q_i = 1-2p_i.$$

Then

$$E(N,M) = \sum_{i=1}^N \frac{1+q_i^M}{2} = \frac N2+\frac12\sum_{i=1}^N q_i^M.$$

Using the formula for $p_i$,

$$q_i = 1-\frac{4i(N-i+1)-2}{N^2}.$$

3. Numerical strategy for $N=10^{10}, M=4000$

Direct summation over $10^{10}$ terms is impossible.

But for most $i$,

$$|q_i|<1$$

and $q_i^{4000}$ is astronomically tiny.

Only disks near the two ends contribute appreciably.

Because of symmetry,

$$q_i=q_{N+1-i}.$$

So we sum only near one edge until terms become negligible.

4. Python implementation

from math import log, exp

N = 10**10
M = 4000

def q(i):
    return 1 - (4 * i * (N - i + 1) - 2) / (N * N)

# Sum only where contributions matter
# (beyond this, terms are effectively zero)
LIMIT = 50_000_000

s = 0.0

for i in range(1, LIMIT + 1):
    term = exp(M * log(q(i)))
    s += 2.0 * term   # symmetry

# Expected value
E = N / 2.0 + s / 2.0

print(round(E, 2))

5. Code walkthrough

`q(i)`

Computes

$$q_i = 1-2p_i.$$

Main loop

Computes

$$2\sum_{i=1}^{LIMIT} q_i^M,$$

using symmetry between the left and right edges.

Why truncation works

For moderate $i$,

$$q_i^M \approx e^{-4Mi/N}.$$

With $M=4000$ and $N=10^{10}$, terms decay exponentially and become numerically irrelevant after a few tens of millions.

6. Verification on small examples

For $N=3, M=1$:

$$E(3,1)=\frac{10}{9},$$

matching the problem statement.

For $N=3, M=2$:

$$E(3,2)=\frac53,$$

also correct.

For $N=10, M=4$:

$$E(10,4)\approx 5.157,$$

again matching the statement.

7. Final computation

Carrying out the computation gives

$$E(10^{10},4000)\approx 5000624921.38.$$

So rounded to two decimal places:

Answer: 5000624921.38

Project Euler Problem 430