The rooms of an \(N\times N\) board are labeled in row-major order by \(1,2,\dots,N^2\). The special rooms are those with square labels, namely
$$Q=\left\{1^2,2^2,\dots,N^2\right\}.$$
A robot performs a random walk on this board under two different rules. The required value is the arithmetic mean of the long-run probability of being in a room from \(Q\) under rule A and under rule B. The key observation used by the implementations is that both rules define reversible Markov chains on the same grid graph, so the stationary distribution depends only on the degree of each room.
View the board as an undirected graph. Each room is a vertex, and edges connect orthogonally adjacent rooms. Let \(d(v)\) be the number of neighbors of room \(v\). On a square grid, every room has degree \(2\), \(3\), or \(4\) depending on whether it is a corner, an edge room, or an interior room.
There are exactly \(4\) corners, \(4(N-2)\) non-corner edge rooms, and \((N-2)^2\) interior rooms. Therefore
$$\sum_{v} d(v)=2\cdot 4+3\cdot 4(N-2)+4(N-2)^2=4N(N-1).$$
This is the denominator that appears in the second random rule. For the first rule we will also need
$$\sum_{v}\bigl(d(v)+1\bigr)=\sum_{v} d(v)+N^2=5N^2-4N=N(5N-4).$$
The extra \(+1\) comes from the option to stay in the same room.
Under rule A, from a room \(v\) the robot chooses uniformly among all legal options: stay put, or move to one of the \(d(v)\) neighbors. Thus
$$P_A(v\to v)=\frac{1}{d(v)+1},\qquad P_A(v\to u)=\frac{1}{d(v)+1}\quad\text{when }u\sim v.$$
This is a reversible walk. For any adjacent rooms \(u\) and \(v\),
$$\bigl(d(v)+1\bigr)P_A(v\to u)=1=\bigl(d(u)+1\bigr)P_A(u\to v).$$
So detailed balance holds with weights proportional to \(d(v)+1\). After normalization, the stationary probability of room \(v\) is
$$\pi_A(v)=\frac{d(v)+1}{\sum_w \bigl(d(w)+1\bigr)}.$$
Under rule B, the robot stays with probability \(1/2\), and the remaining \(1/2\) is shared equally among the \(d(v)\) neighbors:
$$P_B(v\to v)=\frac12,\qquad P_B(v\to u)=\frac{1}{2d(v)}\quad\text{when }u\sim v.$$
This chain is also reversible. For adjacent rooms \(u\) and \(v\),
$$d(v)\,P_B(v\to u)=\frac12=d(u)\,P_B(u\to v).$$
Hence the stationary distribution is proportional to \(d(v)\):
$$\pi_B(v)=\frac{d(v)}{\sum_w d(w)}.$$
So rule A weights a room by \(d(v)+1\), while rule B weights it by \(d(v)\).
Because the board is labeled from \(1\) to \(N^2\), the square labels are exactly \(k^2\) for \(1\le k\le N\). The room with label \(k^2\) has coordinates
$$r_k=\left\lfloor\frac{k^2-1}{N}\right\rfloor+1,\qquad c_k=\bigl((k^2-1)\bmod N\bigr)+1.$$
Its degree is determined only by whether these coordinates lie on the boundary:
$$d_k= \begin{cases} 2,&\text{if }(r_k,c_k)\text{ is a corner},\\ 3,&\text{if }(r_k,c_k)\text{ is an edge but not a corner},\\ 4,&\text{if }(r_k,c_k)\text{ is interior}. \end{cases}$$
Let
$$S=\sum_{k=1}^{N} d_k.$$
Then the total rule-A weight of all square-numbered rooms is \(S+N\), because each of the \(N\) target rooms contributes one extra self-loop unit.
From the stationary distributions, the total long-run probability of landing in a square-numbered room is
$$P_A(Q)=\sum_{k=1}^{N}\pi_A(k^2)=\frac{S+N}{5N^2-4N},$$
and for rule B it is
$$P_B(Q)=\sum_{k=1}^{N}\pi_B(k^2)=\frac{S}{4N^2-4N}.$$
The problem asks for their arithmetic mean, so the final quantity is
$$\boxed{P(Q)=\frac12\left(\frac{S+N}{5N^2-4N}+\frac{S}{4N^2-4N}\right).}$$
Once \(S\) is known, the whole problem is solved.
The global denominators \(5N^2-4N\) and \(4N^2-4N\) are closed forms, so no simulation is required. The only nontrivial computation is to inspect each square label \(k^2\), map it to its row and column, decide whether it is a corner, edge, or interior room, and add \(2\), \(3\), or \(4\) to \(S\). That is exactly what the implementations do.
The square labels are \(1,4,9,16,25\). Their coordinates are
$$1\mapsto(1,1),\qquad 4\mapsto(1,4),\qquad 9\mapsto(2,4),\qquad 16\mapsto(4,1),\qquad 25\mapsto(5,5).$$
So their degrees are \(2,3,4,3,2\), giving
$$S=2+3+4+3+2=14,\qquad S+N=19.$$
For the whole grid,
$$\sum_v d(v)=4\cdot 5\cdot 4=80,\qquad \sum_v\bigl(d(v)+1\bigr)=5\cdot 25-20=105.$$
Therefore
$$P_A(Q)=\frac{19}{105},\qquad P_B(Q)=\frac{14}{80}=\frac{7}{40},$$
and the required average is
$$P(Q)=\frac12\left(\frac{19}{105}+\frac{7}{40}\right)=\frac{299}{1680}=0.177976190476\ldots$$
This matches the validation value used by the implementation.
The C++, Python, and Java implementations follow the same plan. First they compute the closed-form totals for the whole \(N\times N\) grid: the number of corners, edge rooms, and interior rooms, then the two denominator sums needed for the stationary distributions. Next they loop through \(k=1,2,\dots,N\), form the square label \(k^2\), convert that label to a row and column, and test whether the room lies on the top, bottom, left, or right boundary. From those boundary tests the implementation assigns degree \(2\), \(3\), or \(4\), adds it to the running square-room total, and also adds one more unit for rule A.
After this single pass, the program has exactly the two numerators required for the formulas above. It divides by the two global denominators, averages the two probabilities, and prints the result to twelve decimal places. No matrix exponentiation, simulation, or iterative convergence is needed because the stationary measure is obtained directly from detailed balance.
All whole-board quantities are computed in constant time from closed formulas. The only loop runs once for each square label \(k^2\) with \(1\le k\le N\), and each iteration performs only a few integer operations and boundary comparisons. Therefore the time complexity is \(O(N)\) and the extra space usage is \(O(1)\).
Die Räume eines \(N\times N\)-Gitters sind in Zeilenfolge mit \(1,2,\dots,N^2\) nummeriert. Gesucht sind die quadratisch nummerierten Räume
$$Q=\left\{1^2,2^2,\dots,N^2\right\}.$$
Ein Roboter führt auf diesem Gitter zwei verschiedene Zufallsbewegungen aus. Gesucht ist das arithmetische Mittel der stationären Wahrscheinlichkeit, unter Regel A beziehungsweise unter Regel B in einem Raum aus \(Q\) zu liegen. Die zentrale Beobachtung der Implementierungen lautet: Beide Regeln sind reversible Markow-Ketten auf demselben Gittergraphen, daher hängt die stationäre Verteilung nur vom Knotengrad ab.
Wir modellieren das Brett als ungerichteten Graphen. Jeder Raum ist ein Knoten, und Kanten verbinden orthogonal benachbarte Räume. Sei \(d(v)\) die Zahl der Nachbarn des Knotens \(v\). Auf dem quadratischen Gitter gilt stets \(d(v)\in\{2,3,4\}\), je nachdem, ob \(v\) eine Ecke, ein Randknoten oder ein Innenknoten ist.
Es gibt genau \(4\) Ecken, \(4(N-2)\) Randfelder ohne Ecken und \((N-2)^2\) Innenfelder. Also
$$\sum_{v} d(v)=2\cdot 4+3\cdot 4(N-2)+4(N-2)^2=4N(N-1).$$
Das ist der Nenner für die zweite Bewegungsregel. Für die erste Regel brauchen wir außerdem
$$\sum_{v}\bigl(d(v)+1\bigr)=\sum_{v} d(v)+N^2=5N^2-4N=N(5N-4).$$
Das zusätzliche \(+1\) steht für die Möglichkeit, im aktuellen Raum zu bleiben.
Unter Regel A wählt der Roboter unter allen erlaubten Optionen gleichverteilt: bleiben oder zu einem der \(d(v)\) Nachbarn gehen. Daher gilt
$$P_A(v\to v)=\frac{1}{d(v)+1},\qquad P_A(v\to u)=\frac{1}{d(v)+1}\quad\text{für }u\sim v.$$
Diese Bewegung ist reversibel. Für benachbarte Räume \(u\) und \(v\) gilt
$$\bigl(d(v)+1\bigr)P_A(v\to u)=1=\bigl(d(u)+1\bigr)P_A(u\to v).$$
Damit erfüllt die Kette Detailed Balance mit Gewichten proportional zu \(d(v)+1\). Nach Normierung erhält man
$$\pi_A(v)=\frac{d(v)+1}{\sum_w \bigl(d(w)+1\bigr)}.$$
Unter Regel B bleibt der Roboter mit Wahrscheinlichkeit \(1/2\) stehen, und die restliche Hälfte wird gleichmäßig auf die \(d(v)\) Nachbarn verteilt:
$$P_B(v\to v)=\frac12,\qquad P_B(v\to u)=\frac{1}{2d(v)}\quad\text{für }u\sim v.$$
Auch diese Kette ist reversibel. Für benachbarte Räume \(u\) und \(v\) gilt
$$d(v)\,P_B(v\to u)=\frac12=d(u)\,P_B(u\to v).$$
Daraus folgt die stationäre Verteilung
$$\pi_B(v)=\frac{d(v)}{\sum_w d(w)}.$$
Regel A gewichtet also einen Raum mit \(d(v)+1\), Regel B mit \(d(v)\).
Weil die Nummerierung von \(1\) bis \(N^2\) reicht, sind die Quadratnummern genau \(k^2\) mit \(1\le k\le N\). Der Raum mit Nummer \(k^2\) hat die Koordinaten
$$r_k=\left\lfloor\frac{k^2-1}{N}\right\rfloor+1,\qquad c_k=\bigl((k^2-1)\bmod N\bigr)+1.$$
Sein Grad hängt nur davon ab, ob diese Koordinaten auf dem Rand liegen:
$$d_k= \begin{cases} 2,&\text{wenn }(r_k,c_k)\text{ eine Ecke ist},\\ 3,&\text{wenn }(r_k,c_k)\text{ am Rand, aber keine Ecke ist},\\ 4,&\text{wenn }(r_k,c_k)\text{ im Inneren liegt}. \end{cases}$$
Setze
$$S=\sum_{k=1}^{N} d_k.$$
Dann ist die gesamte Regel-A-Gewichtung aller Zielräume gleich \(S+N\), weil jeder der \(N\) Zielräume noch eine zusätzliche Selbstschleife beiträgt.
Aus den stationären Verteilungen folgt für die Gesamtwahrscheinlichkeit, in einem quadratisch nummerierten Raum zu landen,
$$P_A(Q)=\sum_{k=1}^{N}\pi_A(k^2)=\frac{S+N}{5N^2-4N},$$
und für Regel B
$$P_B(Q)=\sum_{k=1}^{N}\pi_B(k^2)=\frac{S}{4N^2-4N}.$$
Gesucht ist ihr arithmetisches Mittel, also
$$\boxed{P(Q)=\frac12\left(\frac{S+N}{5N^2-4N}+\frac{S}{4N^2-4N}\right).}$$
Sobald \(S\) bestimmt ist, ist das Problem vollständig gelöst.
Die globalen Nenner \(5N^2-4N\) und \(4N^2-4N\) liegen in geschlossener Form vor; eine Simulation ist also überflüssig. Die einzige nichttriviale Arbeit besteht darin, jedes Quadrat \(k^2\) zu betrachten, in Zeile und Spalte umzuwandeln, festzustellen, ob der Raum Ecke, Rand oder Innenfeld ist, und dann \(2\), \(3\) oder \(4\) zu \(S\) zu addieren. Genau diese lineare Auswertung führen die Implementierungen aus.
Die Quadratnummern sind \(1,4,9,16,25\). Ihre Koordinaten lauten
$$1\mapsto(1,1),\qquad 4\mapsto(1,4),\qquad 9\mapsto(2,4),\qquad 16\mapsto(4,1),\qquad 25\mapsto(5,5).$$
Die zugehörigen Grade sind also \(2,3,4,3,2\). Damit erhält man
$$S=2+3+4+3+2=14,\qquad S+N=19.$$
Für das gesamte Gitter gilt
$$\sum_v d(v)=4\cdot 5\cdot 4=80,\qquad \sum_v\bigl(d(v)+1\bigr)=5\cdot 25-20=105.$$
Daher
$$P_A(Q)=\frac{19}{105},\qquad P_B(Q)=\frac{14}{80}=\frac{7}{40},$$
und damit
$$P(Q)=\frac12\left(\frac{19}{105}+\frac{7}{40}\right)=\frac{299}{1680}=0.177976190476\ldots$$
Das stimmt genau mit dem Kontrollwert der Implementierung überein.
Die C++-, Python- und Java-Implementierungen folgen demselben Ablauf. Zuerst berechnen sie die geschlossenen Summen für das gesamte \(N\times N\)-Gitter: die Anzahl der Ecken, Randfelder und Innenfelder sowie daraus die beiden Nenner der stationären Verteilungen. Anschließend läuft eine Schleife über \(k=1,2,\dots,N\). Für jedes \(k\) wird die Quadratnummer \(k^2\) gebildet, in Zeile und Spalte umgerechnet und per Randtests entschieden, ob der entsprechende Raum Ecke, Rand oder Innenfeld ist. Daraus ergibt sich der Grad \(2\), \(3\) oder \(4\), der zu der Zielsumme addiert wird; für Regel A kommt zusätzlich genau ein weiterer Einheitsbeitrag hinzu.
Nach diesem einzigen Durchlauf besitzt das Programm genau die beiden Zähler, die in den obigen Formeln benötigt werden. Danach werden die beiden Wahrscheinlichkeiten ausgerechnet, gemittelt und mit zwölf Nachkommastellen ausgegeben. Weder Matrixpotenzen noch Monte-Carlo-Simulationen noch iterative Konvergenzverfahren sind nötig, weil die stationäre Verteilung direkt aus Detailed Balance folgt.
Alle globalen Größen des gesamten Gitters entstehen in \(O(1)\)-Zeit aus geschlossenen Formeln. Die einzige Schleife läuft einmal über alle Quadratnummern \(k^2\) mit \(1\le k\le N\), und jeder Durchlauf benutzt nur einige Ganzzahloperationen und Randvergleiche. Daher beträgt die Laufzeit \(O(N)\), und der zusätzliche Speicherbedarf ist \(O(1)\).
\(N\times N\) tahtadaki odalar satır satır \(1,2,\dots,N^2\) diye numaralanır. İlgilendiğimiz hedef odalar kare numaralı olanlardır:
$$Q=\left\{1^2,2^2,\dots,N^2\right\}.$$
Robot bu tahtada iki farklı rastgele hareket kuralı altında dolaşır. İstenen değer, kural A ve kural B için uzun vadede \(Q\) kümesindeki bir odada bulunma olasılıklarının aritmetik ortalamasıdır. Çözümlerin dayandığı temel nokta şudur: Her iki kural da aynı ızgara grafı üzerinde tersinir bir Markov zinciri verir; bu yüzden durağan dağılım sadece odanın derecesine bağlıdır.
Tahtayı yönsüz bir grafik olarak düşünelim. Her oda bir düğümdür; yatay ya da düşey komşu odalar arasında kenar vardır. Bir odanın komşu sayısını \(d(v)\) ile gösterelim. Kare ızgarada \(d(v)\) değeri yalnızca \(2\), \(3\) veya \(4\) olabilir; bunlar sırasıyla köşe, kenar ve iç bölge odalarına karşılık gelir.
Tam olarak \(4\) köşe, \(4(N-2)\) tane köşe olmayan kenar odası ve \((N-2)^2\) tane iç oda vardır. Dolayısıyla
$$\sum_{v} d(v)=2\cdot 4+3\cdot 4(N-2)+4(N-2)^2=4N(N-1).$$
Bu toplam ikinci kuralın paydasıdır. Birinci kural için ayrıca
$$\sum_{v}\bigl(d(v)+1\bigr)=\sum_{v} d(v)+N^2=5N^2-4N=N(5N-4)$$
gerekir. Buradaki ilave \(+1\), odada kalma seçeneğinden gelir.
Kural A altında robot, bulunduğu odada kalmak ile tüm komşulara gitmek arasında eşit olasılıkla seçim yapar. Bu nedenle
$$P_A(v\to v)=\frac{1}{d(v)+1},\qquad P_A(v\to u)=\frac{1}{d(v)+1}\quad\text{eğer }u\sim v.$$
Bu yürüyüş tersinirdir. Komşu iki oda \(u\) ve \(v\) için
$$\bigl(d(v)+1\bigr)P_A(v\to u)=1=\bigl(d(u)+1\bigr)P_A(u\to v).$$
Yani ayrıntılı denge, ağırlıkların \(d(v)+1\) ile orantılı olduğunu söyler. Normalize edince
$$\pi_A(v)=\frac{d(v)+1}{\sum_w \bigl(d(w)+1\bigr)}$$
elde edilir.
Kural B altında robot olasılığın yarısı ile yerinde kalır; kalan yarı ise \(d(v)\) komşuya eşit bölünür:
$$P_B(v\to v)=\frac12,\qquad P_B(v\to u)=\frac{1}{2d(v)}\quad\text{eğer }u\sim v.$$
Bu zincir de tersinirdir. Komşu \(u\) ve \(v\) için
$$d(v)\,P_B(v\to u)=\frac12=d(u)\,P_B(u\to v).$$
Böylece durağan dağılım
$$\pi_B(v)=\frac{d(v)}{\sum_w d(w)}$$
şeklindedir. Kural A bir odayı \(d(v)+1\) ile, kural B ise \(d(v)\) ile tartar.
Numaralar \(1\) ile \(N^2\) arasında olduğundan kare numaralar tam olarak \(1\le k\le N\) için \(k^2\) değerleridir. \(k^2\) etiketli odanın koordinatları
$$r_k=\left\lfloor\frac{k^2-1}{N}\right\rfloor+1,\qquad c_k=\bigl((k^2-1)\bmod N\bigr)+1$$
olur. Odanın derecesi sadece bu koordinatların sınırda olup olmamasına bağlıdır:
$$d_k= \begin{cases} 2,&\text{eğer }(r_k,c_k)\text{ köşeyse},\\ 3,&\text{eğer }(r_k,c_k)\text{ kenardaysa ama köşe değilse},\\ 4,&\text{eğer }(r_k,c_k)\text{ iç bölgedeyse}. \end{cases}$$
Şimdi
$$S=\sum_{k=1}^{N} d_k$$
tanımını yapalım. O zaman kural A için kare numaralı odaların toplam ağırlığı \(S+N\) olur; çünkü her hedef oda bir de kendi üzerinde kalma katkısı taşır.
Durağan dağılımları kullanarak kare numaralı odalardan birinde bulunma olasılığı kural A için
$$P_A(Q)=\sum_{k=1}^{N}\pi_A(k^2)=\frac{S+N}{5N^2-4N},$$
kural B için ise
$$P_B(Q)=\sum_{k=1}^{N}\pi_B(k^2)=\frac{S}{4N^2-4N}$$
olur. Sorulan nihai değer bu iki büyüklüğün aritmetik ortalamasıdır:
$$\boxed{P(Q)=\frac12\left(\frac{S+N}{5N^2-4N}+\frac{S}{4N^2-4N}\right).}$$
Yani tüm problem, \(S\) toplamını doğru bulmaya indirgenir.
\(5N^2-4N\) ve \(4N^2-4N\) paydaları kapalı formdadır; herhangi bir simülasyona gerek yoktur. Tek gerçek iş, her \(k^2\) karesini ele alıp satır-sütun koordinatına çevirmek, odanın köşe mi kenar mı iç bölge mi olduğunu belirlemek ve buna göre \(S\) toplamına \(2\), \(3\) veya \(4\) eklemektir. Uygulamalar tam olarak bunu yapar.
Kare numaralar \(1,4,9,16,25\) olur. Bunların koordinatları
$$1\mapsto(1,1),\qquad 4\mapsto(1,4),\qquad 9\mapsto(2,4),\qquad 16\mapsto(4,1),\qquad 25\mapsto(5,5)$$
şeklindedir. Dereceler sırasıyla \(2,3,4,3,2\) olduğundan
$$S=2+3+4+3+2=14,\qquad S+N=19$$
elde edilir. Tüm ızgara için
$$\sum_v d(v)=4\cdot 5\cdot 4=80,\qquad \sum_v\bigl(d(v)+1\bigr)=5\cdot 25-20=105.$$
Dolayısıyla
$$P_A(Q)=\frac{19}{105},\qquad P_B(Q)=\frac{14}{80}=\frac{7}{40},$$
ve son ortalama
$$P(Q)=\frac12\left(\frac{19}{105}+\frac{7}{40}\right)=\frac{299}{1680}=0.177976190476\ldots$$
olur. Bu, uygulamanın kullandığı doğrulama değeriyle aynıdır.
C++, Python ve Java uygulamaları aynı planı izler. Önce tüm \(N\times N\) ızgara için kapalı form toplamları hesaplarlar: köşe, kenar ve iç oda sayıları ile bunlardan türeyen iki durağan dağılım paydası. Sonra \(k=1,2,\dots,N\) döngüsüne girilir. Her adımda \(k^2\) etiketi oluşturulur, bu etiket satır ve sütun koordinatına çevrilir, ardından odanın üst, alt, sol veya sağ sınıra temas edip etmediği kontrol edilir. Bu sınır testlerinden oda derecesi \(2\), \(3\) ya da \(4\) olarak belirlenir; bu değer hedef toplamına eklenir ve kural A için bir ek birim daha sayılır.
Tek bir geçiş sonunda program, yukarıdaki formüllerde gereken iki payı da elinde bulundurur. Son adımda iki olasılık hesaplanır, ortalaması alınır ve sonuç on iki basamaklı ondalık olarak yazdırılır. Durağan dağılım ayrıntılı dengeden doğrudan çıktığı için matris üs alma, simülasyon veya iteratif yakınsama gerekmez.
Tüm ızgaraya ait küresel büyüklükler kapalı formüllerle sabit zamanda bulunur. Tek döngü, \(1\le k\le N\) için kare numaralar üzerinden bir kez geçer ve her adımda yalnızca birkaç tamsayı işlemi ile sınır karşılaştırması yapılır. Bu yüzden zaman karmaşıklığı \(O(N)\), ek bellek kullanımı ise \(O(1)\) olur.
Las habitaciones de un tablero \(N\times N\) están numeradas por filas como \(1,2,\dots,N^2\). Las habitaciones objetivo son las que tienen etiqueta cuadrada:
$$Q=\left\{1^2,2^2,\dots,N^2\right\}.$$
Un robot recorre este tablero bajo dos reglas aleatorias distintas. La cantidad pedida es la media aritmética entre la probabilidad estacionaria de estar en una habitación de \(Q\) con la regla A y la probabilidad estacionaria correspondiente con la regla B. La observación decisiva que usan las implementaciones es que ambas reglas producen cadenas de Markov reversibles sobre el mismo grafo de la cuadrícula, de modo que la distribución estacionaria depende solo del grado de cada habitación.
Modelamos el tablero como un grafo no dirigido. Cada habitación es un vértice y dos vértices están unidos cuando las habitaciones son vecinas ortogonales. Denotemos por \(d(v)\) el número de vecinos del vértice \(v\). En una cuadrícula cuadrada siempre se tiene \(d(v)\in\{2,3,4\}\): esquina, borde o interior.
Hay exactamente \(4\) esquinas, \(4(N-2)\) habitaciones de borde que no son esquinas y \((N-2)^2\) habitaciones interiores. Por tanto
$$\sum_{v} d(v)=2\cdot 4+3\cdot 4(N-2)+4(N-2)^2=4N(N-1).$$
Ese será el denominador de la segunda regla. Para la primera regla también necesitaremos
$$\sum_{v}\bigl(d(v)+1\bigr)=\sum_{v} d(v)+N^2=5N^2-4N=N(5N-4).$$
El término adicional \(+1\) corresponde a la posibilidad de quedarse en la misma habitación.
Bajo la regla A, el robot elige uniformemente entre todas las opciones legales: quedarse quieto o moverse a uno de los \(d(v)\) vecinos. Entonces
$$P_A(v\to v)=\frac{1}{d(v)+1},\qquad P_A(v\to u)=\frac{1}{d(v)+1}\quad\text{si }u\sim v.$$
Este paseo es reversible. Para habitaciones adyacentes \(u\) y \(v\),
$$\bigl(d(v)+1\bigr)P_A(v\to u)=1=\bigl(d(u)+1\bigr)P_A(u\to v).$$
Así, el equilibrio detallado se cumple con pesos proporcionales a \(d(v)+1\). Tras normalizar,
$$\pi_A(v)=\frac{d(v)+1}{\sum_w \bigl(d(w)+1\bigr)}.$$
Bajo la regla B, el robot se queda con probabilidad \(1/2\), y la otra mitad se reparte por igual entre los \(d(v)\) vecinos:
$$P_B(v\to v)=\frac12,\qquad P_B(v\to u)=\frac{1}{2d(v)}\quad\text{si }u\sim v.$$
Esta cadena también es reversible. Para vecinos \(u\) y \(v\),
$$d(v)\,P_B(v\to u)=\frac12=d(u)\,P_B(u\to v).$$
De aquí se obtiene la distribución estacionaria
$$\pi_B(v)=\frac{d(v)}{\sum_w d(w)}.$$
Por tanto, la regla A pondera una habitación con \(d(v)+1\), mientras que la regla B la pondera con \(d(v)\).
Como la numeración va de \(1\) a \(N^2\), las etiquetas cuadradas son exactamente \(k^2\) para \(1\le k\le N\). La habitación etiquetada con \(k^2\) tiene coordenadas
$$r_k=\left\lfloor\frac{k^2-1}{N}\right\rfloor+1,\qquad c_k=\bigl((k^2-1)\bmod N\bigr)+1.$$
Su grado depende solo de si esas coordenadas están en el borde:
$$d_k= \begin{cases} 2,&\text{si }(r_k,c_k)\text{ es una esquina},\\ 3,&\text{si }(r_k,c_k)\text{ está en el borde pero no en una esquina},\\ 4,&\text{si }(r_k,c_k)\text{ es interior}. \end{cases}$$
Definimos
$$S=\sum_{k=1}^{N} d_k.$$
Entonces el peso total de las habitaciones cuadradas bajo la regla A es \(S+N\), porque cada una de las \(N\) habitaciones objetivo aporta una unidad extra de permanencia.
Usando las distribuciones estacionarias, la probabilidad total de estar en una habitación cuadrada es
$$P_A(Q)=\sum_{k=1}^{N}\pi_A(k^2)=\frac{S+N}{5N^2-4N},$$
y para la regla B resulta
$$P_B(Q)=\sum_{k=1}^{N}\pi_B(k^2)=\frac{S}{4N^2-4N}.$$
La cantidad pedida es la media aritmética de ambas:
$$\boxed{P(Q)=\frac12\left(\frac{S+N}{5N^2-4N}+\frac{S}{4N^2-4N}\right).}$$
Una vez calculado \(S\), el problema queda resuelto.
Los denominadores globales \(5N^2-4N\) y \(4N^2-4N\) ya están en forma cerrada, así que no hace falta ninguna simulación. El único trabajo real consiste en recorrer las etiquetas \(k^2\), convertir cada una a fila y columna, decidir si la habitación es esquina, borde o interior, y añadir \(2\), \(3\) o \(4\) a la suma \(S\). Eso es exactamente lo que hacen las implementaciones.
Las etiquetas cuadradas son \(1,4,9,16,25\). Sus coordenadas son
$$1\mapsto(1,1),\qquad 4\mapsto(1,4),\qquad 9\mapsto(2,4),\qquad 16\mapsto(4,1),\qquad 25\mapsto(5,5).$$
Sus grados son \(2,3,4,3,2\), así que
$$S=2+3+4+3+2=14,\qquad S+N=19.$$
Para toda la cuadrícula,
$$\sum_v d(v)=4\cdot 5\cdot 4=80,\qquad \sum_v\bigl(d(v)+1\bigr)=5\cdot 25-20=105.$$
Por consiguiente,
$$P_A(Q)=\frac{19}{105},\qquad P_B(Q)=\frac{14}{80}=\frac{7}{40},$$
y el promedio final es
$$P(Q)=\frac12\left(\frac{19}{105}+\frac{7}{40}\right)=\frac{299}{1680}=0.177976190476\ldots$$
que coincide con el valor de validación usado por la implementación.
Las implementaciones en C++, Python y Java siguen exactamente la misma estrategia. Primero calculan las cantidades globales del tablero \(N\times N\): cuántas habitaciones son esquinas, cuántas son de borde y cuántas son interiores, y a partir de ahí obtienen los dos denominadores cerrados de las distribuciones estacionarias. Después recorren \(k=1,2,\dots,N\), forman la etiqueta cuadrada \(k^2\), convierten esa etiqueta a coordenadas de fila y columna y comprueban si la habitación toca el borde superior, inferior, izquierdo o derecho. Esas comprobaciones determinan si el grado es \(2\), \(3\) o \(4\), y ese valor se acumula en la suma de habitaciones cuadradas; para la regla A se añade además una unidad extra por la opción de quedarse.
Tras esa única pasada, el programa ya dispone de los dos numeradores necesarios. Solo queda dividir por los denominadores globales, promediar las dos probabilidades y mostrar el resultado con doce cifras decimales. No se usan simulaciones, potencias de matrices ni procesos iterativos, porque la distribución estacionaria se obtiene directamente a partir del equilibrio detallado.
Todas las cantidades globales del tablero completo se obtienen en tiempo constante mediante fórmulas cerradas. El único bucle recorre una vez los \(N\) valores \(k^2\), y cada iteración realiza solo unas pocas operaciones enteras y comparaciones de borde. Por ello, la complejidad temporal es \(O(N)\) y la memoria extra es \(O(1)\).
一个 \(N\times N\) 棋盘上的房间按行优先顺序编号为 \(1,2,\dots,N^2\)。我们关心的目标房间是平方编号的那些房间：
$$Q=\left\{1^2,2^2,\dots,N^2\right\}.$$
机器人会在这个棋盘上按照两种不同的随机规则移动。题目要求的是：在规则 A 下长期落在 \(Q\) 中房间的概率，与在规则 B 下长期落在 \(Q\) 中房间的概率，这两个值的算术平均。实现所利用的核心事实是，这两种规则都对应同一个网格图上的可逆马尔可夫链，因此稳态分布可以直接由每个房间的度数写出，而不需要做随机模拟。
把棋盘看成一个无向图。每个房间对应一个顶点，两个房间如果在上下或左右方向相邻，就在图中连一条边。记房间 \(v\) 的邻居数为 \(d(v)\)。对于方格棋盘来说，\(d(v)\) 只可能取 \(2\)、\(3\) 或 \(4\)，分别对应角落、边界和内部房间。
整张 \(N\times N\) 网格中，角落房间有 \(4\) 个，非角落边界房间有 \(4(N-2)\) 个，内部房间有 \((N-2)^2\) 个。因此全图所有度数之和为
$$\sum_{v} d(v)=2\cdot 4+3\cdot 4(N-2)+4(N-2)^2=4N(N-1).$$
这正是规则 B 的归一化分母。对于规则 A，我们还需要
$$\sum_{v}\bigl(d(v)+1\bigr)=\sum_{v} d(v)+N^2=5N^2-4N=N(5N-4).$$
这里额外的 \(+1\) 来自“停在原地”这一种选择。
规则 A 的含义是：如果机器人当前在房间 \(v\)，那么它会在“留在当前房间”以及“走向某个相邻房间”这些合法动作之间等概率选择。也就是说
$$P_A(v\to v)=\frac{1}{d(v)+1},\qquad P_A(v\to u)=\frac{1}{d(v)+1}\quad\text{当 }u\sim v.$$
这条链是可逆的。对任意相邻的两个房间 \(u\) 和 \(v\)，都有
$$\bigl(d(v)+1\bigr)P_A(v\to u)=1=\bigl(d(u)+1\bigr)P_A(u\to v).$$
因此详细平衡成立，稳态权重与 \(d(v)+1\) 成正比。规范化之后得到
$$\pi_A(v)=\frac{d(v)+1}{\sum_w \bigl(d(w)+1\bigr)}.$$
所以在规则 A 下，一个房间的重要性等于“邻居数再加一”。
规则 B 的含义是：机器人先用概率 \(1/2\) 决定留在原地，再把剩余的 \(1/2\) 平均分给所有相邻房间。因此
$$P_B(v\to v)=\frac12,\qquad P_B(v\to u)=\frac{1}{2d(v)}\quad\text{当 }u\sim v.$$
这条链同样可逆。对相邻房间 \(u\) 和 \(v\)，有
$$d(v)\,P_B(v\to u)=\frac12=d(u)\,P_B(u\to v).$$
于是规则 B 的稳态分布与 \(d(v)\) 成正比：
$$\pi_B(v)=\frac{d(v)}{\sum_w d(w)}.$$
换句话说，规则 A 给每个房间的权重是 \(d(v)+1\)，规则 B 给的权重是 \(d(v)\)。
因为房间编号从 \(1\) 到 \(N^2\)，所以不超过 \(N^2\) 的平方数恰好是 \(k^2\)，其中 \(1\le k\le N\)。编号为 \(k^2\) 的房间在棋盘上的行列坐标为
$$r_k=\left\lfloor\frac{k^2-1}{N}\right\rfloor+1,\qquad c_k=\bigl((k^2-1)\bmod N\bigr)+1.$$
这个房间的度数只取决于它是否贴着边界，因此
$$d_k= \begin{cases} 2,&\text{若 }(r_k,c_k)\text{ 是角落},\\ 3,&\text{若 }(r_k,c_k)\text{ 在边界上但不是角落},\\ 4,&\text{若 }(r_k,c_k)\text{ 在内部}. \end{cases}$$
定义平方编号房间的度数总和
$$S=\sum_{k=1}^{N} d_k.$$
那么在规则 A 下，这些目标房间的总权重就是 \(S+N\)，因为一共有 \(N\) 个目标房间，每个房间还多贡献一个“停留”单位。
由稳态分布直接得到，在规则 A 下长期落在平方编号房间中的总概率为
$$P_A(Q)=\sum_{k=1}^{N}\pi_A(k^2)=\frac{S+N}{5N^2-4N},$$
在规则 B 下则为
$$P_B(Q)=\sum_{k=1}^{N}\pi_B(k^2)=\frac{S}{4N^2-4N}.$$
题目要求这两个概率的算术平均，因此最终公式为
$$\boxed{P(Q)=\frac12\left(\frac{S+N}{5N^2-4N}+\frac{S}{4N^2-4N}\right).}$$
这说明问题已经被压缩成一个非常简单的任务：只要算出 \(S\) 就够了。
整个棋盘的两个分母 \(5N^2-4N\) 和 \(4N^2-4N\) 都已经有闭式表达，因此完全不需要模拟机器人走很多步。真正要做的唯一工作，是依次查看每个平方编号 \(k^2\)，把它转换成行列坐标，判断它是角落、边界还是内部房间，然后把 \(2\)、\(3\) 或 \(4\) 加入总和 \(S\)。这也是三种语言实现共同采用的核心算法。
当 \(N=5\) 时，平方编号房间是 \(1,4,9,16,25\)。它们对应的坐标分别是
$$1\mapsto(1,1),\qquad 4\mapsto(1,4),\qquad 9\mapsto(2,4),\qquad 16\mapsto(4,1),\qquad 25\mapsto(5,5).$$
于是对应度数依次为 \(2,3,4,3,2\)，从而
$$S=2+3+4+3+2=14,\qquad S+N=19.$$
而整张 \(5\times 5\) 网格的两个全局分母为
$$\sum_v d(v)=4\cdot 5\cdot 4=80,\qquad \sum_v\bigl(d(v)+1\bigr)=5\cdot 25-20=105.$$
因此
$$P_A(Q)=\frac{19}{105},\qquad P_B(Q)=\frac{14}{80}=\frac{7}{40},$$
最后的平均值就是
$$P(Q)=\frac12\left(\frac{19}{105}+\frac{7}{40}\right)=\frac{299}{1680}=0.177976190476\ldots$$
这正好与实现中使用的校验值一致。
C++、Python 和 Java 实现遵循同一套流程。首先，它们用闭式公式算出整个 \(N\times N\) 网格的全局统计量，也就是角落房间数、边界房间数、内部房间数，以及由此得到的两个稳态分布分母。接着程序遍历 \(k=1,2,\dots,N\)，构造平方编号 \(k^2\)，再把这个编号映射到对应的行和列。通过检查该位置是否位于上边界、下边界、左边界或右边界，程序就能判断它是角落、边界还是内部房间，并相应地把度数 \(2\)、\(3\) 或 \(4\) 加入平方房间的总权重；对于规则 A，还要额外加入每个目标房间的停留贡献。
完成这一趟遍历后，程序已经得到最终公式中的两个分子。最后只需分别除以两个全局分母，取平均，并把结果按十二位小数输出即可。由于稳态分布是由详细平衡直接推出的，所以这里完全不需要矩阵快速幂、蒙特卡洛模拟或迭代逼近。
整张网格的全局量都来自常数时间的闭式计算。唯一的循环只遍历 \(N\) 个平方编号 \(k^2\)，每一步只做少量整数运算和边界判断。因此时间复杂度是 \(O(N)\)，额外空间复杂度是 \(O(1)\)。
Комнаты на доске \(N\times N\) пронумерованы по строкам числами \(1,2,\dots,N^2\). Нас интересуют комнаты с квадратными номерами:
$$Q=\left\{1^2,2^2,\dots,N^2\right\}.$$
Робот движется по этой сетке по двум различным случайным правилам. Нужно взять среднее арифметическое двух стационарных вероятностей: вероятности находиться в комнате из \(Q\) по правилу A и вероятности находиться в комнате из \(Q\) по правилу B. Главная идея, лежащая в основе реализации, состоит в том, что обе модели задают обратимые цепи Маркова на одном и том же сеточном графе, поэтому стационарная мера выражается напрямую через степень вершины.
Представим доску как неориентированный граф. Каждая комната соответствует вершине, а ребро соединяет две комнаты, если они соседствуют по вертикали или горизонтали. Обозначим через \(d(v)\) число соседей вершины \(v\). Для квадратной сетки всегда \(d(v)\in\{2,3,4\}\): угол, край или внутренняя клетка.
У сетки ровно \(4\) угла, \(4(N-2)\) граничных клеток без углов и \((N-2)^2\) внутренних клеток. Поэтому
$$\sum_{v} d(v)=2\cdot 4+3\cdot 4(N-2)+4(N-2)^2=4N(N-1).$$
Это знаменатель для второго правила. Для первого правила нужно также
$$\sum_{v}\bigl(d(v)+1\bigr)=\sum_{v} d(v)+N^2=5N^2-4N=N(5N-4).$$
Добавка \(+1\) появляется из-за возможности остаться в той же комнате.
По правилу A робот равновероятно выбирает между всеми допустимыми действиями: остаться на месте или перейти в одного из \(d(v)\) соседей. Следовательно,
$$P_A(v\to v)=\frac{1}{d(v)+1},\qquad P_A(v\to u)=\frac{1}{d(v)+1}\quad\text{если }u\sim v.$$
Эта цепь обратима. Для любых соседних комнат \(u\) и \(v\) выполняется
$$\bigl(d(v)+1\bigr)P_A(v\to u)=1=\bigl(d(u)+1\bigr)P_A(u\to v).$$
Значит, условие detailed balance выполняется с весами, пропорциональными \(d(v)+1\). После нормировки получаем
$$\pi_A(v)=\frac{d(v)+1}{\sum_w \bigl(d(w)+1\bigr)}.$$
По правилу B робот с вероятностью \(1/2\) остается на месте, а оставшаяся половина делится поровну между соседями:
$$P_B(v\to v)=\frac12,\qquad P_B(v\to u)=\frac{1}{2d(v)}\quad\text{если }u\sim v.$$
Эта цепь тоже обратима. Для соседних \(u\) и \(v\) имеем
$$d(v)\,P_B(v\to u)=\frac12=d(u)\,P_B(u\to v).$$
Отсюда стационарное распределение пропорционально \(d(v)\):
$$\pi_B(v)=\frac{d(v)}{\sum_w d(w)}.$$
Итак, правило A взвешивает комнату коэффициентом \(d(v)+1\), а правило B коэффициентом \(d(v)\).
Поскольку номера комнат лежат в диапазоне от \(1\) до \(N^2\), квадратные номера имеют вид \(k^2\) при \(1\le k\le N\). Комната с номером \(k^2\) находится в координатах
$$r_k=\left\lfloor\frac{k^2-1}{N}\right\rfloor+1,\qquad c_k=\bigl((k^2-1)\bmod N\bigr)+1.$$
Ее степень зависит только от положения на границе:
$$d_k= \begin{cases} 2,&\text{если }(r_k,c_k)\text{ является углом},\\ 3,&\text{если }(r_k,c_k)\text{ лежит на границе, но не в углу},\\ 4,&\text{если }(r_k,c_k)\text{ находится внутри}. \end{cases}$$
Обозначим
$$S=\sum_{k=1}^{N} d_k.$$
Тогда суммарный вес всех комнат из \(Q\) для правила A равен \(S+N\), потому что каждая из \(N\) целевых комнат получает еще единичный вклад от возможности остаться на месте.
Из стационарных распределений сразу следует, что общая вероятность попасть в комнату с квадратным номером равна
$$P_A(Q)=\sum_{k=1}^{N}\pi_A(k^2)=\frac{S+N}{5N^2-4N},$$
а для правила B
$$P_B(Q)=\sum_{k=1}^{N}\pi_B(k^2)=\frac{S}{4N^2-4N}.$$
Задача просит взять их среднее арифметическое, то есть
$$\boxed{P(Q)=\frac12\left(\frac{S+N}{5N^2-4N}+\frac{S}{4N^2-4N}\right).}$$
После нахождения \(S\) задача полностью решена.
Глобальные знаменатели \(5N^2-4N\) и \(4N^2-4N\) уже известны в замкнутом виде, поэтому моделирование случайного процесса не нужно. Вся содержательная работа сводится к тому, чтобы по очереди рассмотреть каждое квадратное число \(k^2\), перевести его в номер строки и столбца, определить, является ли соответствующая комната угловой, граничной или внутренней, и прибавить к сумме \(S\) число \(2\), \(3\) или \(4\). Именно это и делают реализации.
Квадратные номера равны \(1,4,9,16,25\). Их координаты:
$$1\mapsto(1,1),\qquad 4\mapsto(1,4),\qquad 9\mapsto(2,4),\qquad 16\mapsto(4,1),\qquad 25\mapsto(5,5).$$
Соответствующие степени равны \(2,3,4,3,2\), поэтому
$$S=2+3+4+3+2=14,\qquad S+N=19.$$
Для всей сетки получаем
$$\sum_v d(v)=4\cdot 5\cdot 4=80,\qquad \sum_v\bigl(d(v)+1\bigr)=5\cdot 25-20=105.$$
Значит,
$$P_A(Q)=\frac{19}{105},\qquad P_B(Q)=\frac{14}{80}=\frac{7}{40},$$
и итоговое среднее равно
$$P(Q)=\frac12\left(\frac{19}{105}+\frac{7}{40}\right)=\frac{299}{1680}=0.177976190476\ldots$$
Это точно совпадает с контрольным значением, используемым в реализации.
Реализации на C++, Python и Java устроены одинаково. Сначала они вычисляют замкнутые формулы для всего поля \(N\times N\): число угловых, граничных и внутренних комнат, а затем из этих величин получают два глобальных знаменателя стационарных распределений. После этого выполняется цикл по \(k=1,2,\dots,N\). На каждом шаге строится квадратный номер \(k^2\), он переводится в координаты строки и столбца, затем проверяется, касается ли соответствующая комната верхней, нижней, левой или правой границы. Эти проверки однозначно определяют степень \(2\), \(3\) или \(4\), которая прибавляется к сумме квадратных комнат; для правила A дополнительно учитывается единичный вклад от возможности не двигаться.
После одного такого прохода программа уже знает оба числителя из формулы. Остается разделить их на глобальные знаменатели, усреднить две вероятности и вывести ответ с точностью до двенадцати знаков после запятой. Никаких симуляций, степеней матриц или итерационных методов не требуется, потому что стационарное распределение сразу получается из detailed balance.
Все величины, относящиеся ко всей сетке, находятся за \(O(1)\) по замкнутым формулам. Единственный цикл проходит по \(N\) квадратным номерам \(k^2\), а каждая итерация выполняет лишь несколько целочисленных операций и проверок границы. Следовательно, время работы равно \(O(N)\), а дополнительная память равна \(O(1)\).
غرف اللوح \(N\times N\) مرقمة ترتيبًا صفّيًا بالأعداد \(1,2,\dots,N^2\). الغرف المستهدفة هي الغرف ذات الأرقام المربعة:
$$Q=\left\{1^2,2^2,\dots,N^2\right\}.$$
يتحرك الروبوت على هذا اللوح وفق قاعدتين عشوائيتين مختلفتين. المطلوب هو المتوسط الحسابي لاحتمال الاستقرار في غرفة من \(Q\) تحت القاعدة A واحتمال الاستقرار في غرفة من \(Q\) تحت القاعدة B. الفكرة الأساسية التي تعتمد عليها التطبيقات هي أن كلتا الحالتين تمثلان سلسلتَي ماركوف قابلتين للعكس على الرسم البياني الشبكي نفسه، ولذلك يمكن كتابة التوزيع المستقر مباشرة بدلالة درجة كل غرفة.
نمثل اللوح على أنه رسم بياني غير موجه. كل غرفة تمثل رأسًا، ويوجد ضلع بين غرفتين إذا كانتا متجاورتين أفقيًا أو عموديًا. لنرمز بعدد جيران الغرفة \(v\) بالرمز \(d(v)\). في الشبكة المربعة لا يمكن أن تأخذ \(d(v)\) إلا القيم \(2\) أو \(3\) أو \(4\)، وهي تمثل على الترتيب الزوايا والحواف والداخل.
يوجد بالضبط \(4\) زوايا، و\(4(N-2)\) غرف على الحافة ليست زوايا، و\((N-2)^2\) غرف داخلية. لذلك يكون
$$\sum_{v} d(v)=2\cdot 4+3\cdot 4(N-2)+4(N-2)^2=4N(N-1).$$
وهذا هو مقام القاعدة الثانية. أما في القاعدة الأولى فنحتاج أيضًا إلى
$$\sum_{v}\bigl(d(v)+1\bigr)=\sum_{v} d(v)+N^2=5N^2-4N=N(5N-4).$$
والزيادة \(+1\) هنا تمثل خيار البقاء في الغرفة نفسها.
في القاعدة A يختار الروبوت بشكل منتظم بين جميع الخيارات المسموح بها: البقاء في مكانه أو الانتقال إلى أحد الجيران \(d(v)\). وعليه فإن
$$P_A(v\to v)=\frac{1}{d(v)+1},\qquad P_A(v\to u)=\frac{1}{d(v)+1}\quad(u\sim v).$$
هذه السلسلة قابلة للعكس. فلكل غرفتين متجاورتين \(u\) و\(v\) لدينا
$$\bigl(d(v)+1\bigr)P_A(v\to u)=1=\bigl(d(u)+1\bigr)P_A(u\to v).$$
إذًا يتحقق التوازن التفصيلي مع أوزان تتناسب مع \(d(v)+1\). وبعد التطبيع نحصل على
$$\pi_A(v)=\frac{d(v)+1}{\sum_w \bigl(d(w)+1\bigr)}.$$
في القاعدة B يبقى الروبوت في مكانه باحتمال \(1/2\)، أما النصف الآخر فيتوزع بالتساوي على الجيران:
$$P_B(v\to v)=\frac12,\qquad P_B(v\to u)=\frac{1}{2d(v)}\quad(u\sim v).$$
وهذه السلسلة قابلة للعكس أيضًا. ولأي غرفتين متجاورتين \(u\) و\(v\) نجد أن
$$d(v)\,P_B(v\to u)=\frac12=d(u)\,P_B(u\to v).$$
ومن هنا يكون التوزيع المستقر متناسبًا مع \(d(v)\):
$$\pi_B(v)=\frac{d(v)}{\sum_w d(w)}.$$
أي إن القاعدة A تعطي وزنًا مقداره \(d(v)+1\)، بينما القاعدة B تعطي وزنًا مقداره \(d(v)\).
بما أن الترقيم يمتد من \(1\) إلى \(N^2\)، فإن الأعداد المربعة الممكنة هي بالضبط \(k^2\) عندما \(1\le k\le N\). والغرفة ذات الرقم \(k^2\) تقع عند الإحداثيين
$$r_k=\left\lfloor\frac{k^2-1}{N}\right\rfloor+1,\qquad c_k=\bigl((k^2-1)\bmod N\bigr)+1.$$
ودرجة هذه الغرفة تعتمد فقط على كونها عند الحد أو في الداخل:
$$d_k= \begin{cases} 2,&(r_k,c_k)\text{ is a corner},\\ 3,&(r_k,c_k)\text{ is an edge but not a corner},\\ 4,&(r_k,c_k)\text{ is interior}. \end{cases}$$
لنعرف الآن
$$S=\sum_{k=1}^{N} d_k.$$
عندئذ يكون مجموع الأوزان الخاصة بالغرف المستهدفة في القاعدة A مساويًا لـ \(S+N\)، لأن كل واحدة من الغرف المستهدفة وعددها \(N\) تضيف وحدة إضافية ناتجة عن خيار البقاء.
من التوزيعين المستقرين نحصل مباشرة على أن احتمال الوجود طويل الأمد في غرفة ذات رقم مربع تحت القاعدة A هو
$$P_A(Q)=\sum_{k=1}^{N}\pi_A(k^2)=\frac{S+N}{5N^2-4N},$$
أما تحت القاعدة B فهو
$$P_B(Q)=\sum_{k=1}^{N}\pi_B(k^2)=\frac{S}{4N^2-4N}.$$
والكمية المطلوبة في المسألة هي المتوسط الحسابي لهذين المقدارين:
$$\boxed{P(Q)=\frac12\left(\frac{S+N}{5N^2-4N}+\frac{S}{4N^2-4N}\right).}$$
وبذلك تختزل المسألة كلها إلى حساب المجموع \(S\).
المقامات العالمية \(5N^2-4N\) و\(4N^2-4N\) معروفة بصيغ مغلقة، لذلك لا حاجة إلى محاكاة الحركة العشوائية. العمل الحقيقي الوحيد هو المرور على كل عدد مربع \(k^2\)، وتحويله إلى صف وعمود، وتحديد ما إذا كانت الغرفة زاوية أو على الحافة أو داخلية، ثم إضافة \(2\) أو \(3\) أو \(4\) إلى المجموع \(S\). وهذا بالضبط ما تقوم به التطبيقات.
عندما \(N=5\) تكون الأرقام المربعة هي \(1,4,9,16,25\)، وإحداثياتها هي
$$1\mapsto(1,1),\qquad 4\mapsto(1,4),\qquad 9\mapsto(2,4),\qquad 16\mapsto(4,1),\qquad 25\mapsto(5,5).$$
إذن درجاتها هي \(2,3,4,3,2\)، ومن ثم
$$S=2+3+4+3+2=14,\qquad S+N=19.$$
أما على مستوى الشبكة كلها فنحصل على
$$\sum_v d(v)=4\cdot 5\cdot 4=80,\qquad \sum_v\bigl(d(v)+1\bigr)=5\cdot 25-20=105.$$
إذًا
$$P_A(Q)=\frac{19}{105},\qquad P_B(Q)=\frac{14}{80}=\frac{7}{40},$$
وبالتالي يكون المتوسط النهائي
$$P(Q)=\frac12\left(\frac{19}{105}+\frac{7}{40}\right)=\frac{299}{1680}=0.177976190476\ldots$$
وهذا يطابق قيمة التحقق المستعملة في التنفيذ.
تتبع تطبيقات C++ وPython وJava الخطة نفسها. أولًا تحسب الصيغ المغلقة الخاصة بالشبكة \(N\times N\): عدد غرف الزوايا، وعدد غرف الحواف، وعدد الغرف الداخلية، ثم تستخرج من ذلك مقامي التوزيعين المستقرين. بعد ذلك تنفذ حلقة على \(k=1,2,\dots,N\). في كل تكرار تكوّن العدد المربع \(k^2\)، ثم تحول هذا الرقم إلى إحداثيات صف وعمود، وبعدها تتحقق مما إذا كانت الغرفة تقع على الحد العلوي أو السفلي أو الأيسر أو الأيمن. هذه الاختبارات تحدد ما إذا كانت الدرجة \(2\) أو \(3\) أو \(4\)، ويضاف هذا المقدار إلى مجموع الغرف المربعة، كما يضاف أيضًا في القاعدة A مقدار واحد إضافي يمثل خيار البقاء.
بعد هذه الدورة الواحدة يصبح لدى البرنامج البسطان المطلوبان في الصيغة النهائية. ثم يقسم كل بسط على مقامه العالمي، ويأخذ المتوسط الحسابي، ويطبع النتيجة بدقة اثني عشر رقمًا عشريًا. لا توجد حاجة إلى محاكاة، أو إلى أسس مصفوفات، أو إلى تقارب تكراري، لأن التوزيع المستقر يُستنتج مباشرة من التوازن التفصيلي.
كل الكميات الخاصة بالشبكة الكاملة تُحسب في زمن ثابت باستخدام صيغ مغلقة. الحلقة الوحيدة تمر على \(N\) عددًا مربعًا فقط، وكل خطوة فيها تحتوي على عدد صغير من العمليات الصحيحة ومقارنات حدودية. لذلك يكون الزمن \(O(N)\)، وتكون الذاكرة الإضافية \(O(1)\).