There are \(n\) boats in front-to-back order, initially separated by \(40\) metres. Boat \(j\) rows at a constant random speed
$$v_j=-\log X_j,\qquad X_j\sim U(0,1),$$
with the \(X_j\) independent. A boat stops as soon as it bumps the boat directly ahead or reaches the finish line. Each bump is an adjacent swap, so the race ends with a final permutation \(\pi\) of the starting order. The goal is to compute the probability that this final permutation is even. For the actual problem we need the case \(n=13\) and \(L=1800\).
The implementations do not track even and odd outcomes separately. Instead, they work with the expected sign of the final permutation, because the sign of a concatenation of independent permutation blocks multiplies cleanly.
Because every starting gap equals \(40\), we divide all distances by \(40\) and set
$$m=\frac{L}{40}.$$
So the target instance becomes \((n,m)=(13,45)\).
If the boats are indexed from front to back, then boat \(k\) has
$$r_k=m-k+1$$
scaled units of unobstructed water available before its first decisive event. Summing these distances gives
$$R(n,m)=\sum_{k=1}^{n} r_k = nm-\frac{n(n-1)}{2}.$$
Let \(\operatorname{sgn}(\pi)=+1\) for an even permutation and \(-1\) for an odd permutation. Define
$$\Sigma(n,m)=\mathbb{E}[\operatorname{sgn}(\pi)].$$
Then
$$\Sigma(n,m)=P_{\mathrm{even}}(n,m)-P_{\mathrm{odd}}(n,m)=2p(n,m)-1,$$
so the required probability is recovered by
$$p(n,m)=\frac{1+\Sigma(n,m)}{2}.$$
This single quantity is exactly what the dynamic program stores.
Boat \(k\) needs to cover distance \(r_k\) before its first decisive event occurs, so its associated time scale is
$$T_k=\frac{r_k}{v_k}=-\frac{r_k}{\log X_k}.$$
Now define the transformed variable
$$Y_k=X_k^{1/r_k}=e^{-v_k/r_k}.$$
The map between \(T_k\) and \(Y_k\) is monotone decreasing, so the first decisive event is determined by the largest \(Y_k\).
For \(0\le y\le 1\),
$$\Pr(Y_k\le y)=\Pr(X_k\le y^{r_k})=y^{r_k},$$
hence \(Y_k\) has density \(r_k y^{r_k-1}\). Therefore
$$\Pr\!\bigl(Y_k=\max(Y_1,\dots,Y_n)\bigr)=\int_0^1 r_k y^{r_k-1}\prod_{j\ne k} y^{r_j}\,dy=\frac{r_k}{R(n,m)}.$$
So the first decisive event chooses index \(k\) with weight
$$\frac{m-k+1}{nm-\frac{n(n-1)}{2}}.$$
Condition on the first decisive event being attached to boat \(k\). Then the leading block of \(k\) boats becomes a closed Torpids subrace on the critical course \(k-1\): once that first event is fixed, there is no spare scaled water left inside that block. The boats behind it never interact with that resolved block again.
After deleting the resolved leading block, the remaining boats form a fresh instance of the same process with \(n-k\) boats and course parameter \(m-k\).
Because permutation signs multiply under concatenation, the conditional contribution to the expected sign is
$$\Sigma(k,k-1)\,\Sigma(n-k,m-k).$$
Averaging over all possible values of \(k\) yields the main recurrence, valid for \(m\ge n\):
$$\Sigma(n,m)=\sum_{k=1}^{n}\frac{m-k+1}{nm-\frac{n(n-1)}{2}}\;\Sigma(k,k-1)\,\Sigma(n-k,m-k).$$
The trivial base cases are
$$\Sigma(0,m)=\Sigma(1,m)=1,$$
because with zero or one boat the final permutation is always even.
At the critical boundary \(m=n-1\), the newly added last boat contributes a fixed parity factor of \((-1)^{n-1}\), while the remaining uncertainty is exactly the \((n-1,n-1)\) instance. Thus
$$\Sigma(n,n-1)=(-1)^{n-1}\Sigma(n-1,n-1).$$
These formulas completely determine every state needed by the dynamic program.
Here \(m=160/40=4\). Start with the small boundary values
$$\Sigma(1,0)=1,\qquad \Sigma(2,1)=-1.$$
For \((n,m)=(2,2)\), the recurrence gives
$$\Sigma(2,2)=\frac{2}{3}\Sigma(1,0)\Sigma(1,1)+\frac{1}{3}\Sigma(2,1)\Sigma(0,0)=\frac{2}{3}-\frac{1}{3}=\frac{1}{3}.$$
Therefore the critical value for three boats is
$$\Sigma(3,2)=(-1)^2\Sigma(2,2)=\frac{1}{3}.$$
Now apply the main recurrence at \((3,4)\). Since
$$R(3,4)=3\cdot 4-\frac{3\cdot 2}{2}=9,$$
the weights are \(4/9\), \(3/9\), and \(2/9\). Also \(\Sigma(2,3)=1/5\). Hence
$$\Sigma(3,4)=\frac{4}{9}\cdot 1\cdot \frac{1}{5}+\frac{3}{9}\cdot (-1)\cdot 1+\frac{2}{9}\cdot \frac{1}{3}\cdot 1=\frac{4}{45}-\frac{1}{3}+\frac{2}{27}=-\frac{23}{135}.$$
So the even-permutation probability is
$$p(3,4)=\frac{1+\Sigma(3,4)}{2}=\frac{1-23/135}{2}=\frac{56}{135}.$$
This is the exact small checkpoint reproduced by the implementations.
The C++, Python, and Java implementations build a two-dimensional table of expected signs for every state up to \((13,45)\). They first fill the trivial rows for \(0\) and \(1\) boat, then assign the boundary values at \(m=n-1\), and finally sweep all larger \(m\) bottom-up with the recurrence above.
Every entry only depends on states that have already been computed, so the iteration order is straightforward and stable. After the table is complete, the implementation converts the stored expected sign into the desired probability with
$$p=\frac{1+\Sigma}{2}.$$
The arithmetic is done in high-precision decimal form so that repeated weighted sums do not introduce visible rounding drift before the final answer is rounded to \(10\) decimal places. The same table also reproduces the exact smaller values \(56/135\) for \((3,4)\) and \(521/1020\) for \((4,10)\).
Let \(m=L/40\). The table contains \(O(nm)\) states. Each nontrivial state performs a sum over \(k=1,\dots,n\), so the total running time is
$$O(n^2m).$$
The memory usage is dominated by the table itself, which stores one high-precision number per state:
$$O(nm).$$
For the target instance \((13,45)\), both bounds are very small.
Es gibt \(n\) Boote in Vorder-nach-Hinten-Reihenfolge, anfangs jeweils \(40\) Meter voneinander entfernt. Boot \(j\) rudert mit konstanter Zufallsgeschwindigkeit
$$v_j=-\log X_j,\qquad X_j\sim U(0,1),$$
wobei die \(X_j\) unabhängig sind. Ein Boot stoppt, sobald es das direkt davorliegende Boot bumpt oder die Ziellinie erreicht. Jeder Bump ist eine benachbarte Vertauschung, daher entsteht am Ende eine Permutation \(\pi\) der Startreihenfolge. Gesucht ist die Wahrscheinlichkeit, dass diese Endpermutation gerade ist. Im eigentlichen Problem gilt \(n=13\) und \(L=1800\).
Die Implementierungen verfolgen gerade und ungerade Endlagen nicht getrennt. Stattdessen verwenden sie den Erwartungswert des Permutationsvorzeichens, weil sich das Vorzeichen bei einer Zerlegung in unabhängige Blöcke multiplikativ verhält.
Da jeder Startabstand gleich \(40\) ist, teilen wir alle Distanzen durch \(40\) und setzen
$$m=\frac{L}{40}.$$
Damit wird aus dem Zielproblem die Instanz \((n,m)=(13,45)\).
Nummeriert man die Boote von vorne nach hinten, dann besitzt Boot \(k\)
$$r_k=m-k+1$$
skalierte Einheiten freien Wassers, bevor sein erster entscheidender Moment eintreten kann. Die Summe dieser Distanzen ist
$$R(n,m)=\sum_{k=1}^{n} r_k = nm-\frac{n(n-1)}{2}.$$
Sei \(\operatorname{sgn}(\pi)=+1\) für eine gerade Permutation und \(-1\) für eine ungerade. Definiere
$$\Sigma(n,m)=\mathbb{E}[\operatorname{sgn}(\pi)].$$
Dann gilt
$$\Sigma(n,m)=P_{\mathrm{gerade}}(n,m)-P_{\mathrm{ungerade}}(n,m)=2p(n,m)-1,$$
und damit erhält man die gesuchte Wahrscheinlichkeit zurück durch
$$p(n,m)=\frac{1+\Sigma(n,m)}{2}.$$
Genau diese eine Größe speichert das dynamische Programm.
Boot \(k\) muss die Distanz \(r_k\) überbrücken, bevor sein erster entscheidender Moment eintritt. Daher gehört zu ihm die Zeitskala
$$T_k=\frac{r_k}{v_k}=-\frac{r_k}{\log X_k}.$$
Nun definieren wir die transformierte Zufallsvariable
$$Y_k=X_k^{1/r_k}=e^{-v_k/r_k}.$$
Die Zuordnung zwischen \(T_k\) und \(Y_k\) ist streng monoton fallend, also wird das erste entscheidende Ereignis durch das größte \(Y_k\) bestimmt.
Für \(0\le y\le 1\) gilt
$$\Pr(Y_k\le y)=\Pr(X_k\le y^{r_k})=y^{r_k},$$
also hat \(Y_k\) die Dichte \(r_k y^{r_k-1}\). Daraus folgt
$$\Pr\!\bigl(Y_k=\max(Y_1,\dots,Y_n)\bigr)=\int_0^1 r_k y^{r_k-1}\prod_{j\ne k} y^{r_j}\,dy=\frac{r_k}{R(n,m)}.$$
Das erste entscheidende Ereignis wählt also den Index \(k\) mit Gewicht
$$\frac{m-k+1}{nm-\frac{n(n-1)}{2}}.$$
Konditionieren wir darauf, dass das erste entscheidende Ereignis zu Boot \(k\) gehört. Dann bilden die vorderen \(k\) Boote ein abgeschlossenes Torpids-Teilrennen auf der kritischen Streckenlänge \(k-1\): Innerhalb dieses Blocks bleibt nach Fixierung des ersten Ereignisses kein zusätzlicher skalierter Freiraum mehr übrig. Die dahinterliegenden Boote interagieren danach nicht mehr mit diesem aufgelösten Block.
Entfernt man den aufgelösten Führungsblock, so bilden die restlichen Boote eine frische Instanz desselben Prozesses mit \(n-k\) Booten und Streckenparameter \(m-k\).
Da sich Permutationsvorzeichen bei einer Konkatenation multiplizieren, ist der bedingte Beitrag zum Erwartungswert des Vorzeichens
$$\Sigma(k,k-1)\,\Sigma(n-k,m-k).$$
Durch Mittelung über alle möglichen Werte von \(k\) erhält man für \(m\ge n\) die Hauptrekursion
$$\Sigma(n,m)=\sum_{k=1}^{n}\frac{m-k+1}{nm-\frac{n(n-1)}{2}}\;\Sigma(k,k-1)\,\Sigma(n-k,m-k).$$
Die trivialen Basisfälle sind
$$\Sigma(0,m)=\Sigma(1,m)=1,$$
denn mit null oder einem Boot ist die Endpermutation immer gerade.
Am kritischen Rand \(m=n-1\) liefert das neu hinzugefügte letzte Boot einen festen Paritätsfaktor \((-1)^{n-1}\), während die verbleibende Unsicherheit genau der Instanz \((n-1,n-1)\) entspricht. Also
$$\Sigma(n,n-1)=(-1)^{n-1}\Sigma(n-1,n-1).$$
Damit sind alle Zustände vollständig bestimmt, die das dynamische Programm benötigt.
Hier ist \(m=160/40=4\). Zunächst gelten die kleinen Randwerte
$$\Sigma(1,0)=1,\qquad \Sigma(2,1)=-1.$$
Für \((n,m)=(2,2)\) liefert die Rekursion
$$\Sigma(2,2)=\frac{2}{3}\Sigma(1,0)\Sigma(1,1)+\frac{1}{3}\Sigma(2,1)\Sigma(0,0)=\frac{2}{3}-\frac{1}{3}=\frac{1}{3}.$$
Daher ist der kritische Wert für drei Boote
$$\Sigma(3,2)=(-1)^2\Sigma(2,2)=\frac{1}{3}.$$
Nun wenden wir die Hauptrekursion auf \((3,4)\) an. Weil
$$R(3,4)=3\cdot 4-\frac{3\cdot 2}{2}=9,$$
sind die Gewichte \(4/9\), \(3/9\) und \(2/9\). Außerdem ist \(\Sigma(2,3)=1/5\). Also
$$\Sigma(3,4)=\frac{4}{9}\cdot 1\cdot \frac{1}{5}+\frac{3}{9}\cdot (-1)\cdot 1+\frac{2}{9}\cdot \frac{1}{3}\cdot 1=\frac{4}{45}-\frac{1}{3}+\frac{2}{27}=-\frac{23}{135}.$$
Damit ergibt sich für die Wahrscheinlichkeit einer geraden Endpermutation
$$p(3,4)=\frac{1+\Sigma(3,4)}{2}=\frac{1-23/135}{2}=\frac{56}{135}.$$
Genau dieser exakte Kontrollwert wird von den Implementierungen reproduziert.
Die C++-, Python- und Java-Implementierungen bauen eine zweidimensionale Tabelle der erwarteten Vorzeichen für alle Zustände bis \((13,45)\) auf. Zuerst werden die trivialen Zeilen für \(0\) und \(1\) Boot gefüllt, dann die Randwerte bei \(m=n-1\) gesetzt und schließlich alle größeren \(m\) mit der obigen Rekursion bottom-up berechnet.
Jeder Tabelleneintrag hängt nur von bereits bekannten Zuständen ab, daher ist die Auswertungsreihenfolge direkt und stabil. Nach dem Tabellenaufbau wird das gespeicherte erwartete Vorzeichen mittels
$$p=\frac{1+\Sigma}{2}$$
in die gesuchte Wahrscheinlichkeit umgerechnet. Die Rechnung erfolgt mit hochpräziser Dezimalarithmetik, damit die vielen gewichteten Summen vor der Endrundung auf \(10\) Nachkommastellen keinen sichtbaren Drift erzeugen. Dieselbe Tabelle reproduziert auch die exakten kleineren Werte \(56/135\) für \((3,4)\) und \(521/1020\) für \((4,10)\).
Mit \(m=L/40\) enthält die Tabelle \(O(nm)\) Zustände. Jeder nichttriviale Zustand summiert über \(k=1,\dots,n\), also beträgt die gesamte Laufzeit
$$O(n^2m).$$
Der Speicherbedarf wird von der Tabelle dominiert, die pro Zustand genau einen hochpräzisen Wert speichert:
$$O(nm).$$
Für die Zielinstanz \((13,45)\) sind beide Schranken sehr klein.
\(n\) tekne önden arkaya doğru sıralanmış halde başlar ve aralarındaki mesafe \(40\) metredir. \(j\). teknenin sabit rastgele hızı
$$v_j=-\log X_j,\qquad X_j\sim U(0,1),$$
şeklindedir ve \(X_j\) değişkenleri birbirinden bağımsızdır. Bir tekne ya hemen önündeki tekneye çarptığında ya da finişe ulaştığında durur. Her bump komşu iki teknenin yer değiştirmesi olduğundan yarış sonunda başlangıç sırasının bir permütasyonu \(\pi\) elde edilir. Amaç, bu son permütasyonun çift olma olasılığını bulmaktır. Asıl problemde \(n=13\) ve \(L=1800\) alınır.
Uygulamalar çift ve tek sonuçları ayrı ayrı saymak yerine son permütasyonun işaretinin beklenen değerini kullanır. Bunun nedeni, bağımsız bloklara ayrılan bir yarışta permütasyon işaretlerinin çarpımsal olarak birleşmesidir.
Tüm başlangıç aralıkları \(40\) olduğu için bütün mesafeleri \(40\)'a böler ve
$$m=\frac{L}{40}$$
tanımını yaparız. Böylece hedef durum \((n,m)=(13,45)\) olur.
Tekneleri önden arkaya doğru numaralarsak, \(k\). teknenin ilk belirleyici olayına kadar önünde kalan serbest su miktarı
$$r_k=m-k+1$$
ölçeklenmiş birimdir. Bu değerlerin toplamı
$$R(n,m)=\sum_{k=1}^{n} r_k = nm-\frac{n(n-1)}{2}$$
şeklindedir.
\(\operatorname{sgn}(\pi)\) çift permütasyon için \(+1\), tek permütasyon için \(-1\) olsun. Şimdi
$$\Sigma(n,m)=\mathbb{E}[\operatorname{sgn}(\pi)]$$
tanımını yapalım. O zaman
$$\Sigma(n,m)=P_{\mathrm{cift}}(n,m)-P_{\mathrm{tek}}(n,m)=2p(n,m)-1,$$
ve aradığımız olasılık
$$p(n,m)=\frac{1+\Sigma(n,m)}{2}$$
olur. Dinamik program tam olarak bu tek büyüklüğü saklar.
\(k\). teknenin ilk belirleyici olayına kadar kat etmesi gereken mesafe \(r_k\) olduğundan ona karşılık gelen zaman ölçeği
$$T_k=\frac{r_k}{v_k}=-\frac{r_k}{\log X_k}$$
olur. Şimdi
$$Y_k=X_k^{1/r_k}=e^{-v_k/r_k}$$
dönüşümünü tanımlayalım. \(T_k\) küçüldükçe \(Y_k\) büyür; dolayısıyla ilk belirleyici olay en büyük \(Y_k\) tarafından belirlenir.
\(0\le y\le 1\) için
$$\Pr(Y_k\le y)=\Pr(X_k\le y^{r_k})=y^{r_k}$$
olduğundan \(Y_k\)'nın yoğunluğu \(r_k y^{r_k-1}\) olur. Böylece
$$\Pr\!\bigl(Y_k=\max(Y_1,\dots,Y_n)\bigr)=\int_0^1 r_k y^{r_k-1}\prod_{j\ne k} y^{r_j}\,dy=\frac{r_k}{R(n,m)}$$
elde edilir. Yani ilk belirleyici olayın \(k\) indeksini seçme ağırlığı
$$\frac{m-k+1}{nm-\frac{n(n-1)}{2}}$$
olur.
İlk belirleyici olayın \(k\). tekneye ait olduğu duruma koşullanalım. O zaman öndeki \(k\) tekne, kritik uzunluğu \(k-1\) olan kapalı bir Torpids alt yarışı oluşturur; çünkü bu ilk olay sabitlendiğinde bu blok içinde artık fazladan ölçeklenmiş mesafe kalmaz. Arkadaki tekneler de çözülmüş bu blokla tekrar etkileşime girmez.
Bu öndeki blok kaldırıldığında geriye aynı kuralların geçerli olduğu, \(n-k\) tekneli ve yarış parametresi \(m-k\) olan yeni bir durum kalır.
Permütasyon işareti blokların birleşiminde çarpıldığı için koşullu katkı
$$\Sigma(k,k-1)\,\Sigma(n-k,m-k)$$
şeklindedir.
Tüm \(k\) değerleri üzerinden ortalama alındığında, \(m\ge n\) için ana bağıntı elde edilir:
$$\Sigma(n,m)=\sum_{k=1}^{n}\frac{m-k+1}{nm-\frac{n(n-1)}{2}}\;\Sigma(k,k-1)\,\Sigma(n-k,m-k).$$
Temel durumlar
$$\Sigma(0,m)=\Sigma(1,m)=1$$
çünkü sıfır ya da bir teknede son permütasyon her zaman çifttir.
Kritik sınır \(m=n-1\) olduğunda, en arkadan eklenen tekne sabit bir \((-1)^{n-1}\) parite katsayısı getirir ve geri kalan belirsizlik tam olarak \((n-1,n-1)\) durumuna eşittir. Bu yüzden
$$\Sigma(n,n-1)=(-1)^{n-1}\Sigma(n-1,n-1).$$
Dinamik programın ihtiyaç duyduğu bütün durumlar bu formüllerle belirlenir.
Burada \(m=160/40=4\) olur. Önce küçük sınır değerleri yazalım:
$$\Sigma(1,0)=1,\qquad \Sigma(2,1)=-1.$$
\((2,2)\) durumu için bağıntı
$$\Sigma(2,2)=\frac{2}{3}\Sigma(1,0)\Sigma(1,1)+\frac{1}{3}\Sigma(2,1)\Sigma(0,0)=\frac{2}{3}-\frac{1}{3}=\frac{1}{3}$$
sonucunu verir. Böylece üç teknenin kritik değeri
$$\Sigma(3,2)=(-1)^2\Sigma(2,2)=\frac{1}{3}$$
olur.
Şimdi \((3,4)\) durumunda ana bağıntıyı uygulayalım. Çünkü
$$R(3,4)=3\cdot 4-\frac{3\cdot 2}{2}=9,$$
ağırlıklar \(4/9\), \(3/9\) ve \(2/9\) olur. Ayrıca \(\Sigma(2,3)=1/5\) tir. Dolayısıyla
$$\Sigma(3,4)=\frac{4}{9}\cdot 1\cdot \frac{1}{5}+\frac{3}{9}\cdot (-1)\cdot 1+\frac{2}{9}\cdot \frac{1}{3}\cdot 1=\frac{4}{45}-\frac{1}{3}+\frac{2}{27}=-\frac{23}{135}.$$
Bundan çift permütasyon olasılığı
$$p(3,4)=\frac{1+\Sigma(3,4)}{2}=\frac{1-23/135}{2}=\frac{56}{135}$$
olarak çıkar. Bu, uygulamaların yeniden ürettiği kesin küçük kontrol değeridir.
C++, Python ve Java uygulamaları \((13,45)\) durumuna kadar tüm beklenen işaret değerlerini içeren iki boyutlu bir tablo kurar. Önce \(0\) ve \(1\) tekne için trivial satırlar doldurulur, sonra \(m=n-1\) sınır değerleri yerleştirilir, ardından daha büyük tüm \(m\) değerleri yukarıdaki bağıntıyla alttan üste hesaplanır.
Her tablo hücresi yalnızca daha önce hesaplanmış hücrelere bağlı olduğundan dolaşım sırası doğaldır ve kararlıdır. Tablo tamamlandığında saklanan beklenen işaret,
$$p=\frac{1+\Sigma}{2}$$
formülüyle aranan olasılığa çevrilir. Hesap, sonucun \(10\) ondalık basamağa yuvarlanmasından önce biriken ağırlıklı toplamların hassasiyet kaybetmemesi için yüksek duyarlıklı ondalık aritmetikle yapılır. Aynı tablo ayrıca \((3,4)\) için \(56/135\) ve \((4,10)\) için \(521/1020\) değerlerini de tam olarak verir.
\(m=L/40\) olmak üzere tabloda \(O(nm)\) adet durum vardır. Her trivial olmayan durum \(k=1,\dots,n\) üzerinde toplama yaptığından toplam süre
$$O(n^2m)$$
olur. Bellek gereksinimi ise durum başına bir yüksek duyarlıklı sayı saklayan tablodan gelir:
$$O(nm).$$
Hedef örnek \((13,45)\) için bu maliyetler oldukça küçüktür.
Hay \(n\) botes colocados de delante hacia atrás, separados inicialmente por \(40\) metros. El bote \(j\) rema con velocidad aleatoria constante
$$v_j=-\log X_j,\qquad X_j\sim U(0,1),$$
con las variables \(X_j\) independientes. Un bote se detiene en cuanto alcanza al bote inmediatamente anterior o llega a la meta. Cada bump es un intercambio adyacente, así que al final aparece una permutación \(\pi\) del orden inicial. Se pide la probabilidad de que esa permutación final sea par. En el caso real del problema, \(n=13\) y \(L=1800\).
Las implementaciones no almacenan por separado las probabilidades de obtener una permutación par o impar. En su lugar trabajan con el valor esperado del signo de la permutación final, porque el signo de una concatenación de bloques independientes se multiplica de forma natural.
Como todas las separaciones iniciales valen \(40\), dividimos todas las distancias entre \(40\) y definimos
$$m=\frac{L}{40}.$$
Así, la instancia objetivo pasa a ser \((n,m)=(13,45)\).
Si numeramos los botes de delante hacia atrás, el bote \(k\) dispone de
$$r_k=m-k+1$$
unidades escaladas de agua libre antes de su primer evento decisivo. La suma total es
$$R(n,m)=\sum_{k=1}^{n} r_k = nm-\frac{n(n-1)}{2}.$$
Sea \(\operatorname{sgn}(\pi)=+1\) para una permutación par y \(-1\) para una impar. Definimos
$$\Sigma(n,m)=\mathbb{E}[\operatorname{sgn}(\pi)].$$
Entonces
$$\Sigma(n,m)=P_{\mathrm{par}}(n,m)-P_{\mathrm{impar}}(n,m)=2p(n,m)-1,$$
y la probabilidad buscada se recupera con
$$p(n,m)=\frac{1+\Sigma(n,m)}{2}.$$
Ese único valor es el que almacena el programa dinámico.
El bote \(k\) debe cubrir la distancia \(r_k\) antes de que ocurra su primer evento decisivo, de modo que la escala temporal asociada es
$$T_k=\frac{r_k}{v_k}=-\frac{r_k}{\log X_k}.$$
Ahora definimos la variable transformada
$$Y_k=X_k^{1/r_k}=e^{-v_k/r_k}.$$
La relación entre \(T_k\) y \(Y_k\) es monótona decreciente, así que el primer evento decisivo queda determinado por el mayor \(Y_k\).
Para \(0\le y\le 1\),
$$\Pr(Y_k\le y)=\Pr(X_k\le y^{r_k})=y^{r_k},$$
por lo que \(Y_k\) tiene densidad \(r_k y^{r_k-1}\). En consecuencia,
$$\Pr\!\bigl(Y_k=\max(Y_1,\dots,Y_n)\bigr)=\int_0^1 r_k y^{r_k-1}\prod_{j\ne k} y^{r_j}\,dy=\frac{r_k}{R(n,m)}.$$
Por tanto, el primer evento decisivo elige el índice \(k\) con peso
$$\frac{m-k+1}{nm-\frac{n(n-1)}{2}}.$$
Condicionemos a que el primer evento decisivo pertenezca al bote \(k\). Entonces el bloque delantero de \(k\) botes se convierte en una subcarrera cerrada con longitud crítica \(k-1\): una vez fijado ese primer evento ya no queda agua escalada sobrante dentro de ese bloque. Los botes que van detrás no vuelven a interactuar con ese bloque ya resuelto.
Si eliminamos el bloque delantero resuelto, los botes restantes forman una nueva instancia del mismo proceso con \(n-k\) botes y parámetro de pista \(m-k\).
Como los signos de las permutaciones se multiplican al concatenar bloques, la contribución condicional al signo esperado es
$$\Sigma(k,k-1)\,\Sigma(n-k,m-k).$$
Promediando sobre todos los valores posibles de \(k\), para \(m\ge n\) obtenemos la recurrencia principal
$$\Sigma(n,m)=\sum_{k=1}^{n}\frac{m-k+1}{nm-\frac{n(n-1)}{2}}\;\Sigma(k,k-1)\,\Sigma(n-k,m-k).$$
Los casos base triviales son
$$\Sigma(0,m)=\Sigma(1,m)=1,$$
porque con cero o un bote la permutación final siempre es par.
En la frontera crítica \(m=n-1\), el nuevo bote del fondo aporta un factor fijo de paridad \((-1)^{n-1}\), mientras que la incertidumbre restante coincide exactamente con la instancia \((n-1,n-1)\). Por ello
$$\Sigma(n,n-1)=(-1)^{n-1}\Sigma(n-1,n-1).$$
Estas fórmulas determinan por completo todos los estados necesarios para el programa dinámico.
Aquí \(m=160/40=4\). Empezamos con los valores pequeños de frontera
$$\Sigma(1,0)=1,\qquad \Sigma(2,1)=-1.$$
Para \((n,m)=(2,2)\), la recurrencia da
$$\Sigma(2,2)=\frac{2}{3}\Sigma(1,0)\Sigma(1,1)+\frac{1}{3}\Sigma(2,1)\Sigma(0,0)=\frac{2}{3}-\frac{1}{3}=\frac{1}{3}.$$
Entonces el valor crítico para tres botes es
$$\Sigma(3,2)=(-1)^2\Sigma(2,2)=\frac{1}{3}.$$
Ahora aplicamos la recurrencia principal en \((3,4)\). Como
$$R(3,4)=3\cdot 4-\frac{3\cdot 2}{2}=9,$$
los pesos son \(4/9\), \(3/9\) y \(2/9\). Además, \(\Sigma(2,3)=1/5\). Por tanto,
$$\Sigma(3,4)=\frac{4}{9}\cdot 1\cdot \frac{1}{5}+\frac{3}{9}\cdot (-1)\cdot 1+\frac{2}{9}\cdot \frac{1}{3}\cdot 1=\frac{4}{45}-\frac{1}{3}+\frac{2}{27}=-\frac{23}{135}.$$
La probabilidad de una permutación final par es entonces
$$p(3,4)=\frac{1+\Sigma(3,4)}{2}=\frac{1-23/135}{2}=\frac{56}{135}.$$
Ese es el valor exacto pequeño que reproducen las implementaciones.
Las implementaciones en C++, Python y Java construyen una tabla bidimensional con los signos esperados para todos los estados hasta \((13,45)\). Primero rellenan las filas triviales de \(0\) y \(1\) bote, después guardan los valores de frontera en \(m=n-1\), y finalmente recorren todos los \(m\) mayores aplicando la recurrencia de abajo hacia arriba.
Cada celda solo depende de celdas ya calculadas, así que el orden de evaluación es directo y estable. Cuando la tabla está completa, la implementación transforma el signo esperado almacenado en la probabilidad pedida mediante
$$p=\frac{1+\Sigma}{2}.$$
La aritmética se realiza con decimales de alta precisión para que las sumas ponderadas repetidas no introduzcan un error visible antes del redondeo final a \(10\) decimales. La misma tabla reproduce además los valores exactos \(56/135\) para \((3,4)\) y \(521/1020\) para \((4,10)\).
Con \(m=L/40\), la tabla contiene \(O(nm)\) estados. Cada estado no trivial evalúa una suma sobre \(k=1,\dots,n\), de modo que el tiempo total es
$$O(n^2m).$$
La memoria está dominada por la propia tabla, que guarda un número de alta precisión por estado:
$$O(nm).$$
Para la instancia objetivo \((13,45)\), ambos costes son muy pequeños.
共有 \(n\) 条船，按从前到后的顺序出发，初始间距都是 \(40\) 米。第 \(j\) 条船以常数随机速度前进：
$$v_j=-\log X_j,\qquad X_j\sim U(0,1),$$
其中各个 \(X_j\) 相互独立。一条船一旦撞上前面紧邻的船，或者自己到达终点，就立刻停止。每一次 bump 都对应一次相邻交换，因此整场比赛结束后，起始顺序会变成某个最终排列 \(\pi\)。题目要求的是这个最终排列为偶排列的概率。实际目标参数是 \(n=13\)、\(L=1800\)。
实现并不是分别维护“最终为偶排列的概率”和“最终为奇排列的概率”。更高效的做法是直接维护最终排列符号的期望值，因为当比赛被拆成两个互不影响的区块时，排列符号会自然地按乘法组合。
由于每个起始间隔都等于 \(40\) 米，把所有距离同时除以 \(40\)，记
$$m=\frac{L}{40}.$$
这样原题就转化成 \((n,m)=(13,45)\)。
如果把船按“从前到后”编号，那么第 \(k\) 条船在遇到自己的第一个决定性事件之前，前方还剩下的自由水域长度是
$$r_k=m-k+1.$$
这些长度加总得到
$$R(n,m)=\sum_{k=1}^{n} r_k = nm-\frac{n(n-1)}{2}.$$
后面的递推权重正是从这个总量里长出来的。
令 \(\operatorname{sgn}(\pi)=+1\) 表示 \(\pi\) 是偶排列，\(\operatorname{sgn}(\pi)=-1\) 表示 \(\pi\) 是奇排列。定义
$$\Sigma(n,m)=\mathbb{E}[\operatorname{sgn}(\pi)].$$
于是有
$$\Sigma(n,m)=P_{\mathrm{even}}(n,m)-P_{\mathrm{odd}}(n,m)=2p(n,m)-1,$$
因此最后要求的偶排列概率可以由
$$p(n,m)=\frac{1+\Sigma(n,m)}{2}$$
直接恢复出来。这样整张动态规划表只需要存一个量，而不必同时存两类概率。
第 \(k\) 条船在发生自己的第一个决定性事件之前，需要先走完 \(r_k\) 这一段有效距离，所以对应的时间尺度是
$$T_k=\frac{r_k}{v_k}=-\frac{r_k}{\log X_k}.$$
接着做一个关键变换：
$$Y_k=X_k^{1/r_k}=e^{-v_k/r_k}.$$
\(T_k\) 越小，\(Y_k\) 就越大，所以“谁先触发决定性事件”与“谁的 \(Y_k\) 最大”是完全等价的。
对任意 \(0\le y\le 1\)，
$$\Pr(Y_k\le y)=\Pr(X_k\le y^{r_k})=y^{r_k},$$
因此 \(Y_k\) 的密度函数是 \(r_k y^{r_k-1}\)。由此可以直接计算出
$$\Pr\!\bigl(Y_k=\max(Y_1,\dots,Y_n)\bigr)=\int_0^1 r_k y^{r_k-1}\prod_{j\ne k} y^{r_j}\,dy=\frac{r_k}{R(n,m)}.$$
这说明第一个决定性事件落在第 \(k\) 条船上的权重恰好是
$$\frac{m-k+1}{nm-\frac{n(n-1)}{2}}.$$
现在条件化到“第一个决定性事件属于第 \(k\) 条船”。在这个条件下，最前面的 \(k\) 条船会形成一个封闭的小型 Torpids 子问题，而且它对应的临界赛道长度正好是 \(k-1\)。直观地说，一旦第一个决定性事件被固定，这个前导区块内部就不再有多余的缩放距离可以让外部船只继续介入。
把这个已经解决的前导区块删除之后，剩余的船只又构成一个同类型的新问题，其参数变成 \(n-k\) 条船、赛道参数 \(m-k\)。
由于两个区块最终排列的符号会相乘，所以在这个条件下，对期望符号的贡献就是
$$\Sigma(k,k-1)\,\Sigma(n-k,m-k).$$
把所有可能的 \(k\) 按上述权重平均，就得到对 \(m\ge n\) 成立的主递推式：
$$\Sigma(n,m)=\sum_{k=1}^{n}\frac{m-k+1}{nm-\frac{n(n-1)}{2}}\;\Sigma(k,k-1)\,\Sigma(n-k,m-k).$$
最基本的边界条件是
$$\Sigma(0,m)=\Sigma(1,m)=1,$$
因为没有船或者只有一条船时，最终排列必然是偶排列。
另一个关键边界出现在临界长度 \(m=n-1\)。这时最后新增的那条船会贡献一个固定的奇偶因子 \((-1)^{n-1}\)，而其余不确定性正好退化成 \((n-1,n-1)\) 这个更小问题，所以
$$\Sigma(n,n-1)=(-1)^{n-1}\Sigma(n-1,n-1).$$
有了这些式子，动态规划需要的全部状态就被完全确定了。
这里 \(m=160/40=4\)。先写出最小边界值：
$$\Sigma(1,0)=1,\qquad \Sigma(2,1)=-1.$$
对于 \((n,m)=(2,2)\)，递推给出
$$\Sigma(2,2)=\frac{2}{3}\Sigma(1,0)\Sigma(1,1)+\frac{1}{3}\Sigma(2,1)\Sigma(0,0)=\frac{2}{3}-\frac{1}{3}=\frac{1}{3}.$$
因此三条船的临界值为
$$\Sigma(3,2)=(-1)^2\Sigma(2,2)=\frac{1}{3}.$$
接下来计算 \((3,4)\)。因为
$$R(3,4)=3\cdot 4-\frac{3\cdot 2}{2}=9,$$
所以三个权重依次是 \(4/9\)、\(3/9\)、\(2/9\)。同时 \(\Sigma(2,3)=1/5\)。代回主递推式可得
$$\Sigma(3,4)=\frac{4}{9}\cdot 1\cdot \frac{1}{5}+\frac{3}{9}\cdot (-1)\cdot 1+\frac{2}{9}\cdot \frac{1}{3}\cdot 1=\frac{4}{45}-\frac{1}{3}+\frac{2}{27}=-\frac{23}{135}.$$
于是偶排列概率为
$$p(3,4)=\frac{1+\Sigma(3,4)}{2}=\frac{1-23/135}{2}=\frac{56}{135}.$$
这正是实现中用来核对的小规模精确结果之一。
C++、Python 和 Java 三份实现都会构造一张二维表，保存从小状态一直到 \((13,45)\) 的所有期望符号值。做法是先填好 \(0\) 条船和 \(1\) 条船这两行，再写入 \(m=n-1\) 的临界边界，最后按自底向上的顺序计算更大的 \(m\)。
每个表项只依赖已经算好的更小状态，因此迭代顺序非常直接。整张表完成后，再用
$$p=\frac{1+\Sigma}{2}$$
把存下来的期望符号转换成最终所需的偶排列概率。为了避免反复做加权求和时出现可见的舍入漂移，实现使用了高精度十进制数值，最后才把答案四舍五入到 \(10\) 位小数。同一张表还会重现 \((3,4)\) 的 \(56/135\) 与 \((4,10)\) 的 \(521/1020\) 这两个精确校验值。
令 \(m=L/40\)。动态规划表一共有 \(O(nm)\) 个状态。每个非平凡状态都要对 \(k=1,\dots,n\) 做一次求和，因此总时间复杂度是
$$O(n^2m).$$
空间复杂度由整张表主导，每个状态保存一个高精度数：
$$O(nm).$$
对目标参数 \((13,45)\) 来说，这个代价很小。
Есть \(n\) лодок, выстроенных от передней к задней, с начальными промежутками по \(40\) метров. Лодка \(j\) движется с постоянной случайной скоростью
$$v_j=-\log X_j,\qquad X_j\sim U(0,1),$$
причём все \(X_j\) независимы. Лодка останавливается либо в момент bump с ближайшей лодкой впереди, либо при достижении финиша. Каждый bump соответствует соседней транспозиции, поэтому в конце получается некоторая перестановка \(\pi\) стартового порядка. Требуется найти вероятность того, что эта конечная перестановка чётна. В реальной задаче нужно вычислить случай \(n=13\) и \(L=1800\).
Реализации не хранят отдельно вероятности чётного и нечётного исходов. Вместо этого они используют математическое ожидание знака конечной перестановки, потому что знак при склейке независимых блоков умножается, и рекурсия становится заметно чище.
Так как все начальные интервалы равны \(40\), разделим все расстояния на \(40\) и введём
$$m=\frac{L}{40}.$$
Тогда целевой случай превращается в \((n,m)=(13,45)\).
Если нумеровать лодки спереди назад, то у лодки \(k\) есть
$$r_k=m-k+1$$
масштабированных единиц свободной воды до её первого решающего события. Сумма этих расстояний равна
$$R(n,m)=\sum_{k=1}^{n} r_k = nm-\frac{n(n-1)}{2}.$$
Пусть \(\operatorname{sgn}(\pi)=+1\) для чётной перестановки и \(-1\) для нечётной. Определим
$$\Sigma(n,m)=\mathbb{E}[\operatorname{sgn}(\pi)].$$
Тогда
$$\Sigma(n,m)=P_{\mathrm{even}}(n,m)-P_{\mathrm{odd}}(n,m)=2p(n,m)-1,$$
поэтому искомая вероятность выражается как
$$p(n,m)=\frac{1+\Sigma(n,m)}{2}.$$
Именно это одно число и хранится в таблице динамики.
Лодке \(k\) нужно пройти расстояние \(r_k\), прежде чем произойдёт её первое решающее событие, значит соответствующий масштаб времени равен
$$T_k=\frac{r_k}{v_k}=-\frac{r_k}{\log X_k}.$$
Теперь введём преобразованную величину
$$Y_k=X_k^{1/r_k}=e^{-v_k/r_k}.$$
Связь между \(T_k\) и \(Y_k\) строго монотонна: чем меньше \(T_k\), тем больше \(Y_k\). Следовательно, первое решающее событие определяется максимальным \(Y_k\).
Для \(0\le y\le 1\) имеем
$$\Pr(Y_k\le y)=\Pr(X_k\le y^{r_k})=y^{r_k},$$
значит плотность \(Y_k\) равна \(r_k y^{r_k-1}\). Отсюда получаем
$$\Pr\!\bigl(Y_k=\max(Y_1,\dots,Y_n)\bigr)=\int_0^1 r_k y^{r_k-1}\prod_{j\ne k} y^{r_j}\,dy=\frac{r_k}{R(n,m)}.$$
Итак, первое решающее событие выбирает индекс \(k\) с весом
$$\frac{m-k+1}{nm-\frac{n(n-1)}{2}}.$$
Зафиксируем случай, когда первое решающее событие связано с лодкой \(k\). Тогда передний блок из \(k\) лодок образует замкнутую подгонку Torpids на критической длине трассы \(k-1\): после фиксации первого события внутри этого блока уже не остаётся лишней масштабированной дистанции. Лодки позади больше не взаимодействуют с этим уже разрешённым блоком.
Если удалить передний блок, то оставшиеся лодки снова дают ту же самую задачу, но уже с \(n-k\) лодками и параметром трассы \(m-k\).
Поскольку знак перестановки при конкатенации блоков перемножается, условный вклад в ожидаемый знак равен
$$\Sigma(k,k-1)\,\Sigma(n-k,m-k).$$
Усредняя по всем возможным \(k\), для \(m\ge n\) получаем основную рекурсию
$$\Sigma(n,m)=\sum_{k=1}^{n}\frac{m-k+1}{nm-\frac{n(n-1)}{2}}\;\Sigma(k,k-1)\,\Sigma(n-k,m-k).$$
Тривиальные базовые случаи таковы:
$$\Sigma(0,m)=\Sigma(1,m)=1,$$
потому что при нуле или одной лодке конечная перестановка всегда чётна.
На критической границе \(m=n-1\) новая последняя лодка добавляет фиксированный множитель чётности \((-1)^{n-1}\), а вся оставшаяся неопределённость совпадает с экземпляром \((n-1,n-1)\). Поэтому
$$\Sigma(n,n-1)=(-1)^{n-1}\Sigma(n-1,n-1).$$
Этих формул достаточно, чтобы определить все состояния, необходимые динамическому алгоритму.
Здесь \(m=160/40=4\). Сначала выпишем малые граничные значения:
$$\Sigma(1,0)=1,\qquad \Sigma(2,1)=-1.$$
Для \((n,m)=(2,2)\) рекурсия даёт
$$\Sigma(2,2)=\frac{2}{3}\Sigma(1,0)\Sigma(1,1)+\frac{1}{3}\Sigma(2,1)\Sigma(0,0)=\frac{2}{3}-\frac{1}{3}=\frac{1}{3}.$$
Следовательно, критическое значение для трёх лодок равно
$$\Sigma(3,2)=(-1)^2\Sigma(2,2)=\frac{1}{3}.$$
Теперь применим основную рекурсию к \((3,4)\). Поскольку
$$R(3,4)=3\cdot 4-\frac{3\cdot 2}{2}=9,$$
веса равны \(4/9\), \(3/9\) и \(2/9\). Кроме того, \(\Sigma(2,3)=1/5\). Поэтому
$$\Sigma(3,4)=\frac{4}{9}\cdot 1\cdot \frac{1}{5}+\frac{3}{9}\cdot (-1)\cdot 1+\frac{2}{9}\cdot \frac{1}{3}\cdot 1=\frac{4}{45}-\frac{1}{3}+\frac{2}{27}=-\frac{23}{135}.$$
Отсюда вероятность чётной конечной перестановки равна
$$p(3,4)=\frac{1+\Sigma(3,4)}{2}=\frac{1-23/135}{2}=\frac{56}{135}.$$
Именно это точное малое значение воспроизводят реализации.
Реализации на C++, Python и Java строят двумерную таблицу ожидаемых знаков для всех состояний вплоть до \((13,45)\). Сначала заполняются тривиальные строки для \(0\) и \(1\) лодки, затем выставляются граничные значения при \(m=n-1\), после чего все большие \(m\) вычисляются снизу вверх по приведённой рекурсии.
Каждая ячейка зависит только от уже посчитанных состояний, поэтому порядок обхода прост и устойчив. Когда таблица построена, сохранённый ожидаемый знак преобразуется в искомую вероятность по формуле
$$p=\frac{1+\Sigma}{2}.$$
Вычисления ведутся в десятичной арифметике высокой точности, чтобы многократные взвешенные суммы не давали заметного накопления ошибки до финального округления к \(10\) знакам после запятой. Та же таблица воспроизводит и точные меньшие значения \(56/135\) для \((3,4)\) и \(521/1020\) для \((4,10)\).
Пусть \(m=L/40\). Таблица содержит \(O(nm)\) состояний. Для каждого нетривиального состояния вычисляется сумма по \(k=1,\dots,n\), поэтому общее время работы равно
$$O(n^2m).$$
Память определяется самой таблицей, в которой хранится по одному числу высокой точности на состояние:
$$O(nm).$$
Для целевого случая \((13,45)\) эти оценки очень малы.
لدينا \(n\) قوارب مرتبة من الأمام إلى الخلف، وبين كل قارب والذي يليه \(40\) مترًا. سرعة القارب رقم \(j\) ثابتة وعشوائية وتساوي
$$v_j=-\log X_j,\qquad X_j\sim U(0,1),$$
مع استقلال جميع المتغيرات \(X_j\). يتوقف القارب عندما يصطدم بالقارب الذي أمامه مباشرة أو عندما يصل إلى خط النهاية. وكل bump يمثّل تبديلًا متجاورًا، لذلك ينتهي السباق بترتيب نهائي \(\pi\) هو تبديل للترتيب الابتدائي. المطلوب هو احتمال أن يكون هذا التبديل النهائي زوجيًا. في المسألة الفعلية نحتاج إلى الحالة \(n=13\) و\(L=1800\).
التنفيذات لا تحتفظ باحتمال التبديل الزوجي واحتمال التبديل الفردي كلٌّ على حدة. بدلًا من ذلك تستخدم القيمة المتوقعة لإشارة التبديل النهائي، لأن إشارة تبديل ناتج عن دمج كتل مستقلة تتصرف بصورة ضربـية تجعل العلاقة التكرارية أنظف بكثير.
بما أن كل مسافة ابتدائية تساوي \(40\)، نقسم جميع المسافات على \(40\) ونعرّف
$$m=\frac{L}{40}.$$
وبذلك تتحول الحالة المطلوبة إلى \((n,m)=(13,45)\).
إذا رقّمنا القوارب من الأمام إلى الخلف، فإن القارب \(k\) يملك أمامه مقدارًا من الماء الحر يساوي
$$r_k=m-k+1$$
بوحدات القياس الجديدة قبل أن يقع أول حدث حاسم يتعلق به. ومجموع هذه المسافات هو
$$R(n,m)=\sum_{k=1}^{n} r_k = nm-\frac{n(n-1)}{2}.$$
لنعرّف \(\operatorname{sgn}(\pi)=+1\) إذا كان التبديل زوجيًا و\(-1\) إذا كان فرديًا، ثم نضع
$$\Sigma(n,m)=\mathbb{E}[\operatorname{sgn}(\pi)].$$
عندئذ
$$\Sigma(n,m)=P_{\mathrm{even}}(n,m)-P_{\mathrm{odd}}(n,m)=2p(n,m)-1,$$
ومن ثم يمكن استرجاع الاحتمال المطلوب من خلال
$$p(n,m)=\frac{1+\Sigma(n,m)}{2}.$$
وهذه هي الكمية الوحيدة التي يخزنها الجدول الديناميكي.
القارب \(k\) يحتاج إلى قطع مسافة مقدارها \(r_k\) قبل أن يقع أول حدث حاسم يخصه، ولذلك يكون مقياس الزمن الموافق له هو
$$T_k=\frac{r_k}{v_k}=-\frac{r_k}{\log X_k}.$$
ثم نعرّف المتغير المحوّل
$$Y_k=X_k^{1/r_k}=e^{-v_k/r_k}.$$
العلاقة بين \(T_k\) و\(Y_k\) رتيبة تناقصية، لذلك فإن أول حدث حاسم يتحدد بالقيمة العظمى بين \(Y_1,\dots,Y_n\).
ولكل \(0\le y\le 1\) لدينا
$$\Pr(Y_k\le y)=\Pr(X_k\le y^{r_k})=y^{r_k},$$
ولذلك تكون كثافة \(Y_k\) مساوية لـ \(r_k y^{r_k-1}\). ومن هنا نحصل على
$$\Pr\!\bigl(Y_k=\max(Y_1,\dots,Y_n)\bigr)=\int_0^1 r_k y^{r_k-1}\prod_{j\ne k} y^{r_j}\,dy=\frac{r_k}{R(n,m)}.$$
أي أن أول حدث حاسم يختار الفهرس \(k\) بوزن
$$\frac{m-k+1}{nm-\frac{n(n-1)}{2}}.$$
لنشترط الآن أن أول حدث حاسم يعود إلى القارب \(k\). عندها تتحول الكتلة الأمامية المكونة من \(k\) قوارب إلى مسألة فرعية مغلقة من النوع نفسه على طول حرج مقداره \(k-1\)، لأن تثبيت هذا الحدث الأول يستهلك كل المسافة المقيّسة الزائدة داخل تلك الكتلة. أما القوارب التي خلفها فلن تعود لتتفاعل مع هذه الكتلة بعد حلها.
وعند حذف الكتلة الأمامية المحسومة، يتبقى لدينا مثال جديد من العملية نفسها بعدد قوارب يساوي \(n-k\) ومعامل مسار يساوي \(m-k\).
وبما أن إشارة التبديل تتضاعف عند وصل الكتل، فإن المساهمة الشرطية في الإشارة المتوقعة تساوي
$$\Sigma(k,k-1)\,\Sigma(n-k,m-k).$$
بأخذ المتوسط على جميع قيم \(k\) الممكنة نحصل، عندما \(m\ge n\)، على العلاقة الأساسية
$$\Sigma(n,m)=\sum_{k=1}^{n}\frac{m-k+1}{nm-\frac{n(n-1)}{2}}\;\Sigma(k,k-1)\,\Sigma(n-k,m-k).$$
أما الحالات الابتدائية البسيطة فهي
$$\Sigma(0,m)=\Sigma(1,m)=1,$$
لأن التبديل النهائي يكون زوجيًا دائمًا عند عدم وجود قوارب أو عند وجود قارب واحد فقط.
وعلى الحد الحرج \(m=n-1\)، يضيف القارب الأخير الجديد عامل زوجية ثابتًا مقداره \((-1)^{n-1}\)، بينما تصبح بقية اللايقين مطابقة تمامًا للحالة \((n-1,n-1)\). لذلك
$$\Sigma(n,n-1)=(-1)^{n-1}\Sigma(n-1,n-1).$$
بهذه الصيغ تتحدد كل الحالات التي يحتاجها الجدول الديناميكي تحديدًا كاملًا.
هنا يكون \(m=160/40=4\). نبدأ بالقيم الحدّية الصغيرة:
$$\Sigma(1,0)=1,\qquad \Sigma(2,1)=-1.$$
وبالنسبة إلى الحالة \((2,2)\) تعطي العلاقة التكرارية
$$\Sigma(2,2)=\frac{2}{3}\Sigma(1,0)\Sigma(1,1)+\frac{1}{3}\Sigma(2,1)\Sigma(0,0)=\frac{2}{3}-\frac{1}{3}=\frac{1}{3}.$$
إذًا تصبح القيمة الحرجة لثلاثة قوارب
$$\Sigma(3,2)=(-1)^2\Sigma(2,2)=\frac{1}{3}.$$
والآن نطبّق العلاقة الرئيسية على \((3,4)\). بما أن
$$R(3,4)=3\cdot 4-\frac{3\cdot 2}{2}=9,$$
فإن الأوزان هي \(4/9\) و\(3/9\) و\(2/9\). كذلك لدينا \(\Sigma(2,3)=1/5\). ومن ثم
$$\Sigma(3,4)=\frac{4}{9}\cdot 1\cdot \frac{1}{5}+\frac{3}{9}\cdot (-1)\cdot 1+\frac{2}{9}\cdot \frac{1}{3}\cdot 1=\frac{4}{45}-\frac{1}{3}+\frac{2}{27}=-\frac{23}{135}.$$
فيترتب على ذلك أن احتمال الحصول على تبديل زوجي هو
$$p(3,4)=\frac{1+\Sigma(3,4)}{2}=\frac{1-23/135}{2}=\frac{56}{135}.$$
وهذه إحدى القيم الصغيرة الدقيقة التي تعيدها التنفيذات كما هي.
التنفيذات في C++ وPython وJava تبني جدولًا ثنائي الأبعاد يحفظ قيم الإشارة المتوقعة لكل الحالات حتى \((13,45)\). تبدأ أولًا بملء الصفين الخاصين بحالتي صفر قارب وقارب واحد، ثم تضيف القيم الحدّية عند \(m=n-1\)، وبعد ذلك تمر على القيم الأكبر من \(m\) تصاعديًا باستعمال العلاقة التكرارية السابقة.
كل خانة تعتمد فقط على خانات سبق حسابها، ولذلك يكون ترتيب الحساب مباشرًا ومستقرًا. وبعد اكتمال الجدول، تحوّل التنفيذات الإشارة المتوقعة المخزنة إلى الاحتمال المطلوب بواسطة
$$p=\frac{1+\Sigma}{2}.$$
ويُستخدم حساب عشري عالي الدقة حتى لا تنتج عن المجاميع الموزونة المتكررة انحرافات تقريبية ملحوظة قبل التقريب النهائي إلى \(10\) منازل عشرية. كما يعيد الجدول نفسه القيمتين الدقيقتين \(56/135\) للحالة \((3,4)\) و\(521/1020\) للحالة \((4,10)\).
إذا كان \(m=L/40\)، فإن الجدول يحتوي على \(O(nm)\) حالة. وكل حالة غير بديهية تحتاج إلى جمع على \(k=1,\dots,n\)، لذا يكون زمن التنفيذ الكلي
$$O(n^2m).$$
أما الذاكرة فتهيمن عليها بنية الجدول نفسها، إذ يُخزَّن عدد عالي الدقة واحد لكل حالة:
$$O(nm).$$
وبالنسبة إلى الحالة المستهدفة \((13,45)\)، فهاتان الكلفتان صغيرتان جدًا.