Solution

Answer: 330.721154

Let $E$ denote the expected number of empty squares after 50 random jumps.

The key observation is that the fleas move independently.

Instead of tracking all $900$ fleas jointly (impossible directly), we compute for each square $s$:

$$\Pr(s \text{ is empty after 50 steps})$$

and then sum over all squares.

1. Mathematical analysis

Consider a fixed target square $s$.

For each starting square $i$, let

$$p_{i\to s}^{(50)}$$

be the probability that the flea starting at $i$ is at $s$ after 50 jumps.

Since fleas move independently,

$$\Pr(s \text{ empty}) = \prod_{i=1}^{900} \left(1-p_{i\to s}^{(50)}\right)$$

because each flea independently avoids $s$.

Therefore,

$$E = \sum_{s} \Pr(s \text{ empty}) = \sum_{s} \prod_{i=1}^{900} \left(1-p_{i\to s}^{(50)}\right)$$

So the problem reduces to computing all 50-step transition probabilities on the $30\times30$ grid.

Markov-chain structure

A flea performs a random walk on the grid.

If a square has degree $d\in{2,3,4}$, then from that square the flea moves uniformly to one of its neighbors with probability $1/d$.

The state space has only $900$ states, so we can evolve probabilities dynamically.

For one starting square:

initialize probability $1$ at the start,
repeatedly distribute probability mass to neighbors for 50 steps.

This gives all $p_{i\to s}^{(50)}$.

Doing this naively for all $900$ starts costs roughly

$$900 \times 50 \times 900$$

operations, which is completely feasible.

2. Python implementation

from math import prod

N = 30
STEPS = 50

# ------------------------------------------------------------
# Build neighbor lists for every square
# ------------------------------------------------------------

neighbors = {}

for r in range(N):
    for c in range(N):
        adj = []

        if r > 0:
            adj.append((r - 1, c))
        if r < N - 1:
            adj.append((r + 1, c))
        if c > 0:
            adj.append((r, c - 1))
        if c < N - 1:
            adj.append((r, c + 1))

        neighbors[(r, c)] = adj

# ------------------------------------------------------------
# empty_prob[r][c] will accumulate:
#   product over fleas of (1 - probability flea ends here)
# ------------------------------------------------------------

empty_prob = [[1.0 for _ in range(N)] for _ in range(N)]

# ------------------------------------------------------------
# Process each flea independently
# ------------------------------------------------------------

for sr in range(N):
    for sc in range(N):

        # Current probability distribution
        cur = [[0.0 for _ in range(N)] for _ in range(N)]
        cur[sr][sc] = 1.0

        # Perform 50 random-walk steps
        for _ in range(STEPS):

            nxt = [[0.0 for _ in range(N)] for _ in range(N)]

            for r in range(N):
                for c in range(N):

                    p = cur[r][c]

                    if p == 0.0:
                        continue

                    adj = neighbors[(r, c)]
                    share = p / len(adj)

                    for nr, nc in adj:
                        nxt[nr][nc] += share

            cur = nxt

        # Multiply contribution into empty probabilities
        for r in range(N):
            for c in range(N):
                empty_prob[r][c] *= (1.0 - cur[r][c])

# ------------------------------------------------------------
# Expected number of empty squares
# ------------------------------------------------------------

answer = 0.0

for r in range(N):
    for c in range(N):
        answer += empty_prob[r][c]

print(f"{answer:.6f}")

3. Code walkthrough

Building neighbors

neighbors[(r, c)]

stores all legal adjacent squares.

corners have 2 neighbors,
edges have 3,
interior squares have 4.

Empty-square probabilities

We maintain:

empty_prob[r][c]

Initially every square is certainly empty with probability $1$ before considering any fleas.

For each flea we multiply by:

$$1 - p_{i\to s}^{(50)}$$

because that flea must avoid the square.

Simulating one flea

cur[sr][sc] = 1.0

starts the flea at its initial square.

Each step distributes probability equally among neighbors.

This is exactly the Markov transition rule.

After 50 iterations:

cur[r][c]

equals the probability the flea finishes at $(r,c)$.

Final expectation

For each square:

answer += empty_prob[r][c]

which implements

$$E = \sum_s \Pr(s \text{ empty})$$

by linearity of expectation.

4. Verification

Some sanity checks:

Initially there are no empty squares.
As fleas randomize, collisions occur.
Therefore the expected number of empty squares should become substantial but remain below 900.
A value around $300$–$350$ is reasonable because the distribution becomes somewhat mixed but not perfectly uniform after only 50 steps.

Running the program gives:

$$330.721154\ldots$$

which fits expectations.

Rounded to six decimal places:

Answer: 330.721154

Project Euler Problem 213