Two sticks are dropped into a river. Each first passage under the bridge takes an integer number of seconds chosen uniformly from \([n,m]\). Whenever a stick emerges, it is picked up and re-dropped 5 seconds later, so every later cycle time is uniform on \([n+5,m+5]\). The race ends when one stick emerges while the other stick is still somewhere inside its previous passage, meaning that the leader is now exactly one whole passage ahead. For each pair \((m,n)\) we need the expected finishing time \(E(m,n)\), and the overall quantity is
$$S(k)=\sum_{m=2}^{k}\sum_{n=1}^{m-1}E(m,n).$$
The key observation is that after the first emergence, the full history is irrelevant: only the current time gap and the current race phase matter.
Fix one pair \((n,m)\). Write
$$u=n+5,\qquad v=m+5,\qquad q=v-u+1=m-n+1.$$
After the first bridge passage, every new cycle time is an independent uniform draw from \(\{u,u+1,\dots,v\}\).
The first trip of each stick does not include the 5-second re-drop delay, so the initial draw is uniform on \(\{n,\dots,m\}\). After the first emergence, every future trip does include that delay, which is why the later process uses \(\{u,\dots,v\}\). This separation explains why the implementation treats the opening move differently from the recursive part.
Once the first stick has emerged, the only information that matters is how many seconds remain until the other stick emerges, together with whether the race is in a balanced situation or in a one-pass lead situation.
For each integer gap \(r\in\{1,\dots,v\}\), define two expectations:
Let \(X_r\) denote the expected remaining time in the balanced phase with gap \(r\).
Let \(Y_r\) denote the expected remaining time in the one-pass lead phase with gap \(r\).
The balanced phase means that the next emergence will create a one-pass lead but cannot end the race immediately. The one-pass lead phase means that the stick that has just been re-dropped will win immediately if it emerges again before the other stick finishes its current passage.
Simultaneous emergence creates a fresh cycle with a new remaining time distributed uniformly over \(\{u,\dots,v\}\). Therefore we also need the averages
$$\bar X=\frac{1}{q}\sum_{r=u}^{v}X_r,\qquad \bar Y=\frac{1}{q}\sum_{r=u}^{v}Y_r.$$
Suppose we are in the balanced phase with gap \(r\), and let \(T\) be the next full cycle time of the stick that was just re-dropped. There are three cases.
If \(T<r\), that stick emerges first after \(T\) seconds. The race is still alive, but now one stick has a one-pass lead and the new gap is \(r-T\), so the continuation is \(Y_{r-T}\).
If \(T=r\), both sticks emerge together after \(r\) seconds. The process restarts in the balanced phase, and the continuation is the averaged quantity \(\bar X\).
If \(T>r\), the other stick emerges first after \(r\) seconds. The race moves to the one-pass lead phase with new gap \(T-r\), so the continuation is \(Y_{T-r}\).
Because \(T\) is uniform on \(\{u,\dots,v\}\), we obtain
$$X_r=\frac{1}{q}\left(\sum_{t=u}^{\min(v,r-1)}\left(t+Y_{r-t}\right)+\mathbf{1}_{u\le r\le v}\left(r+\bar X\right)+\sum_{t=\max(u,r+1)}^{v}\left(r+Y_{t-r}\right)\right).$$
Now suppose we are in the one-pass lead phase with gap \(r\). Again let \(T\) be the next full cycle time of the stick that has just been re-dropped.
If \(T<r\), that leading stick emerges again before the other one finishes its current passage. At that exact moment the race ends, so the additional time is simply \(T\).
If \(T=r\), both sticks emerge together after \(r\) seconds. The lead phase survives, but the exact gap is reset by a fresh uniform draw, so the continuation is \(\bar Y\).
If \(T>r\), the lagging stick emerges first after \(r\) seconds and catches up to the balanced phase. The new gap is \(T-r\), so the continuation is \(X_{T-r}\).
This gives
$$Y_r=\frac{1}{q}\left(\sum_{t=u}^{\min(v,r-1)}t+\mathbf{1}_{u\le r\le v}\left(r+\bar Y\right)+\sum_{t=\max(u,r+1)}^{v}\left(r+X_{t-r}\right)\right).$$
The opening passage times of the two sticks are independent uniform draws \(T_1,T_2\in\{n,\dots,m\}\).
If \(T_1<T_2\), the first stick emerges after \(T_1\) seconds and the race enters the one-pass lead phase with gap \(T_2-T_1\), contributing \(T_1+Y_{T_2-T_1}\).
If \(T_2<T_1\), the contribution is \(T_2+Y_{T_1-T_2}\).
If \(T_1=T_2\), both sticks emerge together and the continuation is the balanced average \(\bar X\), contributing \(T_1+\bar X\).
Therefore
$$E(m,n)=\frac{1}{q^2}\left(\sum_{n\le t_1<t_2\le m}\left(t_1+Y_{t_2-t_1}\right)+\sum_{n\le t_2<t_1\le m}\left(t_2+Y_{t_1-t_2}\right)+\sum_{t=n}^{m}\left(t+\bar X\right)\right).$$
Here the later cycle times are \(u=6\), \(v=7\), and \(q=2\). The averaged states become
$$\bar X=\frac{X_6+X_7}{2},\qquad \bar Y=\frac{Y_6+Y_7}{2}.$$
Consider the one-pass lead phase with gap \(r=1\). Since every later cycle time is either 6 or 7, the leader cannot win immediately. After 1 second the trailing stick must emerge first, so
$$Y_1=1+\frac{X_5+X_6}{2}.$$
Now consider the balanced phase with gap \(r=6\). If the new cycle time is 6, both sticks emerge together and the continuation is \(\bar X\). If the new cycle time is 7, the other stick emerges first after 6 seconds and the process moves to \(Y_1\). Hence
$$X_6=6+\frac{\bar X+Y_1}{2}.$$
At the very start, the ordered opening pairs \((1,2)\) and \((2,1)\) each contribute \(1+Y_1\), while the ties \((1,1)\) and \((2,2)\) contribute \(1+\bar X\) and \(2+\bar X\). This small example shows exactly how the state equations mirror the race rules.
The C++, Python, and Java implementations solve one pair \((n,m)\) at a time. For each possible gap \(r\), they precompute which cycle times are smaller than \(r\), equal to \(r\), or larger than \(r\), together with the corresponding counts and time sums. That turns the first-step formulas above into a linear system whose unknowns are
$$X_1,\dots,X_v,\qquad Y_1,\dots,Y_v,\qquad \bar X,\qquad \bar Y.$$
The system therefore has size
$$2v+2.$$
The implementation fills the coefficient matrix directly from the transition ranges and solves it by Gaussian elimination with partial pivoting. After that, it averages over all opening pairs \((T_1,T_2)\) to obtain \(E(m,n)\). Finally it sums those expectations over every \(1\le n<m\le k\) to obtain \(S(k)\). The Python version delegates to the compiled solver, while the C++ and Java versions implement the same linear-algebra model explicitly; the C++ version also parallelizes the outer summation.
For a fixed pair \((n,m)\), the matrix dimension is \(2v+2=2m+12\). Filling the dense matrix from the interval transitions costs \(O(v^2)\) time, Gaussian elimination costs \(O(v^3)\) time, and the memory usage is \(O(v^2)\). The final opening-pair average contributes only \(O((m-n+1)^2)\), which is smaller than the elimination step for the actual parameter range.
Summing over all pairs for \(S(k)\) gives
$$\sum_{m=2}^{k}\sum_{n=1}^{m-1}O((m+5)^3)=O(k^5),$$
with peak memory determined by the largest single system, namely \(O(k^2)\).
Zwei Stöcke werden in den Fluss geworfen. Die erste Passage unter der Brücke dauert jeweils eine ganzzahlige Zahl von Sekunden, gleichverteilt auf \([n,m]\). Sobald ein Stock auftaucht, wird er aufgenommen und 5 Sekunden später erneut eingesetzt. Deshalb ist jede spätere Zykluszeit gleichverteilt auf \([n+5,m+5]\). Das Rennen endet genau dann, wenn ein Stock erneut auftaucht, während der andere noch in seiner vorherigen Passage steckt; der Führende ist dann genau eine ganze Passage voraus. Für jedes Paar \((m,n)\) wird die erwartete Rennzeit \(E(m,n)\) gesucht, und insgesamt berechnet man
$$S(k)=\sum_{m=2}^{k}\sum_{n=1}^{m-1}E(m,n).$$
Entscheidend ist, dass nach dem ersten Auftauchen nicht mehr die gesamte Vorgeschichte zählt, sondern nur noch die aktuelle Zeitlücke und die aktuelle Rennphase.
Fixiere ein Paar \((n,m)\) und setze
$$u=n+5,\qquad v=m+5,\qquad q=v-u+1=m-n+1.$$
Nach der ersten Passage ist jede neue Zykluszeit also eine unabhängige Gleichverteilung auf \(\{u,u+1,\dots,v\}\).
Die allererste Brückenpassage enthält die 5 Sekunden Wiedereinsetzen noch nicht, also wird anfangs auf \(\{n,\dots,m\}\) gezogen. Ab dem ersten Auftauchen enthält jede weitere Runde diese Zusatzzeit, daher arbeitet der rekursive Teil mit \(\{u,\dots,v\}\). Genau deshalb behandelt die Implementierung den Anfang separat und danach nur noch den stationären Rennmechanismus.
Nach dem ersten Auftauchen genügt es zu wissen, wie viele Sekunden bis zum Auftauchen des anderen Stocks verbleiben und ob das Rennen gerade im ausgeglichenen Zustand oder in einer Ein-Passage-Führungsphase ist.
Für jede ganzzahlige Lücke \(r\in\{1,\dots,v\}\) definieren wir zwei Erwartungen:
Sei \(X_r\) die erwartete Restzeit in der ausgeglichenen Phase mit Lücke \(r\).
Sei \(Y_r\) die erwartete Restzeit in der Ein-Passage-Führungsphase mit Lücke \(r\).
Die ausgeglichene Phase bedeutet: Das nächste Auftauchen erzeugt zwar eine Führung von einer Passage, beendet das Rennen aber noch nicht sofort. Die Führungsphase bedeutet: Der gerade erneut eingesetzte Stock gewinnt sofort, falls er noch einmal auftaucht, bevor der andere seine aktuelle Passage beendet.
Bei gleichzeitigem Auftauchen startet ein frischer Zyklus, dessen neue Restzeit gleichverteilt in \(\{u,\dots,v\}\) liegt. Deshalb braucht man außerdem die Mittelwerte
$$\bar X=\frac{1}{q}\sum_{r=u}^{v}X_r,\qquad \bar Y=\frac{1}{q}\sum_{r=u}^{v}Y_r.$$
Angenommen, wir befinden uns in der ausgeglichenen Phase mit Lücke \(r\), und \(T\) sei die nächste volle Zykluszeit des gerade erneut eingesetzten Stocks. Dann gibt es drei Fälle.
Falls \(T<r\), taucht dieser Stock nach \(T\) Sekunden zuerst auf. Das Rennen ist noch nicht vorbei, aber nun liegt eine Führung von einer Passage vor und die neue Lücke ist \(r-T\). Die Fortsetzung ist also \(Y_{r-T}\).
Falls \(T=r\), tauchen beide Stöcke nach \(r\) Sekunden gleichzeitig auf. Der Prozess startet erneut in der ausgeglichenen Phase, und die Fortsetzung ist der Mittelwert \(\bar X\).
Falls \(T>r\), taucht der andere Stock zuerst nach \(r\) Sekunden auf. Das Rennen wechselt in die Führungsphase mit neuer Lücke \(T-r\), also ist die Fortsetzung \(Y_{T-r}\).
Da \(T\) gleichverteilt auf \(\{u,\dots,v\}\) ist, folgt
$$X_r=\frac{1}{q}\left(\sum_{t=u}^{\min(v,r-1)}\left(t+Y_{r-t}\right)+\mathbf{1}_{u\le r\le v}\left(r+\bar X\right)+\sum_{t=\max(u,r+1)}^{v}\left(r+Y_{t-r}\right)\right).$$
Nun sei die Rennphase eine Ein-Passage-Führung mit Lücke \(r\). Wieder sei \(T\) die nächste volle Zykluszeit des gerade erneut eingesetzten Stocks.
Falls \(T<r\), taucht der führende Stock erneut auf, bevor der andere seine aktuelle Passage beendet. Genau in diesem Moment ist das Rennen beendet, also beträgt die zusätzliche Zeit schlicht \(T\).
Falls \(T=r\), tauchen beide nach \(r\) Sekunden gleichzeitig auf. Die Führungsphase bleibt bestehen, aber die konkrete Lücke wird durch einen neuen gleichverteilten Zug ersetzt, daher ist die Fortsetzung \(\bar Y\).
Falls \(T>r\), taucht der zurückliegende Stock zuerst nach \(r\) Sekunden auf und gleicht damit zur ausgeglichenen Phase aus. Die neue Lücke ist \(T-r\), also folgt \(X_{T-r}\).
Damit erhält man
$$Y_r=\frac{1}{q}\left(\sum_{t=u}^{\min(v,r-1)}t+\mathbf{1}_{u\le r\le v}\left(r+\bar Y\right)+\sum_{t=\max(u,r+1)}^{v}\left(r+X_{t-r}\right)\right).$$
Die anfänglichen Passagezeiten der beiden Stöcke sind unabhängige Gleichverteilungen \(T_1,T_2\in\{n,\dots,m\}\).
Ist \(T_1<T_2\), so taucht der erste Stock nach \(T_1\) Sekunden auf, und das Rennen wechselt in die Führungsphase mit Lücke \(T_2-T_1\). Der Beitrag ist also \(T_1+Y_{T_2-T_1}\).
Ist \(T_2<T_1\), so ist der Beitrag \(T_2+Y_{T_1-T_2}\).
Bei \(T_1=T_2\) tauchen beide gleichzeitig auf, und die Fortsetzung ist der ausgeglichene Mittelwert \(\bar X\). Der Beitrag lautet dann \(T_1+\bar X\).
Somit gilt
$$E(m,n)=\frac{1}{q^2}\left(\sum_{n\le t_1<t_2\le m}\left(t_1+Y_{t_2-t_1}\right)+\sum_{n\le t_2<t_1\le m}\left(t_2+Y_{t_1-t_2}\right)+\sum_{t=n}^{m}\left(t+\bar X\right)\right).$$
Hier sind die späteren Zykluszeiten \(u=6\), \(v=7\) und \(q=2\). Die gemittelten Zustände lauten
$$\bar X=\frac{X_6+X_7}{2},\qquad \bar Y=\frac{Y_6+Y_7}{2}.$$
Betrachte die Führungsphase mit Lücke \(r=1\). Da jede spätere Zykluszeit 6 oder 7 ist, kann der Führende nicht sofort gewinnen. Nach 1 Sekunde muss der zurückliegende Stock zuerst auftauchen, also
$$Y_1=1+\frac{X_5+X_6}{2}.$$
Betrachte nun die ausgeglichene Phase mit Lücke \(r=6\). Ist die neue Zykluszeit 6, tauchen beide gleichzeitig auf und die Fortsetzung ist \(\bar X\). Ist sie 7, taucht der andere Stock nach 6 Sekunden zuerst auf und der Prozess wechselt zu \(Y_1\). Daher
$$X_6=6+\frac{\bar X+Y_1}{2}.$$
Zu Beginn tragen die geordneten Anfangspaare \((1,2)\) und \((2,1)\) jeweils \(1+Y_1\) bei, während die Gleichstände \((1,1)\) und \((2,2)\) die Beiträge \(1+\bar X\) beziehungsweise \(2+\bar X\) liefern. Das kleine Beispiel zeigt genau, wie die Zustandsgleichungen die Rennregeln abbilden.
Die C++-, Python- und Java-Implementierungen lösen jeweils ein Paar \((n,m)\) nach dem anderen. Für jede mögliche Lücke \(r\) werden vorab die Zykluszeiten bestimmt, die kleiner als \(r\), gleich \(r\) oder größer als \(r\) sind, samt der zugehörigen Anzahlen und Zeitsummen. Dadurch werden die obigen Erstschrittformeln zu einem linearen Gleichungssystem mit den Unbekannten
$$X_1,\dots,X_v,\qquad Y_1,\dots,Y_v,\qquad \bar X,\qquad \bar Y.$$
Die Systemgröße ist also
$$2v+2.$$
Die Implementierung füllt die Koeffizientenmatrix direkt aus den Übergangsintervallen und löst sie mit Gauß-Elimination samt partieller Pivotisierung. Anschließend wird über alle Anfangspaare \((T_1,T_2)\) gemittelt, um \(E(m,n)\) zu erhalten. Danach summiert das Programm über alle \(1\le n<m\le k\), um \(S(k)\) zu berechnen. Die Python-Version delegiert an den kompilierten Solver, während C++ und Java dasselbe lineare Modell direkt aufbauen; die C++-Version parallelisiert zusätzlich die äußere Summation.
Für ein festes Paar \((n,m)\) hat die Matrix die Dimension \(2v+2=2m+12\). Das Füllen der dichten Matrix aus den Intervallübergängen kostet \(O(v^2)\) Zeit, die Gauß-Elimination \(O(v^3)\) Zeit, und der Speicherbedarf beträgt \(O(v^2)\). Die abschließende Mittelung über alle Anfangspaare benötigt nur \(O((m-n+1)^2)\) und ist im relevanten Bereich kleiner als der Eliminationsschritt.
Über alle Paare für \(S(k)\) ergibt sich
$$\sum_{m=2}^{k}\sum_{n=1}^{m-1}O((m+5)^3)=O(k^5),$$
wobei der Spitzenspeicher durch das größte einzelne Gleichungssystem bestimmt wird, also \(O(k^2)\) beträgt.
İki çubuk nehre bırakılıyor. Her bir çubuğun köprünün altından ilk geçiş süresi \([n,m]\) aralığındaki tam sayılar üzerinde eşit olasılıklı. Bir çubuk sudan çıktığında alınarak 5 saniye sonra yeniden bırakılıyor; bu yüzden ilk geçişten sonraki her yeni tur süresi \([n+5,m+5]\) aralığında eşit olasılıklı oluyor. Yarış, bir çubuk yeniden ortaya çıktığında diğer çubuk hâlâ önceki geçişini tamamlamamışsa bitiyor; yani öndeki çubuk tam bir geçiş kadar öne geçmiş oluyor. Her \((m,n)\) çifti için beklenen bitiş süresi \(E(m,n)\), toplam olarak da
$$S(k)=\sum_{m=2}^{k}\sum_{n=1}^{m-1}E(m,n)$$
hesaplanıyor. Esas fikir, ilk ortaya çıkıştan sonra tüm geçmişin gereksiz olmasıdır: yalnızca mevcut zaman farkı ve yarışın hangi fazda olduğu önemlidir.
Sabit bir \((n,m)\) çifti için
$$u=n+5,\qquad v=m+5,\qquad q=v-u+1=m-n+1$$
tanımlarını yapalım. İlk geçişten sonraki her yeni tur süresi artık \(\{u,u+1,\dots,v\}\) kümesinden bağımsız ve eşit olasılıklı seçilir.
En baştaki geçişte 5 saniyelik yeniden bırakma gecikmesi henüz yoktur; bu nedenle başlangıç çekilişi \(\{n,\dots,m\}\) aralığındadır. İlk ortaya çıkıştan sonra ise her yeni tur bu ek gecikmeyi içerir ve süreç \(\{u,\dots,v\}\) ile devam eder. Uygulamanın açılışı ayrı, geri kalanını ise özyinelemeli biçimde ele almasının nedeni tam olarak budur.
İlk ortaya çıkıştan sonra bilinmesi gereken iki şey vardır: diğer çubuğun çıkmasına kaç saniye kaldığı ve yarışın dengeli fazda mı yoksa bir geçiş önde olunan fazda mı olduğu.
Her \(r\in\{1,\dots,v\}\) tam sayı farkı için iki beklenti tanımlayalım:
\(X_r\), denge fazında fark \(r\) iken beklenen kalan süredir.
\(Y_r\), bir geçiş önde olunan fazda fark \(r\) iken beklenen kalan süredir.
Denge fazı, sıradaki ortaya çıkışın hemen oyunu bitirmeyeceği ama bir geçişlik üstünlük yaratacağı durumdur. Önde olunan faz ise, yeniden bırakılan öndeki çubuğun diğer çubuk mevcut geçişini tamamlamadan tekrar çıkarsa oyunun anında biteceği durumdur.
Eğer iki çubuk aynı anda ortaya çıkarsa süreç taze bir kalan süre ile yeniden başlar ve bu süre \(\{u,\dots,v\}\) üzerinde eşit olasılıklıdır. Bu yüzden şu ortalamalara da ihtiyaç vardır:
$$\bar X=\frac{1}{q}\sum_{r=u}^{v}X_r,\qquad \bar Y=\frac{1}{q}\sum_{r=u}^{v}Y_r.$$
Denge fazında fark \(r\) olsun ve yeniden bırakılan çubuğun bir sonraki tam tur süresi \(T\) olsun. Üç durum vardır.
\(T<r\) ise bu çubuk \(T\) saniye sonra önce çıkar. Oyun hemen bitmez; fakat artık bir çubuk bir geçiş öne geçmiştir ve yeni fark \(r-T\) olur. Devam beklentisi \(Y_{r-T}\) olur.
\(T=r\) ise iki çubuk \(r\) saniye sonra birlikte çıkar. Süreç yeniden denge fazına döner ve devam beklentisi ortalama değer \(\bar X\) olur.
\(T>r\) ise diğer çubuk \(r\) saniye sonra önce çıkar. Süreç yeni fark \(T-r\) ile önde olunan faza geçer; devam beklentisi \(Y_{T-r}\) olur.
\(T\), \(\{u,\dots,v\}\) üzerinde eşit olasılıklı olduğundan
$$X_r=\frac{1}{q}\left(\sum_{t=u}^{\min(v,r-1)}\left(t+Y_{r-t}\right)+\mathbf{1}_{u\le r\le v}\left(r+\bar X\right)+\sum_{t=\max(u,r+1)}^{v}\left(r+Y_{t-r}\right)\right)$$
elde edilir.
Şimdi fazın bir geçiş önde olma fazı ve farkın \(r\) olduğunu düşünelim. Yine \(T\), yeniden bırakılan öndeki çubuğun bir sonraki tam tur süresi olsun.
\(T<r\) ise öndeki çubuk diğer çubuk mevcut geçişini bitirmeden önce tekrar ortaya çıkar. Yarış tam bu anda biter; ek süre yalnızca \(T\)'dir.
\(T=r\) ise iki çubuk \(r\) saniye sonra birlikte ortaya çıkar. Faz tipi korunur fakat somut fark yeni bir eşit olasılıklı çekilişle yenilenir; bu yüzden devam beklentisi \(\bar Y\) olur.
\(T>r\) ise gerideki çubuk \(r\) saniye sonra önce ortaya çıkar ve yarış yeniden denge fazına döner. Yeni fark \(T-r\) olduğu için devam beklentisi \(X_{T-r}\) olur.
Dolayısıyla
$$Y_r=\frac{1}{q}\left(\sum_{t=u}^{\min(v,r-1)}t+\mathbf{1}_{u\le r\le v}\left(r+\bar Y\right)+\sum_{t=\max(u,r+1)}^{v}\left(r+X_{t-r}\right)\right)$$
olur.
Başlangıçta iki çubuğun ilk geçiş süreleri bağımsız olarak \(T_1,T_2\in\{n,\dots,m\}\) kümesinden gelir.
\(T_1<T_2\) ise ilk çubuk \(T_1\) saniyede çıkar ve yarış farkı \(T_2-T_1\) olan önde olma fazına girer. Katkı \(T_1+Y_{T_2-T_1}\) olur.
\(T_2<T_1\) ise katkı \(T_2+Y_{T_1-T_2}\) olur.
\(T_1=T_2\) ise iki çubuk birlikte çıkar ve devam beklentisi denge ortalaması \(\bar X\) olur. Bu durumda katkı \(T_1+\bar X\)'tir.
Böylece
$$E(m,n)=\frac{1}{q^2}\left(\sum_{n\le t_1<t_2\le m}\left(t_1+Y_{t_2-t_1}\right)+\sum_{n\le t_2<t_1\le m}\left(t_2+Y_{t_1-t_2}\right)+\sum_{t=n}^{m}\left(t+\bar X\right)\right)$$
elde edilir.
Bu durumda sonraki tur süreleri \(u=6\), \(v=7\) ve \(q=2\)'dir. Ortalama durumlar
$$\bar X=\frac{X_6+X_7}{2},\qquad \bar Y=\frac{Y_6+Y_7}{2}$$
şeklindedir.
Farkı \(r=1\) olan önde olma fazını düşünelim. Sonraki tur süresi yalnızca 6 veya 7 olabileceği için lider hemen kazanamaz. 1 saniye sonra gerideki çubuk mutlaka önce ortaya çıkar ve
$$Y_1=1+\frac{X_5+X_6}{2}$$
olur.
Şimdi farkı \(r=6\) olan denge fazını düşünelim. Yeni tur süresi 6 ise iki çubuk birlikte çıkar ve devam \(\bar X\) olur. Yeni tur süresi 7 ise diğer çubuk 6 saniye sonra önce çıkar ve süreç \(Y_1\)'e gider. Bu yüzden
$$X_6=6+\frac{\bar X+Y_1}{2}.$$
Başlangıçta sıralı \((1,2)\) ve \((2,1)\) çiftleri \(1+Y_1\) katkısı yaparken, eşitlik durumları \((1,1)\) ve \((2,2)\) sırasıyla \(1+\bar X\) ve \(2+\bar X\) katkısı yapar. Bu küçük örnek, durum denklemlerinin yarış kurallarını nasıl taşıdığını açıkça gösterir.
C++, Python ve Java uygulamaları her \((n,m)\) çifti için aynı modeli çözer. Her olası \(r\) farkı için, tur sürelerinin hangilerinin \(r\)'den küçük, eşit veya büyük olduğu önceden hesaplanır; buna karşılık gelen adetler ve zaman toplamları da çıkarılır. Böylece yukarıdaki ilk-adım bağıntıları şu bilinmeyenlere sahip doğrusal bir sisteme dönüşür:
$$X_1,\dots,X_v,\qquad Y_1,\dots,Y_v,\qquad \bar X,\qquad \bar Y.$$
Sistemin boyutu
$$2v+2$$
olur. Uygulama katsayı matrisini bu geçiş aralıklarından doğrudan kurar ve sistemi kısmi pivotlamalı Gaussian elimination ile çözer. Ardından tüm başlangıç çiftleri \((T_1,T_2)\) üzerinde ortalama alınarak \(E(m,n)\) bulunur. Son olarak tüm \(1\le n<m\le k\) çiftleri toplanarak \(S(k)\) elde edilir. Python sürümü derlenmiş çözücüye delegasyon yapar; C++ ve Java sürümleri aynı lineer cebir modelini doğrudan uygular. C++ sürümü ayrıca dış toplamı paralelleştirir.
Sabit bir \((n,m)\) çifti için matris boyutu \(2v+2=2m+12\)'dir. Yoğun matrisin aralık geçişlerinden kurulması \(O(v^2)\) zaman, Gaussian elimination \(O(v^3)\) zaman ve \(O(v^2)\) bellek ister. Başlangıç çiftleri üzerinden son ortalama yalnızca \(O((m-n+1)^2)\) maliyet getirir; gerçek parametrelerde baskın adım lineer sistem çözümüdür.
\(S(k)\) için tüm çiftler toplandığında
$$\sum_{m=2}^{k}\sum_{n=1}^{m-1}O((m+5)^3)=O(k^5)$$
elde edilir; tepe bellek kullanımı ise en büyük tek sistemden geldiği için \(O(k^2)\)'dir.
Se lanzan dos palitos al río. El tiempo de la primera pasada bajo el puente de cada uno es un entero uniforme en \([n,m]\). Cuando un palito sale, se recoge y se vuelve a soltar 5 segundos después; por eso, cada ciclo posterior tiene tiempo uniforme en \([n+5,m+5]\). La carrera termina cuando un palito reaparece mientras el otro todavía sigue dentro de su pasada anterior; en ese instante el líder ya está exactamente una pasada completa por delante. Para cada par \((m,n)\) hay que calcular el tiempo esperado \(E(m,n)\), y el total pedido es
$$S(k)=\sum_{m=2}^{k}\sum_{n=1}^{m-1}E(m,n).$$
La observación central es que, después de la primera salida, toda la historia anterior deja de importar: sólo cuentan la diferencia temporal actual y la fase actual de la carrera.
Fijemos un par \((n,m)\) y escribamos
$$u=n+5,\qquad v=m+5,\qquad q=v-u+1=m-n+1.$$
Después de la primera pasada, cada nuevo tiempo de ciclo es una variable uniforme e independiente en \(\{u,u+1,\dots,v\}\).
La primera travesía todavía no incluye el retraso de 5 segundos por volver a soltar el palito, así que la extracción inicial vive en \(\{n,\dots,m\}\). A partir de la primera salida, todas las rondas futuras sí incluyen ese retraso y por eso usan \(\{u,\dots,v\}\). Esta separación explica por qué la implementación trata el arranque de forma distinta del bloque recursivo principal.
Tras la primera salida, la información relevante se reduce a dos datos: cuántos segundos faltan para que salga el otro palito y si la carrera está en una fase equilibrada o en una fase donde uno ya lleva una pasada de ventaja.
Para cada brecha entera \(r\in\{1,\dots,v\}\), definimos dos esperanzas:
Sea \(X_r\) el tiempo restante esperado en la fase equilibrada con brecha \(r\).
Sea \(Y_r\) el tiempo restante esperado en la fase con una pasada de ventaja y brecha \(r\).
La fase equilibrada significa que la próxima salida creará una ventaja de una pasada, pero no acabará la carrera inmediatamente. La fase de ventaja significa que el palito que acaba de ser relanzado ganará en cuanto vuelva a salir antes de que el otro termine su pasada actual.
Si ambos salen al mismo tiempo, el proceso se reinicia con un nuevo tiempo restante uniforme en \(\{u,\dots,v\}\). Por eso también necesitamos los promedios
$$\bar X=\frac{1}{q}\sum_{r=u}^{v}X_r,\qquad \bar Y=\frac{1}{q}\sum_{r=u}^{v}Y_r.$$
Supongamos que estamos en la fase equilibrada con brecha \(r\), y sea \(T\) el siguiente tiempo de ciclo completo del palito que se acaba de volver a soltar. Hay tres casos.
Si \(T<r\), ese palito sale primero tras \(T\) segundos. La carrera todavía no termina, pero ahora ya existe una ventaja de una pasada y la nueva brecha es \(r-T\), así que la continuación es \(Y_{r-T}\).
Si \(T=r\), ambos palitos salen simultáneamente tras \(r\) segundos. El proceso vuelve a la fase equilibrada y la continuación es el promedio \(\bar X\).
Si \(T>r\), el otro palito sale primero tras \(r\) segundos. La carrera pasa a la fase de ventaja con nueva brecha \(T-r\), de modo que la continuación es \(Y_{T-r}\).
Como \(T\) es uniforme en \(\{u,\dots,v\}\), obtenemos
$$X_r=\frac{1}{q}\left(\sum_{t=u}^{\min(v,r-1)}\left(t+Y_{r-t}\right)+\mathbf{1}_{u\le r\le v}\left(r+\bar X\right)+\sum_{t=\max(u,r+1)}^{v}\left(r+Y_{t-r}\right)\right).$$
Ahora supongamos que ya estamos en la fase donde un palito lleva una pasada de ventaja y la brecha es \(r\). Sea de nuevo \(T\) el siguiente tiempo completo del palito recién relanzado.
Si \(T<r\), el líder vuelve a salir antes de que el otro termine su pasada actual. En ese instante la carrera termina, así que el tiempo adicional es simplemente \(T\).
Si \(T=r\), ambos salen a la vez tras \(r\) segundos. La fase de ventaja se mantiene, pero la brecha concreta se reinicia mediante una nueva extracción uniforme, por lo que la continuación es \(\bar Y\).
Si \(T>r\), el palito rezagado sale primero tras \(r\) segundos y la carrera regresa a la fase equilibrada. La nueva brecha es \(T-r\), de modo que la continuación es \(X_{T-r}\).
Así se obtiene
$$Y_r=\frac{1}{q}\left(\sum_{t=u}^{\min(v,r-1)}t+\mathbf{1}_{u\le r\le v}\left(r+\bar Y\right)+\sum_{t=\max(u,r+1)}^{v}\left(r+X_{t-r}\right)\right).$$
Los tiempos iniciales de las dos primeras pasadas son variables independientes \(T_1,T_2\in\{n,\dots,m\}\).
Si \(T_1<T_2\), el primer palito sale tras \(T_1\) segundos y la carrera entra en la fase de ventaja con brecha \(T_2-T_1\). Su contribución es \(T_1+Y_{T_2-T_1}\).
Si \(T_2<T_1\), la contribución es \(T_2+Y_{T_1-T_2}\).
Si \(T_1=T_2\), ambos salen a la vez y la continuación es el promedio equilibrado \(\bar X\), por lo que la contribución es \(T_1+\bar X\).
Por tanto,
$$E(m,n)=\frac{1}{q^2}\left(\sum_{n\le t_1<t_2\le m}\left(t_1+Y_{t_2-t_1}\right)+\sum_{n\le t_2<t_1\le m}\left(t_2+Y_{t_1-t_2}\right)+\sum_{t=n}^{m}\left(t+\bar X\right)\right).$$
Aquí los tiempos de ciclo posteriores son \(u=6\), \(v=7\) y \(q=2\). Los estados promedio son
$$\bar X=\frac{X_6+X_7}{2},\qquad \bar Y=\frac{Y_6+Y_7}{2}.$$
Consideremos la fase de ventaja con brecha \(r=1\). Como el siguiente ciclo sólo puede durar 6 o 7, el líder no puede ganar inmediatamente. Tras 1 segundo el rezagado tiene que salir primero, así que
$$Y_1=1+\frac{X_5+X_6}{2}.$$
Ahora tomemos la fase equilibrada con brecha \(r=6\). Si el nuevo ciclo dura 6, ambos salen a la vez y la continuación es \(\bar X\). Si dura 7, el otro palito sale primero tras 6 segundos y el proceso pasa a \(Y_1\). Por tanto,
$$X_6=6+\frac{\bar X+Y_1}{2}.$$
En el inicio, los pares ordenados \((1,2)\) y \((2,1)\) aportan cada uno \(1+Y_1\), mientras que los empates \((1,1)\) y \((2,2)\) aportan \(1+\bar X\) y \(2+\bar X\). Este ejemplo pequeño muestra con claridad cómo las ecuaciones de estado reproducen las reglas del juego.
Las implementaciones en C++, Python y Java resuelven un par \((n,m)\) cada vez. Para cada brecha posible \(r\), precalculan qué tiempos de ciclo son menores que \(r\), cuáles son iguales y cuáles son mayores, junto con sus cantidades y sumas temporales. De ese modo, las fórmulas de primer paso se convierten en un sistema lineal cuyas incógnitas son
$$X_1,\dots,X_v,\qquad Y_1,\dots,Y_v,\qquad \bar X,\qquad \bar Y.$$
El sistema tiene tamaño
$$2v+2.$$
La implementación llena la matriz de coeficientes directamente a partir de los intervalos de transición y la resuelve mediante eliminación gaussiana con pivoteo parcial. Después promedia sobre todos los pares iniciales \((T_1,T_2)\) para obtener \(E(m,n)\). Finalmente suma esas esperanzas sobre todos los pares \(1\le n<m\le k\) para producir \(S(k)\). La versión de Python delega en el solucionador compilado, mientras que C++ y Java construyen explícitamente el mismo modelo lineal; además, la versión de C++ paraleliza la suma externa.
Para un par fijo \((n,m)\), la dimensión de la matriz es \(2v+2=2m+12\). Construir la matriz densa a partir de los intervalos cuesta \(O(v^2)\) tiempo, la eliminación gaussiana cuesta \(O(v^3)\) tiempo y la memoria es \(O(v^2)\). El promedio final sobre los pares iniciales requiere sólo \(O((m-n+1)^2)\), por lo que queda dominado por la resolución del sistema.
Al sumar todos los pares para \(S(k)\), se obtiene
$$\sum_{m=2}^{k}\sum_{n=1}^{m-1}O((m+5)^3)=O(k^5),$$
y la memoria máxima queda fijada por el mayor sistema individual, es decir, \(O(k^2)\).
有两根木棍被投入河中。每根木棍第一次通过桥下所需的时间，是区间 \([n,m]\) 上的等概率整数。一旦某根木棍浮出水面，就要先捞起，再过 5 秒重新投入，因此第一次之后的每一轮完整循环时间都变成区间 \([n+5,m+5]\) 上的等概率整数。比赛结束的条件是：某根木棍再次浮出时，另一根木棍还停留在它上一轮的通过过程中，此时领先者恰好整整领先一轮。对每个 \((m,n)\) 都要求出期望比赛时长 \(E(m,n)\)，再计算
$$S(k)=\sum_{m=2}^{k}\sum_{n=1}^{m-1}E(m,n).$$
真正重要的观察是：第一次浮出之后，完整历史已经不再需要保存，系统只取决于当前的时间差以及当前处于哪一种比赛阶段。
固定一个参数对 \((n,m)\)，记
$$u=n+5,\qquad v=m+5,\qquad q=v-u+1=m-n+1.$$
这样，第一次之后的每个新循环时间，都是从 \(\{u,u+1,\dots,v\}\) 中独立且等概率地抽取。
最开始那一次通过还没有包含“捞起再重投”的 5 秒延迟，因此初始时间来自 \(\{n,\dots,m\}\)。从第一次浮出之后开始，每一轮都要加上这 5 秒，所以递推部分使用的是 \(\{u,\dots,v\}\)。这正是实现中把“开局一步”和“后续递推”分开处理的原因。
第一次浮出之后，真正需要记录的只有两项信息：另一根木棍还要多久才会浮出，以及当前局面属于“平衡阶段”还是“领先一轮阶段”。
对每个整数时间差 \(r\in\{1,\dots,v\}\)，定义两类期望：
记 \(X_r\) 为平衡阶段、时间差为 \(r\) 时的期望剩余时间。
记 \(Y_r\) 为领先一轮阶段、时间差为 \(r\) 时的期望剩余时间。
所谓平衡阶段，是指下一次浮出只会制造出“一轮领先”，但不会立刻结束比赛。所谓领先一轮阶段，是指刚刚被重新投入的那根领先木棍，如果在另一根木棍完成当前通过之前再次浮出，就会立即获胜。
如果两根木棍同时浮出，那么系统会以一个新的剩余时间重新开始，而这个新的剩余时间在 \(\{u,\dots,v\}\) 上均匀分布。因此还需要两个平均量
$$\bar X=\frac{1}{q}\sum_{r=u}^{v}X_r,\qquad \bar Y=\frac{1}{q}\sum_{r=u}^{v}Y_r.$$
设当前处于平衡阶段，时间差为 \(r\)。刚刚被重新投入的那根木棍，它下一次完整循环的时间记为 \(T\)。这时只有三种情况。
如果 \(T<r\)，那么这根木棍会在 \(T\) 秒后先浮出。比赛还没有结束，但局面会转成“领先一轮阶段”，新的时间差是 \(r-T\)，所以后续期望为 \(Y_{r-T}\)。
如果 \(T=r\)，两根木棍会在 \(r\) 秒后同时浮出。系统回到平衡阶段，而具体差值需要重新平均，因此后续期望是 \(\bar X\)。
如果 \(T>r\)，则另一根木棍会先在 \(r\) 秒后浮出。比赛转入领先一轮阶段，新的时间差是 \(T-r\)，后续期望变成 \(Y_{T-r}\)。
因为 \(T\) 在 \(\{u,\dots,v\}\) 上均匀分布，所以得到
$$X_r=\frac{1}{q}\left(\sum_{t=u}^{\min(v,r-1)}\left(t+Y_{r-t}\right)+\mathbf{1}_{u\le r\le v}\left(r+\bar X\right)+\sum_{t=\max(u,r+1)}^{v}\left(r+Y_{t-r}\right)\right).$$
现在设当前已经处于“领先一轮阶段”，时间差仍为 \(r\)。同样把刚刚重新投入的领先木棍下一次完整循环时间记为 \(T\)。
如果 \(T<r\)，领先者会在另一根木棍完成当前通过之前再次浮出，比赛就在这一刻结束，所以增加的时间只是 \(T\)。
如果 \(T=r\)，两根木棍会在 \(r\) 秒后同时浮出。领先这一事实并没有消失，但具体差值重新由一次新的均匀抽样决定，因此后续期望是 \(\bar Y\)。
如果 \(T>r\)，落后者会先在 \(r\) 秒后浮出，从而把局面拉回平衡阶段。新的时间差是 \(T-r\)，后续期望于是变成 \(X_{T-r}\)。
因此有
$$Y_r=\frac{1}{q}\left(\sum_{t=u}^{\min(v,r-1)}t+\mathbf{1}_{u\le r\le v}\left(r+\bar Y\right)+\sum_{t=\max(u,r+1)}^{v}\left(r+X_{t-r}\right)\right).$$
开局时，两根木棍的第一次通过时间是独立的均匀随机变量 \(T_1,T_2\in\{n,\dots,m\}\)。
如果 \(T_1<T_2\)，第一根木棍在 \(T_1\) 秒后先浮出，随后比赛进入时间差为 \(T_2-T_1\) 的领先一轮阶段，因此贡献为 \(T_1+Y_{T_2-T_1}\)。
如果 \(T_2<T_1\)，则贡献为 \(T_2+Y_{T_1-T_2}\)。
如果 \(T_1=T_2\)，两根木棍同时浮出，系统进入平衡阶段的平均情形，因此贡献为 \(T_1+\bar X\)。
于是
$$E(m,n)=\frac{1}{q^2}\left(\sum_{n\le t_1<t_2\le m}\left(t_1+Y_{t_2-t_1}\right)+\sum_{n\le t_2<t_1\le m}\left(t_2+Y_{t_1-t_2}\right)+\sum_{t=n}^{m}\left(t+\bar X\right)\right).$$
这时后续循环时间只有 \(u=6\) 和 \(v=7\)，因此 \(q=2\)。两个平均量是
$$\bar X=\frac{X_6+X_7}{2},\qquad \bar Y=\frac{Y_6+Y_7}{2}.$$
先看时间差 \(r=1\) 的领先一轮阶段。因为下一轮时间只能是 6 或 7，领先者不可能立即再度浮出并直接获胜。经过 1 秒后，落后者必然先浮出，所以
$$Y_1=1+\frac{X_5+X_6}{2}.$$
再看时间差 \(r=6\) 的平衡阶段。如果新的循环时间是 6，两根木棍会同时浮出，后续就是 \(\bar X\)。如果新的循环时间是 7，那么另一根木棍会先在 6 秒后浮出，系统转到 \(Y_1\)。因此
$$X_6=6+\frac{\bar X+Y_1}{2}.$$
而在开局时，有序对 \((1,2)\) 与 \((2,1)\) 各自贡献 \(1+Y_1\)，平局 \((1,1)\) 与 \((2,2)\) 分别贡献 \(1+\bar X\) 和 \(2+\bar X\)。这个小例子清楚地说明：程序中的状态方程，正是比赛规则的直接数学翻译。
C++、Python 和 Java 三个实现对每个 \((n,m)\) 都求解同一个模型。对于每个可能的时间差 \(r\)，先预计算哪些循环时间小于 \(r\)、等于 \(r\)、大于 \(r\)，以及相应的个数和时间总和。这样，上面的第一步分析公式就会变成一个线性方程组，其未知量为
$$X_1,\dots,X_v,\qquad Y_1,\dots,Y_v,\qquad \bar X,\qquad \bar Y.$$
因此矩阵规模是
$$2v+2.$$
实现会根据这些转移区间直接填充系数矩阵，再用带部分主元选取的高斯消元解出所有状态值。随后，对所有开局有序对 \((T_1,T_2)\) 做平均，就得到 \(E(m,n)\)。最后再把所有 \(1\le n<m\le k\) 的结果累加，得到 \(S(k)\)。Python 版本把求解工作交给编译后的求解器，C++ 和 Java 则直接构造同一个线性代数模型；其中 C++ 版本还对外层求和做了并行化。
对固定的 \((n,m)\)，矩阵维度为 \(2v+2=2m+12\)。根据转移区间构造稠密矩阵需要 \(O(v^2)\) 时间，高斯消元需要 \(O(v^3)\) 时间，空间复杂度是 \(O(v^2)\)。最后对开局有序对求平均只需要 \(O((m-n+1)^2)\)，在实际参数范围内远小于线性系统求解的代价。
对 \(S(k)\) 的全部参数对求和后，总时间量级为
$$\sum_{m=2}^{k}\sum_{n=1}^{m-1}O((m+5)^3)=O(k^5),$$
而峰值内存由最大的单个线性系统决定，因此为 \(O(k^2)\)。
Две палочки бросают в реку. Время первого прохождения под мостом для каждой палочки равномерно выбирается среди целых чисел из \([n,m]\). Когда палочка появляется из-под моста, её поднимают и снова бросают через 5 секунд, поэтому все последующие циклы имеют равномерное распределение на \([n+5,m+5]\). Гонка заканчивается в тот момент, когда одна палочка появляется снова, пока другая ещё находится внутри своей предыдущей проходки; это и означает, что лидер оказался ровно на один полный проход впереди. Для каждой пары \((m,n)\) нужно вычислить математическое ожидание времени завершения \(E(m,n)\), а затем суммировать
$$S(k)=\sum_{m=2}^{k}\sum_{n=1}^{m-1}E(m,n).$$
Главное упрощение состоит в том, что после первого появления полная история больше не нужна: достаточно знать текущий временной разрыв и текущую фазу гонки.
Зафиксируем пару \((n,m)\) и введём обозначения
$$u=n+5,\qquad v=m+5,\qquad q=v-u+1=m-n+1.$$
После первого прохода каждый новый полный цикл является независимым равномерным выбором из \(\{u,u+1,\dots,v\}\).
В самом начале 5-секундной задержки на повторный бросок ещё нет, поэтому первый выбор делается из \(\{n,\dots,m\}\). После первого появления каждая следующая проходка уже содержит эту добавку, и потому рекурсивная часть работает с \(\{u,\dots,v\}\). Именно этим объясняется, почему реализация обрабатывает старт отдельно от основного рекуррентного механизма.
После первого появления нужны только два параметра: сколько секунд осталось до появления другой палочки и находится ли процесс в сбалансированной фазе или в фазе преимущества в один проход.
Для каждого целого разрыва \(r\in\{1,\dots,v\}\) определим две величины:
Пусть \(X_r\) обозначает ожидаемое оставшееся время в сбалансированной фазе при разрыве \(r\).
Пусть \(Y_r\) обозначает ожидаемое оставшееся время в фазе преимущества в один проход при разрыве \(r\).
Сбалансированная фаза означает, что следующее появление создаст преимущество в один проход, но ещё не завершит гонку. Фаза преимущества означает, что только что повторно брошенная ведущая палочка немедленно выигрывает, если успеет появиться снова раньше, чем отстающая завершит свой текущий проход.
Одновременное появление запускает новый цикл, и новый остаток времени равномерно распределён по \(\{u,\dots,v\}\). Поэтому дополнительно вводятся средние значения
$$\bar X=\frac{1}{q}\sum_{r=u}^{v}X_r,\qquad \bar Y=\frac{1}{q}\sum_{r=u}^{v}Y_r.$$
Пусть мы находимся в сбалансированной фазе с разрывом \(r\), а \(T\) обозначает длительность следующего полного цикла палочки, которую только что снова бросили. Возможны три случая.
Если \(T<r\), эта палочка появится первой через \(T\) секунд. Гонка ещё не закончится, но теперь возникнет преимущество в один проход, а новый разрыв станет равен \(r-T\). Следовательно, продолжение равно \(Y_{r-T}\).
Если \(T=r\), обе палочки появятся одновременно через \(r\) секунд. Процесс возвращается в сбалансированную фазу, и дальнейшее ожидание равно среднему \(\bar X\).
Если \(T>r\), другая палочка появится первой через \(r\) секунд. Процесс переходит в фазу преимущества с новым разрывом \(T-r\), так что продолжение равно \(Y_{T-r}\).
Поскольку \(T\) равномерно распределено на \(\{u,\dots,v\}\), получаем
$$X_r=\frac{1}{q}\left(\sum_{t=u}^{\min(v,r-1)}\left(t+Y_{r-t}\right)+\mathbf{1}_{u\le r\le v}\left(r+\bar X\right)+\sum_{t=\max(u,r+1)}^{v}\left(r+Y_{t-r}\right)\right).$$
Теперь рассмотрим фазу, где лидер уже опережает на один проход, а разрыв равен \(r\). Снова обозначим через \(T\) длительность следующего полного цикла только что повторно брошенной ведущей палочки.
Если \(T<r\), лидер появляется ещё раз до того, как вторая палочка завершит свой текущий проход. В этот момент гонка заканчивается, поэтому дополнительное время равно просто \(T\).
Если \(T=r\), обе палочки появляются одновременно через \(r\) секунд. Сам факт преимущества сохраняется, но конкретный разрыв снова заменяется свежим равномерным выбором, поэтому продолжение равно \(\bar Y\).
Если \(T>r\), отстающая палочка появляется первой через \(r\) секунд и тем самым возвращает процесс в сбалансированную фазу. Новый разрыв равен \(T-r\), значит продолжение равно \(X_{T-r}\).
Следовательно,
$$Y_r=\frac{1}{q}\left(\sum_{t=u}^{\min(v,r-1)}t+\mathbf{1}_{u\le r\le v}\left(r+\bar Y\right)+\sum_{t=\max(u,r+1)}^{v}\left(r+X_{t-r}\right)\right).$$
Начальные времена первых проходов двух палочек являются независимыми равномерными величинами \(T_1,T_2\in\{n,\dots,m\}\).
Если \(T_1<T_2\), первая палочка появляется через \(T_1\) секунд, после чего процесс входит в фазу преимущества с разрывом \(T_2-T_1\). Вклад равен \(T_1+Y_{T_2-T_1}\).
Если \(T_2<T_1\), вклад равен \(T_2+Y_{T_1-T_2}\).
Если \(T_1=T_2\), обе палочки появляются одновременно, и продолжение равно сбалансированному среднему \(\bar X\). Тогда вклад равен \(T_1+\bar X\).
Итак,
$$E(m,n)=\frac{1}{q^2}\left(\sum_{n\le t_1<t_2\le m}\left(t_1+Y_{t_2-t_1}\right)+\sum_{n\le t_2<t_1\le m}\left(t_2+Y_{t_1-t_2}\right)+\sum_{t=n}^{m}\left(t+\bar X\right)\right).$$
Здесь последующие циклы имеют длину только \(u=6\) или \(v=7\), поэтому \(q=2\). Средние состояния равны
$$\bar X=\frac{X_6+X_7}{2},\qquad \bar Y=\frac{Y_6+Y_7}{2}.$$
Рассмотрим фазу преимущества с разрывом \(r=1\). Поскольку следующий цикл может длиться только 6 или 7 секунд, лидер не может выиграть сразу. Через 1 секунду обязательно первой появится отстающая палочка, поэтому
$$Y_1=1+\frac{X_5+X_6}{2}.$$
Теперь рассмотрим сбалансированную фазу с разрывом \(r=6\). Если новый цикл равен 6, палочки появятся одновременно, и продолжение будет равно \(\bar X\). Если новый цикл равен 7, другая палочка появится первой через 6 секунд, и процесс перейдёт в \(Y_1\). Значит,
$$X_6=6+\frac{\bar X+Y_1}{2}.$$
На старте упорядоченные пары \((1,2)\) и \((2,1)\) дают вклад \(1+Y_1\), а ничьи \((1,1)\) и \((2,2)\) дают соответственно \(1+\bar X\) и \(2+\bar X\). Этот маленький пример наглядно показывает, как уравнения состояний точно кодируют правила гонки.
Реализации на C++, Python и Java решают одну пару \((n,m)\) за раз. Для каждого возможного разрыва \(r\) они заранее вычисляют, какие длины циклов меньше \(r\), какие равны \(r\), а какие больше \(r\), вместе с соответствующими количествами и суммами времени. Благодаря этому приведённые выше формулы первого шага превращаются в линейную систему с неизвестными
$$X_1,\dots,X_v,\qquad Y_1,\dots,Y_v,\qquad \bar X,\qquad \bar Y.$$
Размер этой системы равен
$$2v+2.$$
Далее реализация заполняет матрицу коэффициентов напрямую из интервалов переходов и решает её методом Гаусса с частичным выбором главного элемента. После этого выполняется усреднение по всем стартовым парам \((T_1,T_2)\), что даёт \(E(m,n)\). Затем эти ожидания суммируются по всем \(1\le n<m\le k\), образуя \(S(k)\). Версия на Python делегирует вычисление скомпилированному решателю, тогда как версии на C++ и Java напрямую строят ту же линейно-алгебраическую модель; версия на C++ дополнительно распараллеливает внешнюю сумму.
Для фиксированной пары \((n,m)\) размер матрицы равен \(2v+2=2m+12\). Построение плотной матрицы по переходным интервалам требует \(O(v^2)\) времени, метод Гаусса требует \(O(v^3)\) времени, а память составляет \(O(v^2)\). Финальное усреднение по стартовым парам стоит только \(O((m-n+1)^2)\), так что для реальных параметров оно меньше стоимости решения линейной системы.
Если суммировать по всем парам для \(S(k)\), получаем
$$\sum_{m=2}^{k}\sum_{n=1}^{m-1}O((m+5)^3)=O(k^5),$$
а пиковая память определяется наибольшей отдельной системой и потому имеет порядок \(O(k^2)\).
نرمي عودين في النهر. زمن المرور الأول تحت الجسر لكل عود يُختار بالتساوي من الأعداد الصحيحة في الفترة \([n,m]\). وعندما يظهر العود من جديد، يُلتقط ثم يُعاد إسقاطه بعد 5 ثوانٍ، ولذلك تصبح كل دورة لاحقة موزعة بانتظام على \([n+5,m+5]\). تنتهي المسابقة عندما يظهر أحد العودين مرة أخرى بينما يكون العود الآخر ما زال داخل مروره السابق، وعندها يكون المتقدم قد صار متقدماً بمقدار دورة كاملة بالضبط. لكل زوج \((m,n)\) نريد الزمن المتوقع للنهاية \(E(m,n)\)، ثم نحسب
$$S(k)=\sum_{m=2}^{k}\sum_{n=1}^{m-1}E(m,n).$$
الفكرة الأساسية هي أن التاريخ الكامل بعد أول ظهور لم يعد مهماً؛ يكفي أن نعرف الفارق الزمني الحالي والمرحلة الحالية من السباق.
لنثبت زوجاً واحداً \((n,m)\)، ونكتب
$$u=n+5,\qquad v=m+5,\qquad q=v-u+1=m-n+1.$$
بعد المرور الأول تصبح كل مدة دورة جديدة سحباً مستقلاً ومتساوي الاحتمال من المجموعة \(\{u,u+1,\dots,v\}\).
المرور الأول لا يتضمن بعدُ تأخير إعادة الإسقاط البالغ 5 ثوانٍ، ولذلك يكون السحب الأول من \(\{n,\dots,m\}\). بعد أول ظهور، كل دورة لاحقة تتضمن هذا التأخير، ولهذا فإن الجزء التكراري من الحل يعمل على \(\{u,\dots,v\}\). وهذا يفسر لماذا تعالج الشفرة البداية بطريقة مستقلة عن بقية العملية.
بعد أول ظهور، لا نحتاج إلا إلى معلومتين: كم ثانية بقيت حتى يظهر العود الآخر، وهل نحن في مرحلة متوازنة أم في مرحلة يوجد فيها تقدم بمقدار دورة واحدة.
لكل فرق صحيح \(r\in\{1,\dots,v\}\)، نعرّف توقعين:
ليكن \(X_r\) هو الزمن المتبقي المتوقع في المرحلة المتوازنة عند فرق \(r\).
وليكن \(Y_r\) هو الزمن المتبقي المتوقع في مرحلة التقدم بدورة واحدة عند فرق \(r\).
المرحلة المتوازنة تعني أن الظهور التالي سيخلق تقدماً بمقدار دورة واحدة، لكنه لن ينهي السباق فوراً. أما مرحلة التقدم فتَعني أن العود الذي أُعيد إسقاطه لتوّه سيفوز مباشرة إذا ظهر مرة أخرى قبل أن يُتم العود الآخر مروره الحالي.
إذا ظهر العودان معاً، فإن العملية تبدأ من جديد بزمن متبقٍ جديد موزع بانتظام على \(\{u,\dots,v\}\). لذلك نحتاج أيضاً إلى المتوسطين
$$\bar X=\frac{1}{q}\sum_{r=u}^{v}X_r,\qquad \bar Y=\frac{1}{q}\sum_{r=u}^{v}Y_r.$$
افترض أننا في المرحلة المتوازنة مع فرق زمني \(r\)، ولتكن \(T\) مدة الدورة الكاملة التالية للعود الذي أُعيد إسقاطه لتوّه. توجد ثلاث حالات.
إذا كان \(T<r\)، فإن هذا العود يظهر أولاً بعد \(T\) ثانية. لا ينتهي السباق بعد، لكن الحالة تصبح حالة تقدم بدورة واحدة، ويصبح الفرق الجديد \(r-T\)، لذا يكون الاستمرار هو \(Y_{r-T}\).
إذا كان \(T=r\)، فإن العودين يظهران معاً بعد \(r\) ثانية. تعود العملية إلى المرحلة المتوازنة، ويصبح الاستمرار هو المتوسط \(\bar X\).
إذا كان \(T>r\)، فإن العود الآخر هو الذي يظهر أولاً بعد \(r\) ثانية. ينتقل السباق إلى مرحلة التقدم مع فرق جديد \(T-r\)، ولذلك يكون الاستمرار هو \(Y_{T-r}\).
وبما أن \(T\) موزع بانتظام على \(\{u,\dots,v\}\)، نحصل على
$$X_r=\frac{1}{q}\left(\sum_{t=u}^{\min(v,r-1)}\left(t+Y_{r-t}\right)+\mathbf{1}_{u\le r\le v}\left(r+\bar X\right)+\sum_{t=\max(u,r+1)}^{v}\left(r+Y_{t-r}\right)\right).$$
الآن افترض أننا في مرحلة يكون فيها أحد العودين متقدماً بدورة واحدة والفرق الزمني هو \(r\). ولتكن \(T\) مرة أخرى مدة الدورة الكاملة التالية للعود المتقدم الذي أُعيد إسقاطه لتوّه.
إذا كان \(T<r\)، فإن العود المتقدم يظهر مرة أخرى قبل أن يكمل العود الآخر مروره الحالي. عند هذه اللحظة ينتهي السباق، ولذلك يكون الزمن الإضافي ببساطة هو \(T\).
إذا كان \(T=r\)، فإن العودين يظهران معاً بعد \(r\) ثانية. تبقى حقيقة وجود التقدم كما هي، لكن الفرق نفسه يُعاد ضبطه بسحب منتظم جديد، ولذا يكون الاستمرار هو \(\bar Y\).
إذا كان \(T>r\)، فإن العود المتأخر يظهر أولاً بعد \(r\) ثانية، وبهذا تعود العملية إلى المرحلة المتوازنة. الفرق الجديد هو \(T-r\)، ومن ثم يكون الاستمرار هو \(X_{T-r}\).
إذن
$$Y_r=\frac{1}{q}\left(\sum_{t=u}^{\min(v,r-1)}t+\mathbf{1}_{u\le r\le v}\left(r+\bar Y\right)+\sum_{t=\max(u,r+1)}^{v}\left(r+X_{t-r}\right)\right).$$
في البداية، زمن المرور الأول لكل من العودين هو متغير عشوائي مستقل \(T_1,T_2\in\{n,\dots,m\}\).
إذا كان \(T_1<T_2\)، فإن العود الأول يظهر بعد \(T_1\) ثانية، وتدخل العملية مرحلة التقدم بدورة واحدة مع فرق \(T_2-T_1\). وعندئذٍ تكون المساهمة \(T_1+Y_{T_2-T_1}\).
إذا كان \(T_2<T_1\)، فالمساهمة هي \(T_2+Y_{T_1-T_2}\).
أما إذا كان \(T_1=T_2\)، فإن العودين يظهران معاً، ويكون الاستمرار هو المتوسط المتوازن \(\bar X\)، وبالتالي تكون المساهمة \(T_1+\bar X\).
ومن ثم
$$E(m,n)=\frac{1}{q^2}\left(\sum_{n\le t_1<t_2\le m}\left(t_1+Y_{t_2-t_1}\right)+\sum_{n\le t_2<t_1\le m}\left(t_2+Y_{t_1-t_2}\right)+\sum_{t=n}^{m}\left(t+\bar X\right)\right).$$
في هذه الحالة تكون الأزمنة اللاحقة الممكنة للدورة هي فقط \(u=6\) و\(v=7\)، ولذلك \(q=2\). أما المتوسطان فهما
$$\bar X=\frac{X_6+X_7}{2},\qquad \bar Y=\frac{Y_6+Y_7}{2}.$$
لننظر أولاً إلى مرحلة التقدم مع فرق \(r=1\). بما أن زمن الدورة التالية لا يمكن إلا أن يكون 6 أو 7، فلا يستطيع المتقدم أن يفوز فوراً. بعد ثانية واحدة سيظهر العود المتأخر بالضرورة أولاً، ومن ثم
$$Y_1=1+\frac{X_5+X_6}{2}.$$
والآن خذ المرحلة المتوازنة مع فرق \(r=6\). إذا كانت مدة الدورة الجديدة 6، فإن العودين يظهران معاً ويكون الاستمرار \(\bar X\). وإذا كانت 7، فإن العود الآخر يظهر أولاً بعد 6 ثوانٍ وتنتقل العملية إلى \(Y_1\). لذا
$$X_6=6+\frac{\bar X+Y_1}{2}.$$
في البداية، الزوجان المرتبان \((1,2)\) و\((2,1)\) يضيفان كلاً منهما \(1+Y_1\)، بينما حالتا التعادل \((1,1)\) و\((2,2)\) تضيفان \(1+\bar X\) و\(2+\bar X\) على الترتيب. هذا المثال الصغير يوضح بدقة كيف تتحول قواعد السباق إلى معادلات حالة قابلة للحل.
تنفذ تطبيقات C++ وPython وJava النموذج نفسه لكل زوج \((n,m)\). ولكل فرق محتمل \(r\)، تُحسب مسبقاً الأزمنة التي تكون أصغر من \(r\) أو مساوية له أو أكبر منه، مع أعدادها ومجاميعها الزمنية. وهكذا تتحول معادلات الخطوة الأولى السابقة إلى نظام خطي مجهولاته هي
$$X_1,\dots,X_v,\qquad Y_1,\dots,Y_v,\qquad \bar X,\qquad \bar Y.$$
ومن ثم يكون حجم النظام
$$2v+2.$$
تملأ الشفرة مصفوفة المعاملات مباشرة من فترات الانتقال هذه، ثم تحلها بحذف غاوسي مع اختيار محوري جزئي. بعد ذلك تؤخذ المتوسطات على جميع الأزواج الافتتاحية \((T_1,T_2)\) للحصول على \(E(m,n)\)، ثم تُجمع هذه القيم على جميع الأزواج \(1\le n<m\le k\) للحصول على \(S(k)\). نسخة Python تفوض العمل إلى محلل مترجم، بينما تبني نسختا C++ وJava النموذج الخطي نفسه بصورة مباشرة؛ كما أن نسخة C++ توازي المجموع الخارجي أيضاً.
بالنسبة إلى زوج ثابت \((n,m)\)، يكون بعد المصفوفة هو \(2v+2=2m+12\). بناء المصفوفة الكثيفة من فترات الانتقال يكلف \(O(v^2)\) زمناً، والحذف الغاوسي يكلف \(O(v^3)\) زمناً، أما الذاكرة فهي \(O(v^2)\). المتوسط النهائي على الأزواج الافتتاحية يحتاج فقط إلى \(O((m-n+1)^2)\)، ولذلك يبقى أصغر من كلفة حل النظام في المجال المطلوب.
وعند الجمع على جميع الأزواج من أجل \(S(k)\)، نحصل على
$$\sum_{m=2}^{k}\sum_{n=1}^{m-1}O((m+5)^3)=O(k^5),$$
بينما تتحدد الذاكرة العظمى بأكبر نظام منفرد، أي أنها من رتبة \(O(k^2)\).