One hundred players sit evenly around a circle, and two dice start in opposite positions. In each round, each die independently moves one seat in one direction with probability \(1/6\), stays where it is with probability \(2/3\), or moves one seat in the other direction with probability \(1/6\). The chase ends as soon as both dice are in the same player's hands.
Because the initial separation is 50 seats on a 100-player circle, the required quantity is the expected hitting time of the meeting state starting from circular distance \(50\). The implementations evaluate this expectation as \(3780.6186217845\) rounds.
The key simplification is to ignore absolute seat numbers and keep only the circular distance between the two dice. That turns the game into a finite absorbing Markov chain whose transition law can be written down exactly.
Let \(k\in\{0,1,\dots,n-1\}\) be the clockwise distance from the first die to the second on a circle of \(n=100\) players. If both dice are rotated together by the same number of seats, nothing about future play changes, so the expectation depends only on \(k\), not on the absolute positions.
Define \(E_k\) as the expected number of remaining rounds until the dice meet when the current distance is \(k\). The meeting state is absorbing, hence
$$E_0=0.$$
A useful symmetry check is
$$E_k=E_{n-k},$$
because reversing the orientation of the circle exchanges clockwise and counterclockwise. The implementations keep the full system \(E_1,\dots,E_{99}\) instead of using this reduction, but the symmetry is still mathematically informative.
For a single die, write its movement in one round as \(X\in\{-1,0,1\}\), with
$$\Pr(X=-1)=\frac16,\qquad \Pr(X=0)=\frac23,\qquad \Pr(X=1)=\frac16.$$
If the two dice move by \(X_1\) and \(X_2\), then the circular distance changes by
$$D=X_2-X_1.$$
Convolving these two three-point distributions gives the five possible relative increments
$$\Pr(D=-2)=\frac1{36},\qquad \Pr(D=-1)=\frac29,\qquad \Pr(D=0)=\frac12,\qquad \Pr(D=1)=\frac29,\qquad \Pr(D=2)=\frac1{36}.$$
So a round can only change the distance by \(-2\), \(-1\), \(0\), \(1\), or \(2\), interpreted modulo \(n\).
From a nonzero state \(k\), one round certainly elapses, then the process continues from the new distance. First-step analysis therefore gives
$$E_k=1+\frac1{36}E_{(k-2)\bmod n}+\frac29E_{(k-1)\bmod n}+\frac12E_k+\frac29E_{(k+1)\bmod n}+\frac1{36}E_{(k+2)\bmod n}$$
for every \(1\le k\le n-1\), together with \(E_0=0\).
Equivalently, each nonzero distance satisfies the linear equation
$$E_k-\sum_{\delta=-2}^{2}p_\delta E_{(k+\delta)\bmod n}=1,$$
where \(p_{-2}=p_2=1/36\), \(p_{-1}=p_1=2/9\), and \(p_0=1/2\). Near \(k=1\) and \(k=n-1\), the indices wrap around the circle, so the matrix is cyclic rather than an ordinary straight-line finite-difference system.
The case \(n=4\) makes the recurrence concrete. The nonzero distances are \(1,2,3\), and symmetry gives \(E_1=E_3\). The opposite-start state is \(k=2\).
For \(k=1\), the shifts \(-2,-1,0,1,2\) land in \(3,0,1,2,3\), so
$$E_1=1+\frac1{36}E_3+\frac29E_0+\frac12E_1+\frac29E_2+\frac1{36}E_3=1+\frac59E_1+\frac29E_2.$$
For \(k=2\), the shifts land in \(0,1,2,3,0\), so
$$E_2=1+\frac29E_1+\frac12E_2+\frac29E_3=1+\frac49E_1+\frac12E_2.$$
Solving these equations gives
$$E_1=5.85,\qquad E_2=7.2.$$
This is exactly the same mathematics used for \(n=100\); only the number of unknown states grows.
For the Project Euler instance, \(n=100\), so there are 99 unknown expectations \(E_1,\dots,E_{99}\). The initial configuration places the dice at opposite points of the circle, hence the desired answer is
$$E_{50}.$$
Once the 99 coupled linear equations have been solved, no Monte Carlo simulation or long trajectory averaging is needed. The expectation is read directly from the solved system.
The C++, Python, and Java implementations create one row for each nonzero distance \(k\). Each row starts with the term \(E_k\) on the left and the constant \(1\) on the right, then subtracts the five transition probabilities from the columns corresponding to \((k-2)\bmod n\), \((k-1)\bmod n\), \(k\), \((k+1)\bmod n\), and \((k+2)\bmod n\). Any transition that lands in state \(0\) is skipped because \(E_0=0\) contributes nothing.
For \(n=100\), this produces a \(99\times100\) augmented matrix. The matrix is sparse when first assembled, but Gaussian elimination fills in many entries, so a dense representation is a practical choice.
The implementations use Gaussian elimination with partial pivoting. In each column, the row with the largest absolute pivot is swapped into place, the pivot row is normalized, and then that column is eliminated from every other row. After elimination, the last entry of each row is the solved expectation for that distance state.
All three languages implement the same numerical method. The output is formatted to 10 digits after the decimal point, and the non-C++ versions align their final printed decimal with the higher-precision reference output.
After the linear solve, the only value that matters is the opposite-seat state \(n/2\). With \(n=100\), that means reading the solved entry for distance \(50\), which yields
$$3780.6186217845.$$
Some implementations also verify the recurrence on smaller even circles such as \(n=2\) and \(n=4\) before reporting the 100-player result.
Constructing the equations takes \(O(n)\) time because each of the \(n-1\) rows contains only five transition terms. The dominant cost is solving the dense \((n-1)\times(n-1)\) linear system by Gaussian elimination, which requires \(O(n^3)\) arithmetic operations and \(O(n^2)\) memory.
For \(n=100\), this direct method is entirely reasonable. The important gain is conceptual: the implementations replace repeated random simulation by one deterministic solve for the expected hitting time.
Einhundert Spieler sitzen gleichmaessig auf einem Kreis, und zwei Wuerfel starten an gegenueberliegenden Positionen. In jeder Runde bewegt sich jeder Wuerfel unabhaengig mit Wahrscheinlichkeit \(1/6\) um einen Platz in die eine Richtung, mit Wahrscheinlichkeit \(2/3\) gar nicht und mit Wahrscheinlichkeit \(1/6\) um einen Platz in die andere Richtung. Die Jagd endet, sobald beide Wuerfel beim selben Spieler liegen.
Da der Anfangsabstand auf dem 100er-Kreis genau 50 Plaetze betraegt, ist die gesuchte Groesse die erwartete Treffzeit des Zustands \(0\), wenn man mit Kreisdistanz \(50\) startet. Die Implementierungen berechnen dafuer \(3780.6186217845\) Runden.
Die absolute Sitznummer ist unwichtig. Relevant ist nur der Abstand der beiden Wuerfel auf dem Kreis. Dadurch wird aus dem gesamten Spiel eine endliche absorbierende Markow-Kette mit expliziter Uebergangsstruktur.
Sei \(k\in\{0,1,\dots,n-1\}\) der Uhrzeigerabstand vom ersten Wuerfel zum zweiten auf einem Kreis mit \(n=100\) Spielern. Wenn man beide Wuerfel gleichzeitig um dieselbe Anzahl Sitze rotiert, aendert sich das kuenftige Verhalten nicht. Also haengt der Erwartungswert nur von \(k\) ab und nicht von absoluten Sitznummern.
Bezeichne mit \(E_k\) die erwartete Anzahl verbleibender Runden bis zum Treffen, wenn der aktuelle Abstand \(k\) ist. Der Treffzustand ist absorbierend, also gilt
$$E_0=0.$$
Als hilfreiche Symmetrie gilt ausserdem
$$E_k=E_{n-k},$$
denn eine Umkehr der Orientierung vertauscht nur Uhrzeigersinn und Gegenuhrzeigersinn. Die Implementierungen loesen trotzdem das volle System \(E_1,\dots,E_{99}\), weil das direkt aus der Rekurrenz folgt.
Fuer einen einzelnen Wuerfel sei sein Rundenschritt \(X\in\{-1,0,1\}\) mit
$$\Pr(X=-1)=\frac16,\qquad \Pr(X=0)=\frac23,\qquad \Pr(X=1)=\frac16.$$
Wenn sich die beiden Wuerfel um \(X_1\) und \(X_2\) bewegen, dann aendert sich der Abstand um
$$D=X_2-X_1.$$
Aus der Faltung der beiden Dreipunktverteilungen entstehen genau fuenf moegliche relative Schritte:
$$\Pr(D=-2)=\frac1{36},\qquad \Pr(D=-1)=\frac29,\qquad \Pr(D=0)=\frac12,\qquad \Pr(D=1)=\frac29,\qquad \Pr(D=2)=\frac1{36}.$$
In einer Runde kann sich der Abstand also nur um \(-2\), \(-1\), \(0\), \(1\) oder \(2\) aendern, jeweils modulo \(n\).
Von jedem nichtnulligen Zustand \(k\) vergeht zuerst sicher eine Runde, danach setzt sich das Spiel vom neuen Abstand aus fort. Die Erste-Schritt-Analyse liefert daher
$$E_k=1+\frac1{36}E_{(k-2)\bmod n}+\frac29E_{(k-1)\bmod n}+\frac12E_k+\frac29E_{(k+1)\bmod n}+\frac1{36}E_{(k+2)\bmod n}$$
fuer alle \(1\le k\le n-1\), zusammen mit \(E_0=0\).
Aequivalent dazu erfuellt jeder nichtnullige Abstand die lineare Gleichung
$$E_k-\sum_{\delta=-2}^{2}p_\delta E_{(k+\delta)\bmod n}=1,$$
wobei \(p_{-2}=p_2=1/36\), \(p_{-1}=p_1=2/9\) und \(p_0=1/2\) sind. In den Randzeilen wie \(k=1\) oder \(k=n-1\) wickeln sich die Indizes um den Kreis, deshalb ist das Gleichungssystem zyklisch gekoppelt.
Der Fall \(n=4\) zeigt die Struktur sehr klar. Die nichtnulligen Abstaende sind \(1,2,3\), und aus der Symmetrie folgt \(E_1=E_3\). Der gesuchte Gegenueber-Zustand ist \(k=2\).
Fuer \(k=1\) landen die Schritte \(-2,-1,0,1,2\) in den Zustaenden \(3,0,1,2,3\), also
$$E_1=1+\frac1{36}E_3+\frac29E_0+\frac12E_1+\frac29E_2+\frac1{36}E_3=1+\frac59E_1+\frac29E_2.$$
Fuer \(k=2\) landen die Schritte in \(0,1,2,3,0\), also
$$E_2=1+\frac29E_1+\frac12E_2+\frac29E_3=1+\frac49E_1+\frac12E_2.$$
Die Loesung lautet
$$E_1=5.85,\qquad E_2=7.2.$$
Genau dieselbe Rekurrenz wird spaeter fuer \(n=100\) geloest; nur die Anzahl der Unbekannten ist dort groesser.
Im Problem gilt \(n=100\), also gibt es 99 unbekannte Erwartungen \(E_1,\dots,E_{99}\). Die Anfangslage ist ein gegenueberliegendes Paar auf dem Kreis, also ist die gesuchte Groesse
$$E_{50}.$$
Sobald dieses lineare System geloest ist, ist keine Simulation langer Zufallspfade mehr noetig. Der Erwartungswert wird direkt aus der Loesung abgelesen.
Die C++-, Python- und Java-Implementierungen erzeugen fuer jeden Abstand \(k\neq0\) genau eine Gleichungszeile. Jede Zeile beginnt links mit \(E_k\) und rechts mit der Konstante \(1\). Anschliessend werden die fuenf Uebergangswahrscheinlichkeiten von den Spalten fuer \((k-2)\bmod n\), \((k-1)\bmod n\), \(k\), \((k+1)\bmod n\) und \((k+2)\bmod n\) abgezogen. Uebergaenge in den Zustand \(0\) werden nicht als Matrixeintrag gespeichert, weil \(E_0=0\) ist.
Fuer \(n=100\) entsteht so eine augmentierte Matrix der Groesse \(99\times100\). Beim Aufstellen ist sie noch duenn besetzt, aber durch das Eliminationsverfahren wird sie schnell dicht, daher ist eine volle Matrixdarstellung praktisch.
Die Implementierungen verwenden das Gauß-Verfahren mit partieller Pivotisierung. In jeder Spalte wird zuerst die Zeile mit dem betraglich groessten Pivot nach oben getauscht, danach wird die Pivotzeile normiert und der entsprechende Eintrag in allen anderen Zeilen eliminiert. Nach Abschluss des Verfahrens steht im letzten Eintrag jeder Zeile direkt der geloeste Erwartungswert dieses Zustands.
Die Mathematik ist in allen drei Sprachen dieselbe. Ausgegeben wird die Loesung mit 10 Nachkommastellen, und die Nicht-C++-Versionen richten ihre letzte ausgegebene Stelle am praeziseren Referenzwert aus.
Nach dem linearen Loesen interessiert nur noch der Gegenueber-Zustand \(n/2\). Bei \(n=100\) ist das der Abstand \(50\), also der Wert
$$3780.6186217845.$$
Einige Implementierungen pruefen die Rekurrenz zuvor noch an kleineren geraden Kreisen wie \(n=2\) und \(n=4\).
Das Aufstellen der Gleichungen kostet \(O(n)\) Zeit, weil jede der \(n-1\) Zeilen nur fuenf Uebergangsterme besitzt. Dominierend ist das Loesen des dichten \((n-1)\times(n-1)\)-Systems per Gauß-Elimination mit \(O(n^3)\) Rechenaufwand und \(O(n^2)\) Speicherbedarf.
Fuer \(n=100\) ist diese direkte Methode voellig unproblematisch. Der eigentliche Gewinn besteht darin, dass das Erwartungswertproblem auf einen deterministischen linearen Solver zurueckgefuehrt wird, statt viele Zufallsspiele zu mitteln.
Yuz oyuncu bir cember etrafinda es araliklarla oturur ve iki zar tam karsilikli noktalardan baslar. Her turda her zar bagimsiz olarak \(1/6\) olasilikla bir yone bir koltuk ilerler, \(2/3\) olasilikla yerinde kalir ve \(1/6\) olasilikla diger yone bir koltuk ilerler. Iki zar ayni oyuncuda bulustugu anda kovalamaca biter.
Baslangic ayrimi 100 kisilik cemberde 50 koltuk oldugu icin aranan buyukluk, dairesel mesafe \(50\) iken bulusmaya kadar kalan beklenen tur sayisidir. Uygulamalar bu degeri \(3780.6186217845\) olarak verir.
Asil fikir, mutlak koltuk numaralarini tamamen unutup yalnizca iki zar arasindaki cembersel mesafeyi izlemektir. Bu sayede sorun, gecis olasiliklari tam olarak yazilabilen sonlu bir absorbing Markov zincirine donusur.
\(k\in\{0,1,\dots,n-1\}\), \(n=100\) kisilik cemberde birinci zardan ikinci zara saat yonundeki mesafe olsun. Iki zari birlikte ayni miktarda dondurmek gelecekteki davranisi degistirmez. Dolayisiyla beklenen sure mutlak konumlardan degil, sadece \(k\) degerinden etkilenir.
Mevcut mesafe \(k\) iken bulusmaya kadar kalan beklenen tur sayisini \(E_k\) ile gosterelim. Bulusma durumu sogurucudur, yani
$$E_0=0.$$
Bir baska yararli simetri de
$$E_k=E_{n-k}$$
olmasidir; cemberin yonunu ters cevirmek saat yonu ile saat yonu tersini yer degistirir. Uygulamalar bu simetriyi kullanip durumu yariya indirmiyor, ama denklem sistemini kontrol etmek icin bu esitlik faydalidir.
Tek bir zar icin bir turdaki hareketi \(X\in\{-1,0,1\}\) ile yazalim:
$$\Pr(X=-1)=\frac16,\qquad \Pr(X=0)=\frac23,\qquad \Pr(X=1)=\frac16.$$
Iki zar sirasiyla \(X_1\) ve \(X_2\) kadar hareket ederse, aralarindaki mesafe
$$D=X_2-X_1$$
kadar degisir. Iki uc-nokta dagiliminin birlesiminden su bes olasilik gelir:
$$\Pr(D=-2)=\frac1{36},\qquad \Pr(D=-1)=\frac29,\qquad \Pr(D=0)=\frac12,\qquad \Pr(D=1)=\frac29,\qquad \Pr(D=2)=\frac1{36}.$$
Demek ki bir turda mesafe yalnizca \(-2\), \(-1\), \(0\), \(1\) veya \(2\) kadar degisebilir; hepsi mod \(n\) yorumlanir.
Sifirdan farkli bir \(k\) durumunda once kesin olarak bir tur gecilir, sonra oyun yeni mesafeden devam eder. Bu nedenle ilk-adim analizi
$$E_k=1+\frac1{36}E_{(k-2)\bmod n}+\frac29E_{(k-1)\bmod n}+\frac12E_k+\frac29E_{(k+1)\bmod n}+\frac1{36}E_{(k+2)\bmod n}$$
denklemini verir. Bu denklem \(1\le k\le n-1\) icin gecerlidir ve \(E_0=0\) ile tamamlanir.
Ayni seyi lineer denklem biciminde yazarsak
$$E_k-\sum_{\delta=-2}^{2}p_\delta E_{(k+\delta)\bmod n}=1,$$
burada \(p_{-2}=p_2=1/36\), \(p_{-1}=p_1=2/9\) ve \(p_0=1/2\) olur. \(k=1\) ve \(k=n-1\) gibi sinir durumlarinda indisler cember etrafinda sarildigi icin matris duz bir bant matris degil, dongusel olarak baglidir.
\(n=4\) ornegi bu yapinin nasil calistigini acikca gosterir. Sifirdan farkli mesafeler \(1,2,3\) olur ve simetriden \(E_1=E_3\) gelir. Karsi karsiya baslangic durumu \(k=2\)'dir.
\(k=1\) icin \(-2,-1,0,1,2\) kaymalari sirasiyla \(3,0,1,2,3\) durumlarina gider. Dolayisiyla
$$E_1=1+\frac1{36}E_3+\frac29E_0+\frac12E_1+\frac29E_2+\frac1{36}E_3=1+\frac59E_1+\frac29E_2.$$
\(k=2\) icin yeni durumlar \(0,1,2,3,0\) olur. Bu da
$$E_2=1+\frac29E_1+\frac12E_2+\frac29E_3=1+\frac49E_1+\frac12E_2$$
denklemini verir. Cozum
$$E_1=5.85,\qquad E_2=7.2$$
olur. Buyuk problemde yapilan sey aynidir; sadece bilinmeyen sayisi 99'a cikar.
Asil soruda \(n=100\) oldugundan bilinmeyenler \(E_1,\dots,E_{99}\) seklindedir. Baslangicta zarlar cemberin tam karsi noktalarinda oldugu icin aranan deger
$$E_{50}$$
olur. Bu 99 bagli lineer denklem cozulduktan sonra herhangi bir Monte Carlo benzetimine gerek kalmaz; sonuc dogrudan okunur.
C++, Python ve Java uygulamalari, sifirdan farkli her \(k\) mesafesi icin bir satir kurar. Her satir solda \(E_k\) katsayisiyla, sagda da sabit \(1\) ile baslar; sonra \((k-2)\bmod n\), \((k-1)\bmod n\), \(k\), \((k+1)\bmod n\) ve \((k+2)\bmod n\) durumlarina ait sutunlardan bes gecis olasiligi cikarilir. Yeni durum \(0\) ise matris girisi eklenmez, cunku \(E_0=0\) katkisi zaten sifirdir.
\(n=100\) icin ortaya \(99\times100\) boyutlu bir genisletilmis matris cikar. Baslangicta her satir seyrektir, fakat Gauss eliminasyonu sirasinda doldugu icin yogun matris saklamak uygundur.
Uygulamalar kismi pivotlamali Gauss eliminasyonu kullanir. Her sutunda mutlak degerce en buyuk pivot secilir, ilgili satir yukariya tasinir, pivot satiri normlanir ve ayni sutundaki deger tum diger satirlardan yok edilir. Islem bittiginde her satirin son elemani ilgili durumun cozulmus beklenen suresidir.
Uc dilde de ayni cebir uygulanir. Yayinlanan sonuc ondalik noktadan sonra 10 basamakla yazdirilir; C++ disindaki surumler son basamagi daha yuksek hassasiyetli referans ciktisiyla uyumlu hale getirir.
Lineer cozum tamamlandiginda gerekli olan tek sey karsi-koltuk durumu \(n/2\)'dir. \(n=100\) icin bu, mesafe \(50\) satirindan okunan
$$3780.6186217845$$
degeridir. Bazi uygulamalar bunu yazdirmadan once \(n=2\) ve \(n=4\) gibi kucuk cemberlerde denetim de yapar.
Denklemleri kurmak \(O(n)\) zaman alir, cunku \(n-1\) satirin her birinde yalnizca bes gecis terimi vardir. Baskin maliyet, yogun \((n-1)\times(n-1)\) lineer sistemi Gauss eliminasyonuyla cozmektir; bu adim \(O(n^3)\) aritmetik islem ve \(O(n^2)\) bellek gerektirir.
\(n=100\) icin bu dogrudan yontem son derece makuldur. Asil kazanc, uzun rastgele oyunlari ortalamak yerine beklenen bulusma suresini tek bir deterministik lineer cozumle elde etmektir.
Cien jugadores se sientan uniformemente alrededor de un circulo y dos dados comienzan en posiciones opuestas. En cada ronda, cada dado se mueve de forma independiente: avanza un asiento en una direccion con probabilidad \(1/6\), se queda quieto con probabilidad \(2/3\), o avanza un asiento en la direccion contraria con probabilidad \(1/6\). La persecucion termina en cuanto ambos dados quedan en manos del mismo jugador.
Como la separacion inicial en el circulo de 100 jugadores es de 50 asientos, la cantidad buscada es el tiempo esperado de llegada al estado de encuentro cuando la distancia circular inicial es \(50\). Las implementaciones calculan ese valor como \(3780.6186217845\) rondas.
La simplificacion decisiva consiste en olvidar los numeros absolutos de los asientos y seguir solo la distancia circular entre los dos dados. Eso convierte el juego en una cadena de Markov absorbente finita con una ley de transicion exacta.
Sea \(k\in\{0,1,\dots,n-1\}\) la distancia en sentido horario desde el primer dado hasta el segundo en un circulo con \(n=100\) jugadores. Si ambos dados se rotan juntos el mismo numero de asientos, nada cambia en la evolucion futura. Por eso la esperanza solo depende de \(k\) y no de las posiciones absolutas.
Definimos \(E_k\) como el numero esperado de rondas restantes hasta que los dados se encuentren cuando la distancia actual es \(k\). El estado de encuentro es absorbente, de modo que
$$E_0=0.$$
Tambien conviene observar la simetria
$$E_k=E_{n-k},$$
porque invertir la orientacion del circulo intercambia horario y antihorario. Las implementaciones no usan esta reduccion y resuelven directamente el sistema completo \(E_1,\dots,E_{99}\), pero la identidad sigue siendo una buena comprobacion conceptual.
Para un solo dado, escribimos su movimiento en una ronda como \(X\in\{-1,0,1\}\), con
$$\Pr(X=-1)=\frac16,\qquad \Pr(X=0)=\frac23,\qquad \Pr(X=1)=\frac16.$$
Si los dos dados se desplazan \(X_1\) y \(X_2\), entonces la distancia cambia en
$$D=X_2-X_1.$$
La convolucion de ambas distribuciones produce exactamente cinco incrementos relativos posibles:
$$\Pr(D=-2)=\frac1{36},\qquad \Pr(D=-1)=\frac29,\qquad \Pr(D=0)=\frac12,\qquad \Pr(D=1)=\frac29,\qquad \Pr(D=2)=\frac1{36}.$$
Asi, en una sola ronda la distancia solo puede variar en \(-2\), \(-1\), \(0\), \(1\) o \(2\), siempre modulo \(n\).
Desde un estado no nulo \(k\), primero transcurre con certeza una ronda y luego el proceso continua desde la nueva distancia. El analisis de primer paso da entonces
$$E_k=1+\frac1{36}E_{(k-2)\bmod n}+\frac29E_{(k-1)\bmod n}+\frac12E_k+\frac29E_{(k+1)\bmod n}+\frac1{36}E_{(k+2)\bmod n}$$
para todo \(1\le k\le n-1\), junto con \(E_0=0\).
De forma equivalente, cada distancia no nula satisface
$$E_k-\sum_{\delta=-2}^{2}p_\delta E_{(k+\delta)\bmod n}=1,$$
donde \(p_{-2}=p_2=1/36\), \(p_{-1}=p_1=2/9\) y \(p_0=1/2\). Cerca de \(k=1\) y \(k=n-1\), los indices se envuelven alrededor del circulo, asi que la matriz es ciclica y no una simple banda lineal.
El caso \(n=4\) muestra muy bien la mecanica. Las distancias no nulas son \(1,2,3\), y por simetria se cumple \(E_1=E_3\). El estado de salida opuesto es \(k=2\).
Para \(k=1\), los desplazamientos \(-2,-1,0,1,2\) llevan a \(3,0,1,2,3\), de modo que
$$E_1=1+\frac1{36}E_3+\frac29E_0+\frac12E_1+\frac29E_2+\frac1{36}E_3=1+\frac59E_1+\frac29E_2.$$
Para \(k=2\), los nuevos estados son \(0,1,2,3,0\), y por tanto
$$E_2=1+\frac29E_1+\frac12E_2+\frac29E_3=1+\frac49E_1+\frac12E_2.$$
Al resolver se obtiene
$$E_1=5.85,\qquad E_2=7.2.$$
La version de 100 jugadores usa exactamente la misma recurrencia; solo cambia el tamano del sistema lineal.
En el problema completo, \(n=100\), asi que hay 99 expectativas desconocidas \(E_1,\dots,E_{99}\). La configuracion inicial pone los dados en puntos opuestos del circulo, luego el valor buscado es
$$E_{50}.$$
Una vez resueltas esas 99 ecuaciones acopladas, ya no hace falta ninguna simulacion estocastica. La esperanza se lee directamente de la solucion.
Las implementaciones en C++, Python y Java crean una fila por cada distancia no nula \(k\). Cada fila empieza con el termino \(E_k\) a la izquierda y la constante \(1\) a la derecha; despues resta las cinco probabilidades de transicion en las columnas correspondientes a \((k-2)\bmod n\), \((k-1)\bmod n\), \(k\), \((k+1)\bmod n\) y \((k+2)\bmod n\). Si una transicion cae en el estado \(0\), se omite porque \(E_0=0\) no aporta nada.
Para \(n=100\), esto produce una matriz aumentada de \(99\times100\). Aunque la matriz es dispersa al construirse, la eliminacion gaussiana introduce muchos terminos no nulos, de modo que almacenarla de forma densa es una decision natural.
Las tres implementaciones usan eliminacion gaussiana con pivoteo parcial. En cada columna se intercambia hacia arriba la fila con el pivote de mayor valor absoluto, se normaliza la fila pivote y luego se elimina esa columna del resto de filas. Al final del proceso, la ultima entrada de cada fila contiene la esperanza resuelta para ese estado de distancia.
El procedimiento numerico es el mismo en los tres lenguajes. La salida se formatea con 10 cifras decimales y las versiones que no usan la precision extendida de C++ ajustan la ultima cifra impresa para coincidir con la referencia.
Despues de resolver el sistema, solo interesa el estado opuesto \(n/2\). Para \(n=100\), eso significa leer la entrada correspondiente a la distancia \(50\), que da
$$3780.6186217845.$$
Algunas implementaciones tambien comprueban antes la recurrencia en circulos pequenos y pares, como \(n=2\) y \(n=4\).
Construir las ecuaciones cuesta \(O(n)\) tiempo, porque cada una de las \(n-1\) filas solo contiene cinco terminos de transicion. El coste dominante es resolver el sistema denso \((n-1)\times(n-1)\) mediante eliminacion gaussiana, lo que requiere \(O(n^3)\) operaciones aritmeticas y \(O(n^2)\) memoria.
Para \(n=100\), el metodo directo es totalmente razonable. La ventaja real es que el problema del tiempo esperado se transforma en una unica resolucion lineal determinista, en lugar de promediar simulaciones aleatorias muy largas.
100 名玩家均匀地围坐成一个圆，两枚骰子一开始位于正对的位置。每一轮中，每枚骰子都独立地进行一次局部移动：以 \(1/6\) 的概率向一个方向移动 1 个座位，以 \(2/3\) 的概率停留不动，以 \(1/6\) 的概率向相反方向移动 1 个座位。只要两枚骰子落到同一名玩家手中，追逐过程就结束。
因为在 100 人圆桌上，初始时两枚骰子的圆周距离正好是 50，所以题目要求的是从距离 \(50\) 出发，到首次相遇为止的期望轮数。三种实现最终得到的数值都是 \(3780.6186217845\) 轮。
真正需要跟踪的量不是两枚骰子的绝对座位编号，而只是它们在圆上的相对距离。这样一来，原问题就被压缩成了一个有限的吸收型马尔可夫链，而且每一步的转移概率都可以直接写出来。
设 \(k\in\{0,1,\dots,n-1\}\) 表示在 \(n=100\) 人圆桌上，从第一枚骰子沿顺时针方向走到第二枚骰子的距离。如果把两枚骰子同时整体旋转同样多的座位，之后的随机过程并不会发生任何变化，所以期望值只依赖于距离 \(k\)，与绝对位置无关。
记 \(E_k\) 为当前圆周距离为 \(k\) 时，到两枚骰子相遇还需要的期望轮数。相遇状态是吸收态，因此
$$E_0=0.$$
还有一个很有用的对称关系：
$$E_k=E_{n-k}.$$
原因是把圆的方向反过来，只会交换顺时针与逆时针。实现代码虽然没有利用这个对称性去减少未知量，而是直接求解 \(E_1,\dots,E_{99}\)，但这个恒等式非常适合作为推导和结果的自检。
对单枚骰子来说，把一轮中的位移记作 \(X\in\{-1,0,1\}\)，其分布为
$$\Pr(X=-1)=\frac16,\qquad \Pr(X=0)=\frac23,\qquad \Pr(X=1)=\frac16.$$
如果两枚骰子的位移分别是 \(X_1\) 和 \(X_2\)，那么它们之间的距离变化量就是
$$D=X_2-X_1.$$
把两个三点分布做卷积，就得到相对距离的五种可能变化：
$$\Pr(D=-2)=\frac1{36},\qquad \Pr(D=-1)=\frac29,\qquad \Pr(D=0)=\frac12,\qquad \Pr(D=1)=\frac29,\qquad \Pr(D=2)=\frac1{36}.$$
也就是说，一轮之后，圆周距离只可能减少 2、减少 1、不变、增加 1 或增加 2，而且都要按模 \(n\) 的意义理解。
当当前状态 \(k\neq0\) 时，先必然消耗 1 轮，然后过程从新的距离继续。因此首步分析给出
$$E_k=1+\frac1{36}E_{(k-2)\bmod n}+\frac29E_{(k-1)\bmod n}+\frac12E_k+\frac29E_{(k+1)\bmod n}+\frac1{36}E_{(k+2)\bmod n}$$
这里 \(1\le k\le n-1\)，并配合吸收条件 \(E_0=0\)。
把未知项全部移到左边，可写成统一的线性方程组形式：
$$E_k-\sum_{\delta=-2}^{2}p_\delta E_{(k+\delta)\bmod n}=1,$$
其中 \(p_{-2}=p_2=1/36\)，\(p_{-1}=p_1=2/9\)，\(p_0=1/2\)。需要注意的是，当 \(k\) 接近 1 或 \(n-1\) 时，下标会绕回圆的另一端，所以这个方程组不是普通的直线型五对角系统，而是带有环状耦合的循环系统。
\(n=4\) 的小例子最能说明递推是如何工作的。非零距离只有 \(1,2,3\)，并且由对称性可知 \(E_1=E_3\)。而“正对起点”对应的正是 \(k=2\)。
对 \(k=1\) 来说，五种变化 \(-2,-1,0,1,2\) 分别落到状态 \(3,0,1,2,3\)，于是
$$E_1=1+\frac1{36}E_3+\frac29E_0+\frac12E_1+\frac29E_2+\frac1{36}E_3=1+\frac59E_1+\frac29E_2.$$
对 \(k=2\) 来说，五种变化落到 \(0,1,2,3,0\)，所以
$$E_2=1+\frac29E_1+\frac12E_2+\frac29E_3=1+\frac49E_1+\frac12E_2.$$
解这两个方程可得
$$E_1=5.85,\qquad E_2=7.2.$$
真正的 100 人情形使用的是完全相同的数学框架，只是未知量从很小的手算系统变成了 99 个状态。
在原题中 \(n=100\)，因此未知量是 \(E_1,\dots,E_{99}\) 这 99 个期望值。由于初始时两枚骰子位于圆上的对径位置，所以最终要读出的就是
$$E_{50}.$$
一旦这 99 个联立线性方程被解出，就不需要任何随机模拟或长时间平均，答案直接从解向量中读取即可。
C++、Python 和 Java 三个实现都会为每个非零距离 \(k\) 建立一行方程。每一行先把左边的 \(E_k\) 系数设为 1，右边常数项设为 1，然后分别从 \((k-2)\bmod n\)、\((k-1)\bmod n\)、\(k\)、\((k+1)\bmod n\) 和 \((k+2)\bmod n\) 对应的列中减去五个转移概率。凡是转移到状态 \(0\) 的项都不进入矩阵，因为 \(E_0=0\) 不会贡献任何未知量。
当 \(n=100\) 时，这一步得到的是一个 \(99\times100\) 的增广矩阵。矩阵在建立时很稀疏，但高斯消元会迅速填充非零项，因此直接使用致密存储最省事。
三个实现都采用带部分主元选取的高斯消元。每一列先找绝对值最大的主元行并交换到当前位置，再把主元行归一化，然后从其他所有行中消去这一列。等消元结束后，每一行最后一列就是相应距离状态的期望值。
三种语言使用的是同一套数值线性代数过程。最终输出统一保留小数点后 10 位，而不使用扩展精度的版本还会把最后一位格式化到与高精度参考结果一致。
线性系统解完之后，只需要关心对面起点对应的状态 \(n/2\)。在 \(n=100\) 时，也就是读取距离 \(50\) 的解：
$$3780.6186217845.$$
有些实现还会先在 \(n=2\) 和 \(n=4\) 这样的较小偶数圆上验证递推是否得到已知结果，再输出 100 人答案。
建立方程组只需 \(O(n)\) 时间，因为 \(n-1\) 行中的每一行都只有 5 个转移项。主导成本是对致密的 \((n-1)\times(n-1)\) 线性系统做高斯消元，这需要 \(O(n^3)\) 次算术运算和 \(O(n^2)\) 的内存。
对于 \(n=100\) 这样的规模，直接法完全可行。真正重要的是思路上的转化：实现不是去平均海量随机试验，而是把“期望首次相遇时间”变成一次确定性的线性方程求解。
Сто игроков равномерно рассажены по кругу, а два кубика начинают в диаметрально противоположных позициях. В каждом раунде каждый кубик независимо с вероятностью \(1/6\) смещается на одно место в одну сторону, с вероятностью \(2/3\) остается на месте и с вероятностью \(1/6\) смещается на одно место в противоположную сторону. Погоня заканчивается, как только оба кубика оказываются у одного и того же игрока.
Так как на круге из 100 игроков начальное расстояние равно 50, нужно найти математическое ожидание времени достижения состояния встречи при старте из кругового расстояния \(50\). Реализации вычисляют это значение как \(3780.6186217845\) раунда.
Главное упрощение состоит в том, чтобы забыть абсолютные номера мест и отслеживать только круговое расстояние между двумя кубиками. Тогда вся задача превращается в конечную поглощающую цепь Маркова с явно выписываемыми переходами.
Пусть \(k\in\{0,1,\dots,n-1\}\) обозначает расстояние по часовой стрелке от первого кубика до второго на круге из \(n=100\) игроков. Если повернуть оба кубика одновременно на одно и то же число мест, дальнейшая динамика не изменится. Следовательно, искомое ожидание зависит только от \(k\), а не от абсолютных позиций.
Обозначим через \(E_k\) ожидаемое число оставшихся раундов до встречи, если текущее расстояние равно \(k\). Состояние встречи является поглощающим, поэтому
$$E_0=0.$$
Полезная симметрия имеет вид
$$E_k=E_{n-k},$$
потому что смена ориентации круга просто меняет местами движение по и против часовой стрелки. Реализации не используют это для уменьшения числа неизвестных и решают полную систему \(E_1,\dots,E_{99}\), но сама симметрия хорошо проверяет правильность вывода.
Для одного кубика обозначим его шаг за раунд через \(X\in\{-1,0,1\}\), где
$$\Pr(X=-1)=\frac16,\qquad \Pr(X=0)=\frac23,\qquad \Pr(X=1)=\frac16.$$
Если два кубика сместились на \(X_1\) и \(X_2\), то изменение расстояния равно
$$D=X_2-X_1.$$
Свёртка двух таких трёхточечных распределений даёт ровно пять возможных относительных приращений:
$$\Pr(D=-2)=\frac1{36},\qquad \Pr(D=-1)=\frac29,\qquad \Pr(D=0)=\frac12,\qquad \Pr(D=1)=\frac29,\qquad \Pr(D=2)=\frac1{36}.$$
Значит, за один раунд круговое расстояние может измениться только на \(-2\), \(-1\), \(0\), \(1\) или \(2\), и все индексы понимаются по модулю \(n\).
Из любого ненулевого состояния \(k\) сначала обязательно проходит один раунд, а затем процесс продолжается из нового расстояния. Поэтому анализ первого шага даёт
$$E_k=1+\frac1{36}E_{(k-2)\bmod n}+\frac29E_{(k-1)\bmod n}+\frac12E_k+\frac29E_{(k+1)\bmod n}+\frac1{36}E_{(k+2)\bmod n}$$
для всех \(1\le k\le n-1\), вместе с условием \(E_0=0\).
Эквивалентно, каждое ненулевое состояние удовлетворяет линейному уравнению
$$E_k-\sum_{\delta=-2}^{2}p_\delta E_{(k+\delta)\bmod n}=1,$$
где \(p_{-2}=p_2=1/36\), \(p_{-1}=p_1=2/9\), \(p_0=1/2\). Возле \(k=1\) и \(k=n-1\) индексы переходят через край круга, поэтому матрица имеет циклическую, а не просто линейную ленточную структуру.
Случай \(n=4\) наглядно показывает механику. Ненулевые расстояния равны \(1,2,3\), а по симметрии \(E_1=E_3\). Противоположный старт соответствует состоянию \(k=2\).
Для \(k=1\) сдвиги \(-2,-1,0,1,2\) переводят в состояния \(3,0,1,2,3\), поэтому
$$E_1=1+\frac1{36}E_3+\frac29E_0+\frac12E_1+\frac29E_2+\frac1{36}E_3=1+\frac59E_1+\frac29E_2.$$
Для \(k=2\) новые состояния равны \(0,1,2,3,0\), откуда
$$E_2=1+\frac29E_1+\frac12E_2+\frac29E_3=1+\frac49E_1+\frac12E_2.$$
Решение этой системы:
$$E_1=5.85,\qquad E_2=7.2.$$
Для исходной задачи с 100 игроками используется абсолютно та же рекуррентная схема; меняется только размер системы.
В самой задаче \(n=100\), следовательно, неизвестны 99 ожиданий \(E_1,\dots,E_{99}\). Начальная конфигурация ставит кубики в противоположные точки круга, значит требуется именно
$$E_{50}.$$
После решения этих 99 связанных линейных уравнений никакого моделирования длинных случайных траекторий больше не нужно: ответ просто читается из полученного решения.
Реализации на C++, Python и Java создают по одной строке для каждого ненулевого расстояния \(k\). В начале строки коэффициент при \(E_k\) равен 1, а правая часть тоже равна 1. Затем из столбцов, отвечающих состояниям \((k-2)\bmod n\), \((k-1)\bmod n\), \(k\), \((k+1)\bmod n\) и \((k+2)\bmod n\), вычитаются пять вероятностей перехода. Переходы в состояние \(0\) в матрицу не записываются, потому что \(E_0=0\).
При \(n=100\) получается расширенная матрица размера \(99\times100\). На этапе построения она почти разреженная, но метод Гаусса быстро заполняет многие элементы, поэтому плотное хранение здесь удобно и естественно.
Во всех трех языках используется метод Гаусса с частичным выбором главного элемента. В каждом столбце наверх поднимается строка с максимальным по модулю ведущим элементом, затем ведущая строка нормируется, а этот столбец зануляется во всех остальных строках. После завершения процесса последний элемент каждой строки и есть искомое значение ожидания для соответствующего состояния расстояния.
Численный метод полностью совпадает во всех реализациях. Ответ печатается с 10 знаками после запятой, а версии без расширенной точности дополнительно выравнивают последнюю напечатанную цифру с более точным эталоном.
После решения системы интересует только противоположное состояние \(n/2\). При \(n=100\) это означает чтение значения для расстояния \(50\):
$$3780.6186217845.$$
Некоторые реализации перед этим дополнительно проверяют рекуррентные уравнения на маленьких четных кругах, например при \(n=2\) и \(n=4\).
Построение системы занимает \(O(n)\) времени, потому что в каждой из \(n-1\) строк присутствуют только пять переходных членов. Основная стоимость связана с решением плотной системы размера \((n-1)\times(n-1)\) методом Гаусса: это \(O(n^3)\) арифметических операций и \(O(n^2)\) памяти.
Для \(n=100\) такой прямой подход вполне удобен. Главное достоинство метода в том, что задача о среднем времени встречи переводится в одну детерминированную линейную систему вместо усреднения огромного числа случайных игр.
يجلس مئة لاعب بالتساوي حول دائرة، وتبدأ نردان في موضعين متقابلين تماما. في كل جولة تتحرك كل نردة بصورة مستقلة: تنتقل مقعدا واحدا في احد الاتجاهين باحتمال \(1/6\)، او تبقى في مكانها باحتمال \(2/3\)، او تنتقل مقعدا واحدا في الاتجاه المعاكس باحتمال \(1/6\). وتنتهي المطاردة بمجرد ان تصبح النردتان في يد اللاعب نفسه.
وبما ان المسافة الابتدائية على دائرة من 100 لاعب تساوي 50 مقعدا، فالمطلوب هو عدد الجولات المتوقع حتى الوصول الى حالة الالتقاء عند البدء من المسافة الدائرية \(50\). تعطي التطبيقات القيمة \(3780.6186217845\) جولة.
التبسيط الحاسم هو تجاهل ارقام المقاعد المطلقة والاكتفاء بمتابعة المسافة الدائرية بين النردتين. عندها تتحول اللعبة كلها الى سلسلة ماركوف امتصاصية منتهية، ويمكن كتابة قانون الانتقال فيها بشكل صريح.
لتكن \(k\in\{0,1,\dots,n-1\}\) هي المسافة باتجاه عقارب الساعة من النردة الاولى الى النردة الثانية على دائرة فيها \(n=100\) لاعب. اذا قمنا بتدوير النردتين معا بالعدد نفسه من المقاعد فلن يتغير اي شيء في السلوك المستقبلي، لذلك يعتمد التوقع فقط على \(k\) لا على الموضعين المطلقين.
لنرمز بـ \(E_k\) الى عدد الجولات المتوقع المتبقي حتى تلتقي النردتان عندما تكون المسافة الحالية هي \(k\). حالة الالتقاء حالة امتصاصية، ولذلك
$$E_0=0.$$
وهناك ايضا تناظر مفيد هو
$$E_k=E_{n-k},$$
لان عكس اتجاه النظر الى الدائرة لا يفعل شيئا سوى تبديل الدوران مع وعكس عقارب الساعة. لا تستغل التطبيقات هذا الاختزال، بل تحل النظام الكامل \(E_1,\dots,E_{99}\)، لكن هذه العلاقة تبقى فحصا جيدا لصحة الاشتقاق.
لنكتب حركة نردة واحدة في جولة على صورة \(X\in\{-1,0,1\}\)، حيث
$$\Pr(X=-1)=\frac16,\qquad \Pr(X=0)=\frac23,\qquad \Pr(X=1)=\frac16.$$
اذا تحركت النردتان بمقدارين \(X_1\) و \(X_2\)، فان تغير المسافة بينهما يساوي
$$D=X_2-X_1.$$
وبضم التوزيعين الثلاثيين نحصل على الاحتمالات الخمسة الممكنة للتغير النسبي:
$$\Pr(D=-2)=\frac1{36},\qquad \Pr(D=-1)=\frac29,\qquad \Pr(D=0)=\frac12,\qquad \Pr(D=1)=\frac29,\qquad \Pr(D=2)=\frac1{36}.$$
اذن لا يمكن للمسافة في جولة واحدة الا ان تنقص 2 او 1، او تبقى كما هي، او تزيد 1 او 2، وكل ذلك يفسر بترديد \(n\).
اذا كانت الحالة الحالية \(k\neq0\)، فلابد ان تمر جولة واحدة اولا، ثم يستمر المسار من المسافة الجديدة. لذلك يعطينا تحليل الخطوة الاولى العلاقة
$$E_k=1+\frac1{36}E_{(k-2)\bmod n}+\frac29E_{(k-1)\bmod n}+\frac12E_k+\frac29E_{(k+1)\bmod n}+\frac1{36}E_{(k+2)\bmod n}$$
وذلك لكل \(1\le k\le n-1\)، مع الشرط \(E_0=0\).
وبصورة مكافئة، تحقق كل حالة غير صفرية المعادلة الخطية
$$E_k-\sum_{\delta=-2}^{2}p_\delta E_{(k+\delta)\bmod n}=1,$$
حيث \(p_{-2}=p_2=1/36\)، و\(p_{-1}=p_1=2/9\)، و\(p_0=1/2\). وعندما يكون \(k\) قريبا من \(1\) او من \(n-1\)، تلتف الفهارس حول الدائرة، ولذلك فالمصفوفة دورية وليست مجرد مصفوفة شريطية على خط مستقيم.
الحالة \(n=4\) توضح الفكرة بالكامل. المسافات غير الصفرية هي \(1,2,3\)، ومن التناظر نحصل على \(E_1=E_3\). اما وضع البداية المتقابل فيوافق الحالة \(k=2\).
عند \(k=1\)، فان الازاحات \(-2,-1,0,1,2\) تقود الى الحالات \(3,0,1,2,3\)، ولذلك
$$E_1=1+\frac1{36}E_3+\frac29E_0+\frac12E_1+\frac29E_2+\frac1{36}E_3=1+\frac59E_1+\frac29E_2.$$
وعند \(k=2\)، نحصل على الحالات \(0,1,2,3,0\)، ومن ثم
$$E_2=1+\frac29E_1+\frac12E_2+\frac29E_3=1+\frac49E_1+\frac12E_2.$$
بحل المعادلتين نجد
$$E_1=5.85,\qquad E_2=7.2.$$
هذا هو بالضبط نفس البناء الرياضي المستخدم عندما يكون عدد اللاعبين 100؛ الاختلاف الوحيد هو ان عدد المجهولات يصبح اكبر.
في المسألة الفعلية يكون \(n=100\)، ولذلك توجد 99 قيمة مجهولة هي \(E_1,\dots,E_{99}\). وبما ان النردتين تبدآن في نقطتين متقابلتين على الدائرة، فان القيمة المطلوبة هي
$$E_{50}.$$
وبعد حل هذه المعادلات الخطية المترابطة لا تكون هناك حاجة الى اي محاكاة عشوائية. النتيجة تقرأ مباشرة من الحل.
تنشئ تطبيقات C++ وPython وJava سطرا واحدا لكل مسافة غير صفرية \(k\). يبدأ كل سطر بمعامل \(E_k\) مساويا 1 في الطرف الايسر وبالثابت 1 في الطرف الايمن، ثم تطرح احتمالات الانتقال الخمسة من الاعمدة الموافقة للحالات \((k-2)\bmod n\) و\((k-1)\bmod n\) و\(k\) و\((k+1)\bmod n\) و\((k+2)\bmod n\). اما الانتقالات التي تصل الى الحالة \(0\) فتترك خارج المصفوفة لان \(E_0=0\) لا يضيف متغيرا مجهولا.
عندما يكون \(n=100\)، ينتج عن ذلك مصفوفة موسعة حجمها \(99\times100\). تكون المصفوفة متناثرة عند بنائها اول مرة، لكن حذف غاوس يملأ كثيرا من الخانات، لذلك يكون التخزين الكثيف عمليا ومباشرا.
تستخدم التطبيقات حذف غاوس مع اختيار جزئي للمحور. في كل عمود يتم جلب الصف ذي اكبر محور بالقيمة المطلقة، ثم يطبّع صف المحور، وبعد ذلك يزال هذا العمود من جميع الصفوف الاخرى. وعند انتهاء العملية تصبح الخانة الاخيرة في كل صف هي الزمن المتوقع المحسوب لتلك الحالة.
الطريقة العددية نفسها مطبقة في اللغات الثلاث. وتتم طباعة الناتج بعشرة ارقام بعد الفاصلة العشرية، كما تضبط النسخ التي لا تستخدم الدقة الموسعة اخر رقم مطبوع ليتفق مع المرجع الاعلى دقة.
بعد حل النظام لا نهتم الا بحالة المقعد المقابل \(n/2\). وعند \(n=100\) يعني هذا قراءة قيمة المسافة \(50\):
$$3780.6186217845.$$
وتقوم بعض التطبيقات ايضا بفحص العلاقة العودية على دوائر زوجية صغيرة مثل \(n=2\) و\(n=4\) قبل اعلان نتيجة المئة لاعب.
بناء المعادلات يكلف \(O(n)\) زمنا، لان كل واحد من الصفوف \(n-1\) يحتوي على خمسة حدود انتقال فقط. اما الكلفة المسيطرة فهي حل النظام الخطي الكثيف ذي الحجم \((n-1)\times(n-1)\) بحذف غاوس، وهذا يتطلب \(O(n^3)\) عملية حسابية و\(O(n^2)\) من الذاكرة.
بالنسبة الى \(n=100\)، فهذه الطريقة المباشرة معقولة تماما. والقيمة الحقيقية للفكرة هي تحويل مسألة الزمن المتوقع للالتقاء من محاكاة عشوائية طويلة الى حل خطي حتمي واحد.