Detailed mathematical approach

Problem Summary

A \(30\times 30\) board starts with exactly one flea in every square, so there are \(900\) fleas in total. Whenever the bell rings, each flea jumps simultaneously to one orthogonally adjacent square chosen uniformly from its valid neighbors. Corner squares therefore have degree \(2\), edge squares degree \(3\), and interior squares degree \(4\).

After \(50\) bells, several fleas may land on the same square and some squares may be empty. The goal is to compute the expected number of empty squares, rounded to six decimal places. The direct joint state space of all \(900\) fleas is far too large, so the solution has to exploit independence and expectation rather than simulate every combined configuration.

Mathematical Approach

The right viewpoint is a random walk on the grid graph. Instead of tracking all fleas together, we study one starting square at a time and then recombine the results.

A Single Flea as a Markov Chain

Let \(V\) be the set of the \(900\) squares, and let \(\deg(u)\in\{2,3,4\}\) be the number of valid neighbors of square \(u\). For a flea that starts in square \(s\), define

$p_s^{(t)}(v)=\mathbb{P}(\text{the flea is at }v\text{ after }t\text{ bells}).$

The initial condition is concentrated at the start:

$p_s^{(0)}(v)= \begin{cases} 1,& v=s,\\ 0,& v\ne s. \end{cases}$

Each bell performs one diffusion step. If \(u\sim v\) means that \(u\) and \(v\) are orthogonal neighbors, then

$p_s^{(t+1)}(v)=\sum_{u\sim v}\frac{p_s^{(t)}(u)}{\deg(u)}.$

This is exactly the transition rule implemented in code: every square shares its current probability mass equally among its neighbors. A useful invariant is

$\sum_{v\in V} p_s^{(t)}(v)=1\qquad\text{for every }t,$

so each propagated distribution remains a genuine probability distribution.

The Probability That One Square Is Empty

Fix a target square \(v\). For every starting square \(s\), the event “the flea from \(s\) is not in \(v\) after 50 bells” has probability \(1-p_s^{(50)}(v)\). The fleas move independently of one another, so for this fixed target square we may multiply those probabilities:

$\mathbb{P}(v\text{ is empty after 50 bells})=\prod_{s\in V}\left(1-p_s^{(50)}(v)\right).$

This is the core formula of the problem. It avoids any need to describe how many fleas collide in \(v\); all that matters is whether each independent flea does or does not arrive there.

Linearity of Expectation Removes Inclusion-Exclusion

Let \(I_v\) be the indicator that square \(v\) is empty after \(50\) bells:

$I_v= \begin{cases} 1,& v\text{ is empty},\\ 0,& v\text{ is occupied}. \end{cases}$

The total number of empty squares is

$X=\sum_{v\in V} I_v.$

Even though the events “square \(v\) is empty” and “square \(w\) is empty” are not independent, expectation is linear anyway:

$\mathbb{E}[X]=\sum_{v\in V}\mathbb{E}[I_v]=\sum_{v\in V}\mathbb{P}(v\text{ is empty}).$

Substituting the previous formula gives the final expression actually computed by the implementations:

$\boxed{\mathbb{E}[X]=\sum_{v\in V}\prod_{s\in V}\left(1-p_s^{(50)}(v)\right).}$

Worked Example: A \(2\times 2\) Board After One Bell

This tiny case is useful because it matches the checkpoint used by the implementation. On a \(2\times 2\) board, every square is a corner and has exactly two neighbors. Fix one target square \(v\). After one bell, only the two adjacent starting fleas can land in \(v\), each with probability \(1/2\). The flea that started in \(v\) must leave, and the diagonally opposite flea cannot reach \(v\) in one move. Therefore

$\mathbb{P}(v\text{ empty})=\left(1-\frac12\right)\left(1-\frac12\right)\left(1-0\right)\left(1-0\right)=\frac14.$

All four squares are symmetric, so

$\mathbb{E}[X]=4\cdot\frac14=1,$

which is exactly the expected value produced by the same formula. The full \(30\times 30\) problem is identical in structure; only the diffusion tables are larger.

How the Code Works

Build the Grid Graph Once

The C++, Python, and Java implementations first index the \(30\times 30\) board as \(900\) vertices and build the adjacency list of each square. This encodes the degree pattern \(2/3/4\) for corners, edges, and interior cells.

Propagate One Starting Distribution for 50 Steps

For each starting square \(s\), the implementation initializes a probability vector with mass \(1\) at \(s\) and \(0\) elsewhere. It then performs \(50\) rounds of diffusion using the recurrence above, always reusing two arrays: one for the current distribution and one for the next distribution. After the 50th round, the vector holds all values \(p_s^{(50)}(v)\).

Accumulate Empty-Square Probabilities Multiplicatively

A separate array stores, for every target square \(v\), the running product \(\prod_s (1-p_s^{(50)}(v))\). After finishing the diffusion for one starting square, the implementation multiplies each target entry by the new factor \(1-p_s^{(50)}(v)\). Once all \(900\) starting squares have been processed, each entry already equals the probability that the corresponding square is empty after \(50\) bells.

The final step is just one summation over the \(900\) targets, which returns the expected number of empty squares.

Complexity Analysis

Let the side length be \(n\), so the number of squares is \(N=n^2\). Building the adjacency list takes \(O(N)\) time and \(O(N)\) memory because each square has at most four neighbors.

For each of the \(N\) starting squares, the algorithm performs \(T\) diffusion rounds, and each round touches all \(N\) squares with constant-degree updates. That gives \(O(TN^2)\) time overall. Since \(N=n^2\), this is \(O(Tn^4)\).

The working memory stays \(O(N)\): one adjacency structure of linear size, one accumulator for empty-square probabilities, and two reusable probability vectors for the current and next diffusion layers. For the actual parameters \(n=30\) and \(T=50\), this straightforward dynamic-programming approach is entirely practical.

Footnotes and References

1. Project Euler problem page: Problem 213 - Flea Circus
2. Markov chains: Wikipedia - Markov chain
3. Random walks on graphs: Wikipedia - Random walk
4. Expected value: Wikipedia - Expected value
5. Linearity of expectation: Wikipedia - Properties of expected value