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.
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.
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.
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.
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).}$$
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.
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.
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)\).
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.
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.
Auf einem \(30\times 30\)-Brett sitzt anfangs in jedem Feld genau ein Floh, also insgesamt \(900\) Flöhe. Bei jedem Glockenschlag springt jeder Floh gleichzeitig in eines seiner orthogonal benachbarten Felder, gleichverteilt über alle gültigen Nachbarn. Eckfelder haben daher Grad \(2\), Randfelder Grad \(3\) und innere Felder Grad \(4\).
Nach \(50\) Sprüngen dürfen mehrere Flöhe im selben Feld landen, während andere Felder leer bleiben. Gesucht ist der Erwartungswert der Anzahl leerer Felder auf sechs Nachkommastellen. Eine direkte Beschreibung aller \(900\) Flöhe gemeinsam wäre viel zu groß; die Lösung trennt deshalb die einzelnen Zufallswege und setzt sie erst am Ende wieder zusammen.
Der natürliche Zugang ist ein Random Walk auf dem Gittergraphen. Man betrachtet nicht alle Flöhe gleichzeitig, sondern berechnet für jedes Startfeld separat die Aufenthaltswahrscheinlichkeiten nach \(50\) Schritten.
Sei \(V\) die Menge der \(900\) Felder und \(\deg(u)\in\{2,3,4\}\) die Zahl der gültigen Nachbarn von \(u\). Für einen Floh mit Startfeld \(s\) definieren wir
$$p_s^{(t)}(v)=\mathbb{P}(\text{der Floh steht nach }t\text{ Glockenschlägen auf }v).$$
Am Anfang ist die Verteilung punktförmig:
$$p_s^{(0)}(v)= \begin{cases} 1,& v=s,\\ 0,& v\ne s. \end{cases}$$
Ein weiterer Schritt verteilt die aktuelle Wahrscheinlichkeit gleichmäßig auf die Nachbarn. Mit \(u\sim v\) für benachbarte Felder gilt daher
$$p_s^{(t+1)}(v)=\sum_{u\sim v}\frac{p_s^{(t)}(u)}{\deg(u)}.$$
Genau diese Rekursion wird implementiert. Zugleich bleibt
$$\sum_{v\in V} p_s^{(t)}(v)=1$$
für jedes \(t\) erhalten; die Verteilung eines einzelnen Flohs verliert also nie Wahrscheinlichkeitsmasse.
Fixiere nun ein Zielfeld \(v\). Für jedes Startfeld \(s\) ist die Wahrscheinlichkeit, dass der dort gestartete Floh nach \(50\) Schritten nicht in \(v\) liegt, gleich \(1-p_s^{(50)}(v)\). Da die Flöhe unabhängig voneinander springen, dürfen wir für dieses feste Zielfeld multiplizieren:
$$\mathbb{P}(v\text{ ist nach 50 Glockenschlägen leer})=\prod_{s\in V}\left(1-p_s^{(50)}(v)\right).$$
Damit umgeht man jede Fallunterscheidung über Kollisionen. Für die Leere eines Feldes ist nur relevant, ob der einzelne Floh dort ankommt oder nicht.
Sei \(I_v\) die Indikatorvariable dafür, dass \(v\) leer ist:
$$I_v= \begin{cases} 1,& v\text{ ist leer},\\ 0,& v\text{ ist besetzt}. \end{cases}$$
Dann ist die Gesamtzahl leerer Felder
$$X=\sum_{v\in V} I_v.$$
Die Ereignisse für verschiedene Zielfelder sind nicht unabhängig, aber das ist egal, denn
$$\mathbb{E}[X]=\sum_{v\in V}\mathbb{E}[I_v]=\sum_{v\in V}\mathbb{P}(v\text{ ist leer}).$$
Mit der Produktformel folgt unmittelbar die zentrale Gleichung der Lösung:
$$\boxed{\mathbb{E}[X]=\sum_{v\in V}\prod_{s\in V}\left(1-p_s^{(50)}(v)\right).}$$
Dieses Mini-Beispiel ist nützlich, weil es genau den eingebauten Kontrollfall der Implementierung reproduziert. Auf einem \(2\times 2\)-Brett ist jedes Feld eine Ecke und hat genau zwei Nachbarn. Fixiere ein Zielfeld \(v\). Nach einem Schritt können nur die beiden angrenzenden Startflöhe in \(v\) landen, jeweils mit Wahrscheinlichkeit \(1/2\). Der Floh aus \(v\) selbst muss wegziehen, und der diagonal gegenüberliegende Floh kann \(v\) in einem Schritt nicht erreichen. Also
$$\mathbb{P}(v\text{ leer})=\left(1-\frac12\right)\left(1-\frac12\right)\left(1-0\right)\left(1-0\right)=\frac14.$$
Alle vier Felder sind symmetrisch, also
$$\mathbb{E}[X]=4\cdot\frac14=1.$$
Dasselbe Prinzip gilt unverändert auf dem \(30\times 30\)-Brett; nur die Übergangstabellen werden größer.
Die C++-, Python- und Java-Implementierungen nummerieren die \(900\) Felder durch und erzeugen für jedes Feld seine Nachbarschaftsliste. Damit ist die Gradstruktur \(2/3/4\) des Brettes vollständig festgelegt.
Für ein Startfeld \(s\) beginnt die Wahrscheinlichkeitsverteilung mit Masse \(1\) in \(s\) und \(0\) sonst. Danach werden \(50\) Runden der Rekursion ausgeführt. Die Implementierung verwendet dabei immer nur zwei Vektoren, einen für die aktuelle und einen für die nächste Schicht. Nach Runde \(50\) enthält der aktuelle Vektor genau die Werte \(p_s^{(50)}(v)\) für alle Zielfelder \(v\).
Zusätzlich wird für jedes Zielfeld \(v\) ein laufendes Produkt gespeichert. Nach der Berechnung für ein Startfeld wird der Faktor \(1-p_s^{(50)}(v)\) für alle \(v\) eingemultipliziert. Nach allen \(900\) Starts ist jeder Eintrag bereits die Wahrscheinlichkeit, dass das entsprechende Feld nach \(50\) Glockenschlägen leer ist.
Zum Schluss werden diese \(900\) Werte aufsummiert; das Ergebnis ist der gesuchte Erwartungswert.
Sei \(n\) die Seitenlänge und \(N=n^2\) die Anzahl der Felder. Der Aufbau der Nachbarschaftslisten benötigt \(O(N)\) Zeit und \(O(N)\) Speicher, weil jedes Feld höchstens vier Nachbarn besitzt.
Für jedes der \(N\) Startfelder führt der Algorithmus \(T\) Diffusionsrunden aus, und jede Runde verarbeitet alle \(N\) Felder mit konstantem Aufwand pro Kante. Insgesamt ergibt das \(O(TN^2)\) Zeit. Mit \(N=n^2\) ist das gleich \(O(Tn^4)\).
Der Arbeitsspeicher bleibt \(O(N)\): eine lineare Adjazenzstruktur, ein Akkumulator für die Leerwahrscheinlichkeiten und zwei wiederverwendete Verteilungsvektoren. Für die tatsächlichen Werte \(n=30\) und \(T=50\) ist dieses dynamische Programm problemlos praktikabel.
\(30\times 30\) bir tahtada başlangıçta her hücrede tam bir pire vardır; toplam pire sayısı \(900\)'dür. Her zil çaldığında tüm pireler aynı anda, bulundukları hücrenin geçerli dik komşularından birine eşit olasılıkla zıplar. Bu yüzden köşelerde derece \(2\), kenarlarda derece \(3\), iç bölgede ise derece \(4\) vardır.
\(50\) zil sonrasında bazı hücrelerde birden fazla pire bulunabilir, bazı hücreler ise boş kalabilir. İstenen, boş hücre sayısının beklenen değerini altı ondalık basamakla bulmaktır. \(900\) piresinin ortak durum uzayını doğrudan izlemek imkansız olduğundan çözüm, bağımsız tek-pire yürüyüşlerini ayrı ayrı hesaplayıp sonunda birleştirir.
Doğru model, ızgara grafı üzerindeki bir rassal yürüyüştür. Tüm pireleri birlikte izlemek yerine her başlangıç hücresi için tek bir pirenin \(50\) adım sonraki dağılımı hesaplanır.
\(V\), tahtadaki \(900\) hücrenin kümesi olsun. Bir hücre \(u\) için \(\deg(u)\in\{2,3,4\}\), geçerli komşu sayısını göstersin. \(s\) hücresinden başlayan bir pire için
$$p_s^{(t)}(v)=\mathbb{P}(\text{pire }t\text{ zil sonra }v\text{ hücresinde})$$
tanımını yapalım. Başlangıç durumu tek noktada yoğundur:
$$p_s^{(0)}(v)= \begin{cases} 1,& v=s,\\ 0,& v\ne s. \end{cases}$$
Eğer \(u\sim v\), \(u\) ile \(v\)'nin dik komşu olduğunu gösteriyorsa, bir sonraki adım için geçiş bağıntısı
$$p_s^{(t+1)}(v)=\sum_{u\sim v}\frac{p_s^{(t)}(u)}{\deg(u)}$$
olur. Kodun yaptığı tam olarak budur: her hücre, mevcut olasılık kütlesini komşularına eşit paylaştırır. Ayrıca şu değişmez hep korunur:
$$\sum_{v\in V} p_s^{(t)}(v)=1.$$
Yani her ara dağılım gerçek bir olasılık dağılımıdır.
Şimdi sabit bir hedef hücre \(v\) seçelim. Başlangıç hücresi \(s\) olan piresinin \(50\) zil sonunda \(v\)'de olmama olasılığı \(1-p_s^{(50)}(v)\)'dir. Farklı pirelerin hareketleri bağımsız olduğu için, bu sabit hedef için tüm çarpanlar çarpılabilir:
$$\mathbb{P}(v\text{ hücresi 50 zil sonunda boş})=\prod_{s\in V}\left(1-p_s^{(50)}(v)\right).$$
Bu formül problemin merkezidir. Aynı hücreye kaç piresinin çarptığını tek tek incelemek gerekmez; her bağımsız piresinin oraya gelip gelmediğini bilmek yeterlidir.
\(I_v\), \(v\) hücresinin boş olma göstergesi olsun:
$$I_v= \begin{cases} 1,& v\text{ boş},\\ 0,& v\text{ dolu}. \end{cases}$$
Toplam boş hücre sayısı
$$X=\sum_{v\in V} I_v$$
şeklindedir. Farklı hücrelerin boş olma olayları bağımsız değildir; fakat beklenen değer için buna ihtiyaç yoktur:
$$\mathbb{E}[X]=\sum_{v\in V}\mathbb{E}[I_v]=\sum_{v\in V}\mathbb{P}(v\text{ boş}).$$
Üstteki çarpım formülünü yerleştirince çözümün doğrudan hesapladığı kapalı ifade elde edilir:
$$\boxed{\mathbb{E}[X]=\sum_{v\in V}\prod_{s\in V}\left(1-p_s^{(50)}(v)\right).}$$
Bu küçük örnek, uygulamadaki kontrol testini de açıkladığı için özellikle faydalıdır. \(2\times 2\) tahtada her hücre bir köşedir ve tam iki komşusu vardır. Bir hedef hücre \(v\) sabitlensin. Bir adım sonra yalnızca ona bitişik iki başlangıç piresi \(v\)'ye gelebilir; her biri bunu \(1/2\) olasılıkla yapar. \(v\)'de başlayan pire oradan ayrılmak zorundadır, çapraz köşedeki pire ise bir adımda \(v\)'ye ulaşamaz. Dolayısıyla
$$\mathbb{P}(v\text{ boş})=\left(1-\frac12\right)\left(1-\frac12\right)\left(1-0\right)\left(1-0\right)=\frac14.$$
Dört hücre de simetrik olduğundan
$$\mathbb{E}[X]=4\cdot\frac14=1$$
çıkar. \(30\times 30\) durumunda da mantık tamamen aynıdır; yalnızca olasılık tabloları daha büyüktür.
C++, Python ve Java uygulamaları önce \(30\times 30\) tahtayı \(900\) düğüm olarak numaralandırır ve her hücre için komşu listesini üretir. Böylece köşe, kenar ve iç hücrelerin farklı derece yapısı açıkça kodlanmış olur.
Bir başlangıç hücresi \(s\) seçildiğinde olasılık vektörü sadece \(s\)'de \(1\), diğer yerlerde \(0\) olacak şekilde başlatılır. Sonra yukarıdaki geçiş bağıntısı \(50\) kez uygulanır. Uygulama her turda yalnızca iki dizi kullanır: biri mevcut dağılım, diğeri bir sonraki dağılım içindir. Elli turun sonunda elde edilen vektör, tüm hedef hücreler için \(p_s^{(50)}(v)\) değerlerini içerir.
Ayrı bir dizide her hedef hücre \(v\) için koşan çarpım tutulur. Bir başlangıç hücresinin yayılımı tamamlanınca, bütün hedefler için ilgili çarpana \(1-p_s^{(50)}(v)\) eklenir. Tüm \(900\) başlangıç işlendiğinde her giriş artık o hücrenin \(50\) zil sonunda boş kalma olasılığıdır.
Son aşama basittir: bu \(900\) olasılık toplanır ve boş hücre sayısının beklenen değeri elde edilir.
Tahtanın kenar uzunluğu \(n\), toplam hücre sayısı \(N=n^2\) olsun. Komşuluk listesini kurmak \(O(N)\) zaman ve \(O(N)\) bellek gerektirir; çünkü her hücrenin en fazla dört komşusu vardır.
Algoritma, \(N\) farklı başlangıç hücresinin her biri için \(T\) yayılım turu çalıştırır. Her tur tüm \(N\) hücreyi sabit dereceli geçişlerle güncellediğinden toplam süre \(O(TN^2)\) olur. \(N=n^2\) yazılırsa bu \(O(Tn^4)\)'e eşittir.
Çalışma belleği \(O(N)\) düzeyinde kalır: doğrusal boyutlu komşuluk yapısı, boşluk olasılıklarını tutan bir dizi ve tekrar kullanılan iki dağılım vektörü. Gerçek parametreler \(n=30\) ve \(T=50\) için bu yöntem rahatlıkla uygulanabilir.
En un tablero de \(30\times 30\) hay inicialmente una pulga en cada casilla, es decir, \(900\) pulgas en total. Cada vez que suena la campana, todas saltan al mismo tiempo hacia una casilla ortogonal vecina elegida uniformemente entre las permitidas. Las esquinas tienen por tanto grado \(2\), los bordes grado \(3\) y el interior grado \(4\).
Después de \(50\) campanadas, varias pulgas pueden coincidir en la misma casilla y otras casillas pueden quedar vacías. Se pide el valor esperado del número de casillas vacías, con seis decimales. El espacio de estados conjunto de las \(900\) pulgas es inabordable, así que la solución separa el movimiento de una sola pulga y solo combina la información al final.
La formulación correcta es un paseo aleatorio en el grafo de la cuadrícula. En vez de seguir a las \(900\) pulgas simultáneamente, calculamos la distribución final de una pulga para cada casilla de origen.
Sea \(V\) el conjunto de las \(900\) casillas, y sea \(\deg(u)\in\{2,3,4\}\) el número de vecinos válidos de la casilla \(u\). Para una pulga que empieza en \(s\), definimos
$$p_s^{(t)}(v)=\mathbb{P}(\text{la pulga está en }v\text{ tras }t\text{ campanadas}).$$
La condición inicial es
$$p_s^{(0)}(v)= \begin{cases} 1,& v=s,\\ 0,& v\ne s. \end{cases}$$
Si escribimos \(u\sim v\) cuando \(u\) y \(v\) son vecinos ortogonales, la transición de un paso es
$$p_s^{(t+1)}(v)=\sum_{u\sim v}\frac{p_s^{(t)}(u)}{\deg(u)}.$$
Eso es exactamente lo que implementa el programa: cada casilla reparte su masa de probabilidad por igual entre sus vecinos. Además, se conserva el invariante
$$\sum_{v\in V} p_s^{(t)}(v)=1,$$
de modo que cada capa sigue siendo una distribución de probabilidad válida.
Fijemos ahora una casilla objetivo \(v\). Para cada origen \(s\), la probabilidad de que la pulga que salió de \(s\) no esté en \(v\) después de \(50\) pasos es \(1-p_s^{(50)}(v)\). Como las pulgas se mueven de forma independiente, para esta casilla objetivo podemos multiplicar:
$$\mathbb{P}(v\text{ queda vacía tras 50 campanadas})=\prod_{s\in V}\left(1-p_s^{(50)}(v)\right).$$
Esta identidad es el núcleo del problema. No hace falta describir cuántas pulgas chocan en la misma casilla; basta saber si cada pulga independiente llega o no llega allí.
Sea \(I_v\) la variable indicadora de que la casilla \(v\) está vacía:
$$I_v= \begin{cases} 1,& v\text{ está vacía},\\ 0,& v\text{ está ocupada}. \end{cases}$$
El número total de casillas vacías es
$$X=\sum_{v\in V} I_v.$$
Los eventos de vaciedad de distintas casillas no son independientes, pero la esperanza sigue siendo lineal:
$$\mathbb{E}[X]=\sum_{v\in V}\mathbb{E}[I_v]=\sum_{v\in V}\mathbb{P}(v\text{ está vacía}).$$
Al sustituir la fórmula anterior obtenemos la expresión final que calculan las implementaciones:
$$\boxed{\mathbb{E}[X]=\sum_{v\in V}\prod_{s\in V}\left(1-p_s^{(50)}(v)\right).}$$
Este caso pequeño es útil porque coincide con la comprobación interna del programa. En un tablero \(2\times 2\), cada casilla es una esquina y tiene exactamente dos vecinos. Fijemos una casilla objetivo \(v\). Tras una campanada, solo las dos pulgas adyacentes pueden llegar a \(v\), cada una con probabilidad \(1/2\). La pulga que comenzó en \(v\) está obligada a salir, y la pulga de la esquina opuesta no puede alcanzar \(v\) en un solo salto. Por tanto,
$$\mathbb{P}(v\text{ vacía})=\left(1-\frac12\right)\left(1-\frac12\right)\left(1-0\right)\left(1-0\right)=\frac14.$$
Las cuatro casillas son simétricas, así que
$$\mathbb{E}[X]=4\cdot\frac14=1.$$
El problema real de \(30\times 30\) usa exactamente la misma idea, solo que con una tabla de difusión mucho más grande.
Las implementaciones en C++, Python y Java numeran primero las \(900\) casillas y construyen la lista de vecinos de cada una. Así queda fijada la estructura de grados \(2/3/4\) de esquinas, bordes e interior.
Para cada origen \(s\), la distribución de probabilidad comienza con masa \(1\) en \(s\) y \(0\) en las demás casillas. Luego se aplican \(50\) rondas de la recurrencia anterior. La implementación reutiliza dos arreglos: uno para la capa actual y otro para la siguiente. Tras la ronda 50, el arreglo actual contiene todos los valores \(p_s^{(50)}(v)\).
Se mantiene además un arreglo separado con el producto acumulado para cada casilla objetivo \(v\). Cuando termina la difusión de un origen \(s\), se multiplica el factor \(1-p_s^{(50)}(v)\) en todas las casillas objetivo. Después de procesar los \(900\) orígenes, cada entrada ya es la probabilidad de que esa casilla esté vacía después de \(50\) campanadas.
La última operación es sumar esas \(900\) probabilidades para obtener el valor esperado pedido.
Sea \(n\) la longitud del lado y \(N=n^2\) el número de casillas. Construir la lista de vecinos cuesta \(O(N)\) tiempo y \(O(N)\) memoria, porque cada casilla tiene a lo sumo cuatro vecinos.
Para cada una de las \(N\) casillas de origen, el algoritmo ejecuta \(T\) rondas de difusión, y cada ronda recorre las \(N\) casillas con actualizaciones de grado constante. El tiempo total es, por tanto, \(O(TN^2)\). Como \(N=n^2\), esto equivale a \(O(Tn^4)\).
La memoria de trabajo permanece en \(O(N)\): una estructura de adyacencia lineal, un acumulador para las probabilidades de vaciedad y dos vectores reutilizables para las capas de difusión. Para los parámetros reales \(n=30\) y \(T=50\), este método es perfectamente manejable.
在一个 \(30\times 30\) 的棋盘上，初始时每个格子里恰好有一只跳蚤，因此总共有 \(900\) 只跳蚤。每次铃声响起时，所有跳蚤同时行动，并且各自以相同概率跳向一个合法的上下左右相邻格子。所以角格的度数是 \(2\)，边格是 \(3\)，内部格子是 \(4\)。
经过 \(50\) 次铃声后，某些格子里可能堆了多只跳蚤，另一些格子则可能为空。题目要求的是空格数量的期望值，并保留六位小数。直接跟踪 \(900\) 只跳蚤的联合状态几乎不可能，因此解法必须把“单只跳蚤的随机游走”和“最终空格的期望”拆开处理。
最自然的模型是网格图上的随机游走。我们不去描述全部跳蚤的联合分布，而是对每一个起点单独计算一只跳蚤在 \(50\) 步后的分布，然后再把这些结果组合起来。
设 \(V\) 是这 \(900\) 个格子的集合，\(\deg(u)\in\{2,3,4\}\) 表示格子 \(u\) 的合法邻居数。对于从起点 \(s\) 出发的一只跳蚤，定义
$$p_s^{(t)}(v)=\mathbb{P}(\text{这只跳蚤在 }t\text{ 次铃声后位于 }v).$$
初始条件是一个点质量分布：
$$p_s^{(0)}(v)= \begin{cases} 1,& v=s,\\ 0,& v\ne s. \end{cases}$$
如果 \(u\sim v\) 表示 \(u\) 与 \(v\) 在棋盘上正交相邻，那么一步转移满足
$$p_s^{(t+1)}(v)=\sum_{u\sim v}\frac{p_s^{(t)}(u)}{\deg(u)}.$$
这正是实现里反复执行的“概率扩散”过程：每个格子把当前概率质量平均分给自己的邻居。这个递推还带来一个重要不变量：
$$\sum_{v\in V} p_s^{(t)}(v)=1,$$
也就是说，无论扩散多少轮，单只跳蚤的概率总质量始终保持为 \(1\)。
现在固定一个目标格子 \(v\)。对于任意起点 \(s\)，从 \(s\) 出发的那只跳蚤在 \(50\) 步后不在 \(v\) 的概率是 \(1-p_s^{(50)}(v)\)。由于不同跳蚤的运动彼此独立，所以针对这个固定目标格子，所有这些概率可以直接相乘：
$$\mathbb{P}(v\text{ 在 50 次铃声后为空})=\prod_{s\in V}\left(1-p_s^{(50)}(v)\right).$$
这就是本题最核心的公式。它完全绕开了“到底有多少只跳蚤同时落在 \(v\)”这种复杂联合计数，因为只要知道每只独立跳蚤会不会到达 \(v\) 即可。
设 \(I_v\) 是格子 \(v\) 是否为空的指示变量：
$$I_v= \begin{cases} 1,& v\text{ 为空},\\ 0,& v\text{ 非空}. \end{cases}$$
那么空格总数可以写成
$$X=\sum_{v\in V} I_v.$$
不同格子的“是否为空”事件当然不是独立的，但期望值不需要独立性：
$$\mathbb{E}[X]=\sum_{v\in V}\mathbb{E}[I_v]=\sum_{v\in V}\mathbb{P}(v\text{ 为空}).$$
把上一小节的乘积公式代入后，就得到程序真正计算的总公式：
$$\boxed{\mathbb{E}[X]=\sum_{v\in V}\prod_{s\in V}\left(1-p_s^{(50)}(v)\right).}$$
这个小例子很有价值，因为它正好对应实现中使用的校验情形。对于 \(2\times 2\) 棋盘，每个格子都是角格，因此每只跳蚤都有两个可跳方向。固定某个目标格子 \(v\)。一次铃声后，只有与 \(v\) 相邻的两只跳蚤有可能跳入 \(v\)，而且各自概率都是 \(1/2\)。原本就在 \(v\) 的跳蚤一定会离开，斜对角的那只跳蚤一步之内无法到达 \(v\)。所以
$$\mathbb{P}(v\text{ 为空})=\left(1-\frac12\right)\left(1-\frac12\right)\left(1-0\right)\left(1-0\right)=\frac14.$$
四个格子完全对称，因此
$$\mathbb{E}[X]=4\cdot\frac14=1.$$
真正的 \(30\times 30\) 情形在数学结构上没有任何变化，只是需要计算的扩散表从 \(4\) 个格子扩大到了 \(900\) 个格子。
C++、Python 和 Java 实现都会先把 \(30\times 30\) 棋盘编号为 \(900\) 个顶点，再为每个格子建立邻接表。这样，角格、边格、内部格的不同度数就都被明确编码好了。
当起点 \(s\) 固定后，程序用一个概率向量表示这只跳蚤的当前位置分布：起初只有 \(s\) 位置为 \(1\)，其余位置为 \(0\)。随后按前面的递推式做 \(50\) 轮更新。实现中始终只复用两个数组，一个表示当前层，一个表示下一层，因此空间开销保持在线性级别。完成第 \(50\) 轮后，这个向量就给出了所有 \(p_s^{(50)}(v)\)。
程序还维护另一个长度为 \(900\) 的数组，用来记录每个目标格子的累积乘积。某个起点 \(s\) 的扩散结束后，就把所有目标格子的当前值乘上 \(1-p_s^{(50)}(v)\)。当全部 \(900\) 个起点都处理完以后，这个数组中的每一项恰好就是对应格子在 \(50\) 次铃声后为空的概率。
最后把这 \(900\) 个概率加总，便得到空格数量的期望。
设棋盘边长为 \(n\)，格子总数为 \(N=n^2\)。建立邻接表需要 \(O(N)\) 时间和 \(O(N)\) 空间，因为每个格子的邻居数最多只有四个。
对于每一个起点，共要进行 \(T\) 轮扩散，而每一轮都要扫描全部 \(N\) 个格子并做常数度数的转移更新，所以总时间复杂度是 \(O(TN^2)\)。由于 \(N=n^2\)，这也可以写成 \(O(Tn^4)\)。
额外工作空间保持在 \(O(N)\)：一份线性大小的邻接结构、一份记录空格概率的数组，以及两个重复使用的概率向量。对实际参数 \(n=30\)、\(T=50\) 来说，这种动态规划式的求法完全可行。
На доске \(30\times 30\) в каждой клетке изначально сидит ровно одна блоха, то есть всего \(900\) блох. После каждого удара колокольчика все блохи одновременно перепрыгивают в одну из допустимых ортогонально соседних клеток, выбирая её равновероятно. Поэтому у угловых клеток степень \(2\), у граничных степень \(3\), а у внутренних степень \(4\).
Через \(50\) ударов несколько блох могут оказаться в одной клетке, а некоторые клетки могут опустеть. Нужно найти математическое ожидание числа пустых клеток с точностью до шести знаков после запятой. Совместное состояние всех \(900\) блох слишком велико, поэтому решение опирается на независимость отдельных траекторий и на линейность ожидания.
Удобно смотреть на задачу как на случайное блуждание по графу клеток. Вместо того чтобы отслеживать всех блох одновременно, мы для каждого стартового положения отдельно вычисляем распределение одной блохи через \(50\) шагов.
Пусть \(V\) — множество всех \(900\) клеток, а \(\deg(u)\in\{2,3,4\}\) — число допустимых соседей клетки \(u\). Для блохи, стартующей из клетки \(s\), введём
$$p_s^{(t)}(v)=\mathbb{P}(\text{блоха находится в }v\text{ после }t\text{ ударов}).$$
Начальное распределение сосредоточено в одной точке:
$$p_s^{(0)}(v)= \begin{cases} 1,& v=s,\\ 0,& v\ne s. \end{cases}$$
Если \(u\sim v\) означает, что клетки \(u\) и \(v\) являются ортогональными соседями, то переход на следующий шаг задаётся формулой
$$p_s^{(t+1)}(v)=\sum_{u\sim v}\frac{p_s^{(t)}(u)}{\deg(u)}.$$
Именно эту рекурсию реализует код: каждая клетка делит свою текущую вероятность поровну между соседями. При этом сохраняется важный инвариант
$$\sum_{v\in V} p_s^{(t)}(v)=1,$$
то есть на каждом шаге мы по-прежнему имеем корректное распределение вероятностей.
Зафиксируем целевую клетку \(v\). Для каждого старта \(s\) вероятность того, что блоха из \(s\) не находится в \(v\) через \(50\) шагов, равна \(1-p_s^{(50)}(v)\). Поскольку движения разных блох независимы, для этой фиксированной клетки вероятности можно перемножить:
$$\mathbb{P}(v\text{ пуста после 50 ударов})=\prod_{s\in V}\left(1-p_s^{(50)}(v)\right).$$
Это центральная формула задачи. Она избавляет от необходимости анализировать все возможные столкновения блох в одной клетке; достаточно знать, достигает ли её каждая независимая блоха.
Пусть \(I_v\) — индикатор того, что клетка \(v\) пуста:
$$I_v= \begin{cases} 1,& v\text{ пуста},\\ 0,& v\text{ занята}. \end{cases}$$
Тогда число пустых клеток равно
$$X=\sum_{v\in V} I_v.$$
События пустоты разных клеток зависимы, но для ожидания это не мешает:
$$\mathbb{E}[X]=\sum_{v\in V}\mathbb{E}[I_v]=\sum_{v\in V}\mathbb{P}(v\text{ пуста}).$$
Подставляя формулу из предыдущего пункта, получаем итоговое выражение, которое и вычисляют реализации:
$$\boxed{\mathbb{E}[X]=\sum_{v\in V}\prod_{s\in V}\left(1-p_s^{(50)}(v)\right).}$$
Этот маленький пример полезен, потому что совпадает с контрольной проверкой в реализации. На доске \(2\times 2\) каждая клетка является углом и имеет ровно двух соседей. Зафиксируем целевую клетку \(v\). После одного удара попасть в \(v\) могут только две соседние блохи, и каждая делает это с вероятностью \(1/2\). Блоха, стартовавшая из \(v\), обязана уйти, а блоха из диагонально противоположной клетки не может попасть в \(v\) за один шаг. Поэтому
$$\mathbb{P}(v\text{ пуста})=\left(1-\frac12\right)\left(1-\frac12\right)\left(1-0\right)\left(1-0\right)=\frac14.$$
Все четыре клетки симметричны, значит
$$\mathbb{E}[X]=4\cdot\frac14=1.$$
В задаче \(30\times 30\) используется та же самая схема, только таблица переходов существенно больше.
Реализации на C++, Python и Java сначала нумеруют все \(900\) клеток и строят для каждой список соседей. Так в коде фиксируется структура степеней \(2/3/4\) для углов, границ и внутренних клеток.
Для выбранной стартовой клетки \(s\) вектор вероятностей инициализируется единицей в \(s\) и нулями в остальных местах. Затем \(50\) раз применяется рекуррентный переход. Во всех версиях используются два переиспользуемых массива: текущий слой и следующий слой. После пятидесятого шага текущий массив содержит все значения \(p_s^{(50)}(v)\).
Отдельный массив хранит для каждой целевой клетки \(v\) текущее произведение. После обработки одного стартового положения в него домножается фактор \(1-p_s^{(50)}(v)\) для всех \(v\). Когда обработаны все \(900\) стартов, каждая ячейка этого массива уже равна вероятности того, что соответствующая клетка окажется пустой через \(50\) ударов.
Остаётся только просуммировать все \(900\) значений и получить искомое математическое ожидание.
Пусть \(n\) — длина стороны, а \(N=n^2\) — число клеток. Построение списков соседей занимает \(O(N)\) времени и \(O(N)\) памяти, потому что у каждой клетки не больше четырёх соседей.
Для каждого из \(N\) стартов алгоритм выполняет \(T\) раундов диффузии, и каждый раунд обрабатывает все \(N\) клеток с константным числом переходов. Итого время равно \(O(TN^2)\). Так как \(N=n^2\), это то же самое, что \(O(Tn^4)\).
Рабочая память остаётся линейной, \(O(N)\): одна линейная структура смежности, один аккумулятор вероятностей пустоты и два переиспользуемых вектора распределения. Для реальных параметров \(n=30\) и \(T=50\) такой метод вполне практичен.
لدينا لوحة \(30\times 30\)، وفي كل خلية برغوث واحد في البداية، أي يوجد \(900\) برغوثًا إجمالًا. عند كل رنّة جرس تقفز جميع البراغيث في الوقت نفسه إلى إحدى الخلايا المجاورة أفقيًا أو عموديًا باحتمال متساوٍ بين الجيران المسموح بهم. لذلك تكون درجة خلايا الزوايا \(2\)، وخلايا الحواف \(3\)، والخلايا الداخلية \(4\).
بعد \(50\) رنّة قد تجتمع عدة براغيث في الخلية نفسها، وقد تبقى بعض الخلايا فارغة. المطلوب هو القيمة المتوقعة لعدد الخلايا الفارغة مع ستة منازل عشرية. تتبع الحالة المشتركة لجميع البراغيث معًا غير عملي تمامًا، لذا يعتمد الحل على تحليل حركة برغوث واحد في كل مرة ثم تجميع النتائج بالاستقلالية وخطية التوقع.
أفضل طريقة لرؤية المسألة هي باعتبارها مشيًا عشوائيًا على رسم الشبكة. بدلًا من تتبع \(900\) برغوث معًا، نحسب لكل خلية بداية توزيع برغوث واحد بعد \(50\) خطوة، ثم نستخرج منه احتمال الفراغ.
لتكن \(V\) مجموعة الخلايا كلها، وعددها \(900\). ولتكن \(\deg(u)\in\{2,3,4\}\) عدد الجيران المسموح بهم للخلية \(u\). لبرغوث يبدأ من الخلية \(s\)، نرمز باحتمال وجوده في \(v\) بعد \(t\) رنّات إلى
$$p_s^{(t)}(v)=\mathbb{P}(X_t=v\mid X_0=s).$$
الحالة الابتدائية تتركز في نقطة واحدة:
$$p_s^{(0)}(v)= \begin{cases} 1,& v=s,\\ 0,& v\ne s. \end{cases}$$
إذا كان \(u\sim v\) يعني أن الخليتين \(u\) و\(v\) متجاورتان تعامديًا، فإن علاقة الانتقال هي
$$p_s^{(t+1)}(v)=\sum_{u\sim v}\frac{p_s^{(t)}(u)}{\deg(u)}.$$
وهذه هي بالضبط عملية الانتشار التي تنفذها الشيفرة: كل خلية توزع كتلتها الاحتمالية الحالية بالتساوي على جيرانها. كما أن هناك ثابتًا مهمًا يحافظ عليه التحديث دائمًا:
$$\sum_{v\in V} p_s^{(t)}(v)=1.$$
أي إن كل طبقة تبقى توزيعًا احتماليًا صحيحًا.
ثبّت الآن خلية هدف \(v\)، ولْيكن \(E_v\) حدث أن تكون هذه الخلية فارغة بعد \(50\) رنّة. لكل خلية بداية \(s\)، احتمال ألّا يكون البرغوث القادم من \(s\) في \(v\) بعد \(50\) خطوة هو \(1-p_s^{(50)}(v)\). وبما أن حركات البراغيث مستقلة، يمكن ضرب هذه الاحتمالات لهذه الخلية الهدف الثابتة:
$$\mathbb{P}(E_v)=\prod_{s\in V}\left(1-p_s^{(50)}(v)\right).$$
هذه هي الصيغة المحورية في المسألة. لا حاجة إلى عدّ جميع حالات التصادم داخل \(v\)؛ المهم فقط هو هل يصل كل برغوث مستقل إلى \(v\) أم لا.
ليكن \(I_v\) متغيرًا مؤشريًا يدل على الحدث \(E_v\):
$$I_v= \begin{cases} 1,& E_v,\\ 0,& \neg E_v. \end{cases}$$
إذن عدد الخلايا الفارغة هو
$$X=\sum_{v\in V} I_v.$$
صحيح أن أحداث فراغ الخلايا المختلفة ليست مستقلة، لكن خطية التوقع تبقى صحيحة من دون هذا الشرط:
$$\mathbb{E}[X]=\sum_{v\in V}\mathbb{E}[I_v]=\sum_{v\in V}\mathbb{P}(E_v).$$
وبالتعويض من الصيغة السابقة نحصل على التعبير النهائي الذي تحسبه التطبيقات مباشرة:
$$\boxed{\mathbb{E}[X]=\sum_{v\in V}\prod_{s\in V}\left(1-p_s^{(50)}(v)\right).}$$
هذا المثال الصغير مفيد لأنه يطابق فحص السلامة الموجود في التنفيذ. في لوحة \(2\times 2\) تكون كل خلية زاوية ولها جاران فقط. ثبّت خلية هدف \(v\). بعد رنّة واحدة لا يمكن الوصول إلى \(v\) إلا من البرغوثين المجاورين لها، واحتمال وصول كل واحد منهما هو \(1/2\). أما البرغوث الذي بدأ في \(v\) فلا بد أن يغادر، والبرغوث الموجود في الزاوية المقابلة قطريًا لا يستطيع الوصول في قفزة واحدة. لذلك
$$\mathbb{P}(E_v)=\left(1-\frac12\right)\left(1-\frac12\right)\left(1-0\right)\left(1-0\right)=\frac14.$$
وبما أن الخلايا الأربع متناظرة، فإن
$$\mathbb{E}[X]=4\cdot\frac14=1.$$
المسألة الأصلية على لوحة \(30\times 30\) تستخدم الفكرة نفسها تمامًا، لكن على جدول احتمالات أكبر بكثير.
تبدأ تطبيقات C++ وPython وJava بترقيم خلايا اللوحة \(30\times 30\) وتحويلها إلى \(900\) رأس، ثم تبني قائمة الجيران لكل خلية. بهذا تُشفَّر مباشرة درجات الزوايا والحواف والداخل.
لكل خلية بداية \(s\)، يهيَّأ متجه احتمالات تكون كتلته \(1\) في \(s\) و\(0\) في غيرها. بعد ذلك تُطبَّق علاقة الانتقال \(50\) مرة. التنفيذ يعيد استخدام مصفوفتين فقط: واحدة للحالة الحالية وأخرى للحالة التالية. بعد الجولة الخمسين يحتوي المتجه الحالي على جميع القيم \(p_s^{(50)}(v)\) لكل خلية هدف \(v\).
يوجد أيضًا متجه منفصل يحتفظ، لكل خلية هدف \(v\)، بالجداء التراكمي المناسب. بعد إنهاء الانتشار لخلية بداية واحدة، تضرب الشيفرة في العامل \(1-p_s^{(50)}(v)\) لكل \(v\). وبعد معالجة جميع خلايا البداية البالغ عددها \(900\)، يصبح كل إدخال هو احتمال أن تكون تلك الخلية فارغة بعد \(50\) رنّة.
وفي النهاية تُجمع هذه القيم كلها للحصول على العدد المتوقع للخلايا الفارغة.
إذا كان طول ضلع اللوحة \(n\)، فإن عدد الخلايا هو \(N=n^2\). بناء قوائم الجيران يحتاج إلى \(O(N)\) زمنًا و\(O(N)\) ذاكرة، لأن عدد الجيران لكل خلية لا يتجاوز أربعة.
لكل واحدة من خلايا البداية وعددها \(N\)، ينفذ البرنامج \(T\) جولات انتشار، وفي كل جولة يمر على جميع الخلايا \(N\) مع عدد ثابت من الانتقالات. لذلك يكون الزمن الكلي \(O(TN^2)\). وبالتعويض \(N=n^2\) نحصل على \(O(Tn^4)\).
أما الذاكرة العاملة فتبقى \(O(N)\): بنية تجاور خطية الحجم، ومصفوفة لتراكم احتمالات الفراغ، ومصفوفتان يعاد استخدامهما لطبقات الانتشار. بالنسبة إلى القيم الفعلية \(n=30\) و\(T=50\)، فإن هذه الطريقة مباشرة وقابلة للتنفيذ بسهولة.