Solution

Answer: 0.000989640561

Let the grid size be $N \times N$, with $N=1000$.

A room has:

degree $2$ at corners,
degree $3$ on edges (non-corners),
degree $4$ in the interior.

We must compute the long-run probability that Leonhard is in a square-numbered room, averaging over the two possible movement rules.

1. Stationary distribution for rule (i)

In rule (i), Leonhard chooses uniformly among:

staying put,
each adjacent room.

So a room with degree $d$ has $d+1$ equally likely choices.

For an undirected graph of this type, the stationary distribution is proportional to $d+1$.

Thus the weights are:

corner: $3$,
edge: $4$,
interior: $5$.

Total weight:

$$4\cdot 3 + 4(N-2)\cdot 4 + (N-2)^2\cdot 5$$

For $N=1000$,

$$W_1 = 5N^2 - 4N = 4{,}996{,}000.$$

2. Stationary distribution for rule (ii)

In rule (ii):

probability $1/2$ to stay,
remaining $1/2$ split equally among neighbors.

The stationary distribution is proportional to the degree $d$.

Thus the weights are:

corner: $2$,
edge: $3$,
interior: $4$.

Total weight:

$$W_2 = 4N^2 - 4N = 3{,}996{,}000.$$

3. Count square-numbered rooms by location type

The square-numbered rooms are:

$$1^2,2^2,\dots,1000^2.$$

There are $1000$ square-numbered rooms total.

Checking their positions in the $1000\times1000$ grid gives:

corners: $2$,
edges (non-corners): $46$,
interior: $952$.

(Indeed $2+46+952=1000$.)

4. Probability under each rule

Rule (i)

Weighted square-room total:

$$3\cdot2 + 4\cdot46 + 5\cdot952 = 4950.$$

Hence

$$P_1=\frac{4950}{4{,}996{,}000}.$$

Rule (ii)

Weighted square-room total:

$$2\cdot2 + 3\cdot46 + 4\cdot952 = 3950.$$

Hence

$$P_2=\frac{3950}{3{,}996{,}000}.$$

5. Average over the coin flip

$$P=\frac{P_1+P_2}{2} = \frac12\left( \frac{4950}{4{,}996{,}000} + \frac{3950}{3{,}996{,}000} \right).$$

This simplifies to

$$P=\frac{49393}{49910040} \approx 0.000989640561297887\ldots$$

Rounded to 12 decimal places:

$$0.000989640561$$

Answer: 0.000989640561

Project Euler Problem 575