Pete rolls nine 4-sided dice, so his total lies between \(9\) and \(36\). Colin rolls six 6-sided dice, so his total lies between \(6\) and \(36\). The task is to compute the exact probability that Pete's total is strictly larger than Colin's total.
A naive enumeration would reason about all \(4^9 \cdot 6^6\) joint outcomes separately. The key simplification is that the full roll sequence does not matter once its sum is known, so the problem can be compressed into two exact sum distributions and one final comparison of those distributions.
The natural state space is not the list of individual face results but the running sum after a given number of dice. That is exactly what the implementations count.
For \(n\) dice with \(s\) sides, let \(D_i(t)\) denote the number of ordered outcomes of the first \(i\) dice whose sum is \(t\). The base state is
$$D_0(0)=1,\qquad D_0(t)=0 \text{ for } t\neq 0.$$
After \(i\) dice, the only possible sums satisfy \(i \le t \le is\). Another invariant is
$$\sum_t D_i(t)=s^i,$$
because \(D_i\) counts all ordered outcomes of \(i\) independent \(s\)-sided dice.
For Problem 205, Pete's final table is
$$P(p)=D^{(4)}_9(p),\qquad 9\le p\le 36,$$
and Colin's final table is
$$C(c)=D^{(6)}_6(c),\qquad 6\le c\le 36.$$
If one more \(s\)-sided die is appended, each old sum \(u\) can move to \(u+1,u+2,\dots,u+s\). Therefore the next row satisfies
$$D_{i+1}(t)=\sum_{f=1}^{s} D_i(t-f),$$
with impossible indices interpreted as zero. This is the discrete-convolution recurrence implemented in all three languages.
The same statement can be written in generating-function form:
$$D_n(t)=[x^t]\,(x+x^2+\cdots+x^s)^n.$$
For example, with two 4-sided dice,
$$D_2(5)=D_1(4)+D_1(3)+D_1(2)+D_1(1)=4,$$
because the ordered pairs \((1,4),(2,3),(3,2),(4,1)\) all contribute to sum \(5\).
Once \(P\) and \(C\) are known, the original game becomes a comparison of totals. If Pete reaches \(p\) in \(P(p)\) ways and Colin reaches \(c\) in \(C(c)\) ways, then the joint event \((p,c)\) occurs in
$$P(p)\,C(c)$$
ways, because the two players roll independently.
The total number of joint outcomes is therefore
$$\Omega=\sum_{p=9}^{36}\sum_{c=6}^{36} P(p)C(c)=4^9\cdot 6^6.$$
Pete wins exactly when \(p>c\), so the winning count is
$$W=\sum_{p=9}^{36}\sum_{c=6}^{36} [p>c]\,P(p)C(c).$$
Hence the required probability is
$$\Pr(\text{Pete wins})=\frac{W}{\Omega}.$$
Ties are excluded automatically because the inequality is strict.
A small version of the same game is useful for sanity checking the recurrence and the final strict comparison. Suppose Pete rolls 1 d4 and Colin rolls 1 d6. Then
$$P(1)=P(2)=P(3)=P(4)=1,\qquad C(1)=C(2)=C(3)=C(4)=C(5)=C(6)=1.$$
There are \(4\cdot 6=24\) equally weighted joint outcomes. Pete wins for
$$ (2,1),\ (3,1),\ (3,2),\ (4,1),\ (4,2),\ (4,3), $$
so \(W=6\) and therefore
$$\Pr(\text{Pete wins})=\frac{6}{24}=\frac14.$$
This is exactly the same counting principle as the full \(9\) d\(4\) versus \(6\) d\(6\) problem, just on a much smaller state space.
The C++, Python, and Java implementations all keep an array indexed by possible sums. They start from the degenerate distribution concentrated at sum \(0\), then repeat one update per die: allocate a fresh array for the next stage, and for every current sum push its count to the entries obtained by adding face values \(1\) through \(s\).
Running that routine with \((9,4)\) produces Pete's exact count table, and running it with \((6,6)\) produces Colin's exact count table. Although the arrays are sized up to the maximum sum, only the mathematically valid interval carries nonzero values after each stage.
After both tables have been built, the implementation scans every attainable Pete total against every attainable Colin total. For each pair it multiplies the two counts, adds that product to the grand total, and adds it to the win counter only when Pete's total is larger. Only after all counts have been accumulated does the code divide wins by total to obtain the probability.
One implementation also contains a small checkpoint for the 1 d4 versus 1 d6 case, and one version allows the dice parameters to be changed from the command line. Those details are auxiliary; the core algorithm is the same in C++, Python, and Java.
For \(n\) dice with \(s\) sides, the distribution builder performs \(n\) stages, scans sums up to \(ns\), and for each reachable sum tries all \(s\) faces. This yields \(O(n\cdot ns\cdot s)=O(n^2s^2)\) time, or equivalently \(O(n\cdot s\cdot M)\) if \(M=ns\) denotes the largest possible sum. The memory usage is \(O(M)\) for the current and next arrays.
The final comparison phase costs \(O(S_P S_C)\), where \(S_P\) and \(S_C\) are the sizes of Pete's and Colin's sum ranges. In this problem those ranges are tiny: Pete only spans \(9\) through \(36\), and Colin only spans \(6\) through \(36\). That is why the exact method is fast even though the underlying sample space contains more than twelve billion joint outcomes.
Pete wirft neun 4-seitige Würfel und kann daher nur Summen zwischen \(9\) und \(36\) erreichen. Colin wirft sechs 6-seitige Würfel und erhält Summen zwischen \(6\) und \(36\). Gesucht ist die exakte Wahrscheinlichkeit, dass Petes Summe strikt größer ist als Colins Summe.
Eine naive Aufzählung würde alle \(4^9 \cdot 6^6\) gemeinsamen Würfelergebnisse getrennt betrachten. Der entscheidende Schritt besteht darin, nicht die vollständigen Wurfsequenzen zu speichern, sondern nur zu zählen, wie viele Sequenzen zu jeder möglichen Summe führen.
Der richtige Zustand ist also die laufende Summe nach einer bestimmten Anzahl von Würfeln. Genau diese Tabellen bauen die Implementierungen auf.
Für \(n\) Würfel mit \(s\) Seiten sei \(D_i(t)\) die Anzahl der geordneten Ergebnisse der ersten \(i\) Würfel mit Summe \(t\). Der Anfangszustand ist
$$D_0(0)=1,\qquad D_0(t)=0 \text{ für } t\neq 0.$$
Nach \(i\) Würfeln können nur Summen im Bereich \(i \le t \le is\) auftreten. Außerdem gilt die Invariante
$$\sum_t D_i(t)=s^i,$$
denn \(D_i\) zählt sämtliche geordneten Ergebnisse von \(i\) unabhängigen \(s\)-seitigen Würfeln.
Für Problem 205 ist Petes Endverteilung
$$P(p)=D^{(4)}_9(p),\qquad 9\le p\le 36,$$
und Colins Endverteilung ist
$$C(c)=D^{(6)}_6(c),\qquad 6\le c\le 36.$$
Fügt man einen weiteren \(s\)-seitigen Würfel hinzu, so kann jede alte Summe \(u\) in \(u+1,u+2,\dots,u+s\) übergehen. Deshalb gilt
$$D_{i+1}(t)=\sum_{f=1}^{s} D_i(t-f),$$
wobei unmögliche Indizes als Null interpretiert werden. Genau diese diskrete Faltung wird in allen drei Sprachen umgesetzt.
Äquivalent dazu kann man schreiben
$$D_n(t)=[x^t]\,(x+x^2+\cdots+x^s)^n.$$
Beispielsweise gilt für zwei 4-seitige Würfel
$$D_2(5)=D_1(4)+D_1(3)+D_1(2)+D_1(1)=4,$$
weil die geordneten Paare \((1,4),(2,3),(3,2),(4,1)\) alle die Summe \(5\) erzeugen.
Sobald \(P\) und \(C\) bekannt sind, ist das Würfelproblem auf ein Summenproblem reduziert. Erreicht Pete den Wert \(p\) auf \(P(p)\) Arten und Colin den Wert \(c\) auf \(C(c)\) Arten, dann tritt das gemeinsame Ereignis \((p,c)\) wegen der Unabhängigkeit in
$$P(p)\,C(c)$$
Fällen auf.
Damit ist die Gesamtzahl aller gemeinsamen Ergebnisse
$$\Omega=\sum_{p=9}^{36}\sum_{c=6}^{36} P(p)C(c)=4^9\cdot 6^6.$$
Pete gewinnt genau dann, wenn \(p>c\). Also ist die Zahl der Gewinnfälle
$$W=\sum_{p=9}^{36}\sum_{c=6}^{36} [p>c]\,P(p)C(c).$$
Die gesuchte Wahrscheinlichkeit lautet folglich
$$\Pr(\text{Pete gewinnt})=\frac{W}{\Omega}.$$
Unentschieden zählen nicht mit, weil die Aufgabe ausdrücklich einen strikten Sieg verlangt.
Eine kleine Version desselben Spiels eignet sich hervorragend als Kontrolle der Rekurrenz und der Schlussbedingung \(p>c\). Wenn Pete 1 d4 und Colin 1 d6 wirft, dann gilt
$$P(1)=P(2)=P(3)=P(4)=1,\qquad C(1)=C(2)=C(3)=C(4)=C(5)=C(6)=1.$$
Es gibt also \(4\cdot 6=24\) gleich gewichtete gemeinsame Ergebnisse. Pete gewinnt bei
$$ (2,1),\ (3,1),\ (3,2),\ (4,1),\ (4,2),\ (4,3), $$
also \(W=6\), und damit
$$\Pr(\text{Pete gewinnt})=\frac{6}{24}=\frac14.$$
Genau dieselbe Zähllogik wird im eigentlichen \(9\) d\(4\)-gegen-\(6\) d\(6\)-Problem auf größere Tabellen angewandt.
Die C++-, Python- und Java-Implementierungen verwenden alle ein Array, dessen Index eine mögliche Summe darstellt. Sie beginnen mit der entarteten Verteilung bei Summe \(0\) und führen dann für jeden Würfel denselben Schritt aus: Ein neues Array für die nächste Stufe anlegen und jede aktuelle Anzahl auf die Positionen verschieben, die durch Addition der Augenzahlen \(1\) bis \(s\) entstehen.
Mit den Parametern \((9,4)\) erhält man so Petes exakte Häufigkeitstabelle, mit \((6,6)\) Colins Tabelle. Zwar werden die Arrays bis zur maximalen Summe dimensioniert, aber nach jeder Stufe tragen nur die mathematisch zulässigen Summen einen von Null verschiedenen Wert.
Nach dem Aufbau beider Verteilungen vergleicht die Implementierung jeden erreichbaren Pete-Wert mit jedem erreichbaren Colin-Wert. Für jedes Paar wird das Produkt der beiden Häufigkeiten zur Gesamtzahl addiert; nur wenn Petes Summe größer ist, fließt dasselbe Produkt zusätzlich in den Gewinnzähler ein. Erst ganz am Ende wird der Quotient aus Gewinnfällen und Gesamtfällen gebildet.
Eine Version enthält zusätzlich einen kleinen Kontrollfall für 1 d4 gegen 1 d6, und eine Version erlaubt es, die Würfelparameter per Kommandozeile zu verändern. Diese Zusätze ändern aber nichts am Kernverfahren: In allen drei Sprachen ist der zentrale Gedanke identisch.
Für \(n\) Würfel mit \(s\) Seiten hat der Aufbau der Verteilung \(n\) Stufen, betrachtet Summen bis \(ns\) und probiert für jede erreichbare Summe alle \(s\) möglichen Augenzahlen des neuen Würfels aus. Das ergibt \(O(n\cdot ns\cdot s)=O(n^2s^2)\) Zeit, oder anschaulicher \(O(n\cdot s\cdot M)\) mit \(M=ns\) als maximaler Summe. Der Speicherbedarf ist \(O(M)\) für aktuelles und nächstes Array.
Die abschließende Vergleichsphase kostet \(O(S_P S_C)\), wobei \(S_P\) und \(S_C\) die Größen der beiden Summenintervalle bezeichnen. In Problem 205 sind diese Intervalle sehr klein: Pete hat nur die Werte \(9\) bis \(36\), Colin nur \(6\) bis \(36\). Deshalb ist die exakte Methode schnell, obwohl der zugrunde liegende Ergebnisraum aus mehr als zwölf Milliarden gemeinsamen Würfen besteht.
Pete dokuz tane 4 yüzlü zar attığı için toplamı yalnızca \(9\) ile \(36\) arasında olabilir. Colin ise altı tane 6 yüzlü zar atar ve onun toplamı \(6\) ile \(36\) arasındadır. Aranan değer, Pete'in toplamının Colin'in toplamından kesin olarak büyük olma olasılığıdır.
Ham kuvvetle çözüm, bütün \(4^9 \cdot 6^6\) ortak sonucu tek tek düşünmek olurdu. Asıl fikir, tam zar dizisini değil sadece elde edilen toplamı takip etmektir; böylece problem iki kesin toplam dağılımına ve bu dağılımların son karşılaştırmasına indirgenir.
Doğru durum uzayı, belirli sayıda zar atıldıktan sonraki toplamdır. Uygulamalar da tam olarak bu sayım tablosunu kurar.
\(n\) adet \(s\) yüzlü zar için \(D_i(t)\), ilk \(i\) zarın toplamı \(t\) olan sıralı sonuçların sayısı olsun. Başlangıç durumu
$$D_0(0)=1,\qquad D_0(t)=0 \text{ eğer } t\neq 0$$
şeklindedir. \(i\) zar atıldıktan sonra yalnızca \(i \le t \le is\) aralığındaki toplamlar mümkündür. Ayrıca
$$\sum_t D_i(t)=s^i$$
değişmezi vardır; çünkü \(D_i\), \(i\) bağımsız \(s\) yüzlü zarın bütün sıralı sonuçlarını sayar.
Problem 205'te Pete'in son tablosu
$$P(p)=D^{(4)}_9(p),\qquad 9\le p\le 36,$$
Colin'in son tablosu ise
$$C(c)=D^{(6)}_6(c),\qquad 6\le c\le 36$$
olarak yazılır.
Yeni bir \(s\) yüzlü zar eklendiğinde eski toplam \(u\), \(u+1,u+2,\dots,u+s\) değerlerine gidebilir. Bu yüzden bir sonraki satır
$$D_{i+1}(t)=\sum_{f=1}^{s} D_i(t-f)$$
reküransını sağlar; mümkün olmayan indisler sıfır kabul edilir. Üç dildeki kodların uyguladığı ayrık evrişim tam olarak budur.
Aynı ifade üreteç fonksiyonu diliyle de yazılabilir:
$$D_n(t)=[x^t]\,(x+x^2+\cdots+x^s)^n.$$
Örneğin iki tane 4 yüzlü zar için
$$D_2(5)=D_1(4)+D_1(3)+D_1(2)+D_1(1)=4,$$
çünkü \((1,4),(2,3),(3,2),(4,1)\) sıralı çiftlerinin hepsi toplam \(5\) verir.
\(P\) ve \(C\) tabloları kurulduktan sonra artık mesele zar yüzlerini değil, toplam çiftlerini karşılaştırmaktır. Pete \(p\) toplamına \(P(p)\) yolla, Colin \(c\) toplamına \(C(c)\) yolla ulaşıyorsa, bağımsızlıktan dolayı ortak \((p,c)\) olayı
$$P(p)\,C(c)$$
farklı biçimde gerçekleşir.
Toplam ortak sonuç sayısı
$$\Omega=\sum_{p=9}^{36}\sum_{c=6}^{36} P(p)C(c)=4^9\cdot 6^6$$
olur. Pete yalnızca \(p>c\) iken kazanır. Bu nedenle kazanım sayısı
$$W=\sum_{p=9}^{36}\sum_{c=6}^{36} [p>c]\,P(p)C(c)$$
şeklindedir. Aranan olasılık da
$$\Pr(\text{Pete kazanır})=\frac{W}{\Omega}$$
olur. Beraberlikler otomatik olarak dışarıda kalır; çünkü istenen şey sıkı eşitsizliktir.
Aynı mantığın küçük bir örneği reküransı ve son karşılaştırmayı doğrulamak için idealdir. Pete 1 d4, Colin 1 d6 atsın. O zaman
$$P(1)=P(2)=P(3)=P(4)=1,\qquad C(1)=C(2)=C(3)=C(4)=C(5)=C(6)=1.$$
Toplam \(4\cdot 6=24\) eş ağırlıklı ortak durum vardır. Pete şu çiftlerde kazanır:
$$ (2,1),\ (3,1),\ (3,2),\ (4,1),\ (4,2),\ (4,3). $$
Dolayısıyla \(W=6\) ve
$$\Pr(\text{Pete kazanır})=\frac{6}{24}=\frac14.$$
Bu, asıl \(9\) d\(4\) ile \(6\) d\(6\) probleminde kullanılan sayımın aynısıdır; yalnızca tablo daha küçüktür.
C++, Python ve Java uygulamalarının hepsi olası toplamlarla indekslenen bir dizi tutar. Başlangıçta yalnızca toplam \(0\)'da kütle vardır. Sonra her zar için aynı güncelleme yapılır: bir sonraki aşama için yeni bir dizi oluşturulur ve mevcut her sayım, yüz değerleri \(1\) ile \(s\) eklenerek uygun yeni indislerin üzerine aktarılır.
Bu yordam \((9,4)\) ile çağrıldığında Pete'in kesin sayım tablosunu, \((6,6)\) ile çağrıldığında Colin'in tablosunu üretir. Diziler teorik maksimum toplam kadar ayrılmış olsa da her aşamada yalnızca matematiksel olarak mümkün aralıkta sıfırdan farklı değerler bulunur.
İki tablo hazır olduğunda uygulama her Pete toplamını her Colin toplamıyla karşılaştırır. Her çift için iki sayımın çarpımı genel toplam sayaçına eklenir; yalnızca Pete'in toplamı daha büyükse aynı çarpım kazanım sayaçına da eklenir. Olasılık ancak bütün sayımlar bittikten sonra, kazanım sayısının toplam duruma bölünmesiyle elde edilir.
Bir uygulama ayrıca 1 d4 ile 1 d6 için küçük bir kontrol örneği içerir ve bir sürüm zar parametrelerini komut satırından değiştirmeye izin verir. Bunlar yardımcı ayrıntılardır; çekirdek algoritma üç dilde de aynıdır.
\(n\) adet \(s\) yüzlü zar için dağılım kurucu, \(n\) aşama yapar, \(ns\)'e kadar toplamları tarar ve erişilebilir her toplam için yeni zarın \(s\) farklı yüzünü dener. Bu da \(O(n\cdot ns\cdot s)=O(n^2s^2)\) zaman verir. Aynı ifade, \(M=ns\) en büyük toplam olmak üzere \(O(n\cdot s\cdot M)\) diye de yazılabilir. Bellek kullanımı mevcut ve sonraki diziler için \(O(M)\)'dir.
Son karşılaştırma aşaması \(O(S_P S_C)\) maliyetlidir; burada \(S_P\) ve \(S_C\), Pete ile Colin'in toplam aralıklarının boyutlarıdır. Problem 205'te bu aralıklar küçüktür: Pete yalnızca \(9\) ile \(36\), Colin ise \(6\) ile \(36\) arasında değer alır. Bu nedenle örnek uzayı on iki milyardan fazla ortak sonuç içerse bile kesin yöntem oldukça hızlıdır.
Pete lanza nueve dados de 4 caras, así que su suma solo puede estar entre \(9\) y \(36\). Colin lanza seis dados de 6 caras, por lo que su suma está entre \(6\) y \(36\). Se pide la probabilidad exacta de que la suma de Pete sea estrictamente mayor que la de Colin.
Un enfoque ingenuo examinaría por separado los \(4^9 \cdot 6^6\) resultados conjuntos posibles. La simplificación decisiva consiste en olvidar la secuencia completa de caras y conservar solo cuántas secuencias producen cada suma alcanzable.
El estado correcto no es la lista de caras individuales, sino la suma acumulada después de cierto número de dados. Eso es exactamente lo que cuentan las implementaciones.
Para \(n\) dados de \(s\) caras, definimos \(D_i(t)\) como el número de resultados ordenados de los primeros \(i\) dados cuya suma es \(t\). El estado inicial es
$$D_0(0)=1,\qquad D_0(t)=0 \text{ para } t\neq 0.$$
Después de \(i\) dados, solo pueden aparecer sumas con \(i \le t \le is\). Además se mantiene el invariante
$$\sum_t D_i(t)=s^i,$$
porque \(D_i\) cuenta todos los resultados ordenados de \(i\) dados independientes de \(s\) caras.
En el problema 205, la tabla final de Pete es
$$P(p)=D^{(4)}_9(p),\qquad 9\le p\le 36,$$
y la de Colin es
$$C(c)=D^{(6)}_6(c),\qquad 6\le c\le 36.$$
Al añadir un nuevo dado de \(s\) caras, una suma previa \(u\) puede pasar a \(u+1,u+2,\dots,u+s\). Por tanto, la siguiente fila satisface
$$D_{i+1}(t)=\sum_{f=1}^{s} D_i(t-f),$$
donde los índices imposibles se interpretan como cero. Esa es exactamente la convolución discreta que implementan los programas.
La misma idea puede escribirse con funciones generadoras:
$$D_n(t)=[x^t]\,(x+x^2+\cdots+x^s)^n.$$
Por ejemplo, con dos dados de 4 caras,
$$D_2(5)=D_1(4)+D_1(3)+D_1(2)+D_1(1)=4,$$
porque los pares ordenados \((1,4),(2,3),(3,2),(4,1)\) producen la suma \(5\).
Una vez conocidas \(P\) y \(C\), el juego original se reduce a comparar pares de sumas. Si Pete alcanza \(p\) de \(P(p)\) maneras y Colin alcanza \(c\) de \(C(c)\) maneras, entonces el evento conjunto \((p,c)\) aparece en
$$P(p)\,C(c)$$
maneras, por independencia.
El número total de resultados conjuntos es entonces
$$\Omega=\sum_{p=9}^{36}\sum_{c=6}^{36} P(p)C(c)=4^9\cdot 6^6.$$
Pete gana exactamente cuando \(p>c\), así que el número de victorias es
$$W=\sum_{p=9}^{36}\sum_{c=6}^{36} [p>c]\,P(p)C(c).$$
La probabilidad pedida queda
$$\Pr(\text{Pete gana})=\frac{W}{\Omega}.$$
Los empates no cuentan, porque la condición del problema es una desigualdad estricta.
Una versión pequeña del mismo juego sirve para verificar tanto la recurrencia como la comparación final. Si Pete lanza 1 d4 y Colin 1 d6, entonces
$$P(1)=P(2)=P(3)=P(4)=1,\qquad C(1)=C(2)=C(3)=C(4)=C(5)=C(6)=1.$$
Hay \(4\cdot 6=24\) resultados conjuntos con el mismo peso. Pete gana en
$$ (2,1),\ (3,1),\ (3,2),\ (4,1),\ (4,2),\ (4,3). $$
Por tanto \(W=6\) y
$$\Pr(\text{Pete gana})=\frac{6}{24}=\frac14.$$
Es exactamente la misma lógica combinatoria que en el caso real \(9\) d\(4\) frente a \(6\) d\(6\), solo que con tablas mucho más pequeñas.
Las implementaciones en C++, Python y Java mantienen un arreglo indexado por sumas posibles. Empiezan con la distribución degenerada concentrada en la suma \(0\), y luego repiten una actualización por dado: crean un arreglo nuevo para la siguiente etapa y trasladan cada conteo actual a las posiciones obtenidas al añadir los valores \(1\) hasta \(s\).
Ejecutar esa rutina con \((9,4)\) produce la tabla exacta de Pete; ejecutarla con \((6,6)\) produce la de Colin. Aunque los arreglos se reservan hasta la suma máxima, tras cada etapa solo el intervalo matemáticamente válido contiene entradas no nulas.
Una vez construidas ambas tablas, la implementación compara cada suma alcanzable de Pete con cada suma alcanzable de Colin. Para cada par multiplica los dos conteos, añade el producto al total general y lo añade también al contador de victorias solo cuando la suma de Pete es mayor. La división para obtener la probabilidad se realiza una sola vez, al final.
Una versión incluye además una pequeña comprobación con 1 d4 frente a 1 d6, y una implementación permite cambiar los parámetros de los dados desde la línea de comandos. Esos detalles son accesorios; el algoritmo central es idéntico en los tres lenguajes.
Para \(n\) dados de \(s\) caras, el constructor de la distribución realiza \(n\) etapas, recorre sumas hasta \(ns\) y, para cada suma alcanzable, prueba las \(s\) caras del nuevo dado. Eso da \(O(n\cdot ns\cdot s)=O(n^2s^2)\) tiempo, o equivalentemente \(O(n\cdot s\cdot M)\) si \(M=ns\) es la suma máxima posible. La memoria es \(O(M)\) para el arreglo actual y el siguiente.
La fase final de comparación cuesta \(O(S_P S_C)\), donde \(S_P\) y \(S_C\) son los tamaños de los intervalos de sumas de Pete y Colin. En el problema 205 esos intervalos son pequeños: Pete solo cubre \(9\) a \(36\), y Colin \(6\) a \(36\). Por eso el método exacto es muy rápido a pesar de que el espacio muestral subyacente contiene más de doce mil millones de resultados conjuntos.
Pete 掷九个 4 面骰，因此他的总点数只能落在 \(9\) 到 \(36\) 之间。Colin 掷六个 6 面骰，因此他的总点数落在 \(6\) 到 \(36\) 之间。目标是计算 Pete 的总点数严格大于 Colin 的总点数这一事件的精确概率。
如果直接枚举，就要分别处理全部 \(4^9 \cdot 6^6\) 个联合结果。真正有效的压缩方式是：不再关心每个骰子的完整出目序列，只关心“某个总和出现了多少次”。这样问题就变成两张精确的和分布表，以及最后对这两张表做一次严格大小比较。
因此最自然的状态不是“具体掷出了哪些面”，而是“掷完若干个骰子后当前总和是多少”。三份实现都在计算这个状态。
对 \(n\) 个 \(s\) 面骰，记 \(D_i(t)\) 为“前 \(i\) 个骰子的点数和等于 \(t\) 的有序结果个数”。初始状态是
$$D_0(0)=1,\qquad D_0(t)=0 \text{ 当 } t\neq 0.$$
掷完 \(i\) 个骰子后，只有 \(i \le t \le is\) 的和才可能出现。另外有一个非常重要的不变量：
$$\sum_t D_i(t)=s^i,$$
因为 \(D_i\) 统计的正是 \(i\) 个独立 \(s\) 面骰的全部有序结果。
在本题中，Pete 的最终计数表为
$$P(p)=D^{(4)}_9(p),\qquad 9\le p\le 36,$$
Colin 的最终计数表为
$$C(c)=D^{(6)}_6(c),\qquad 6\le c\le 36.$$
如果再加入一个 \(s\) 面骰，原来的和 \(u\) 可以转移到 \(u+1,u+2,\dots,u+s\)。因此下一层满足
$$D_{i+1}(t)=\sum_{f=1}^{s} D_i(t-f),$$
其中不合法的下标视为零。这正是三份代码都在执行的离散卷积递推。
同一个事实也可以写成生成函数的系数形式：
$$D_n(t)=[x^t]\,(x+x^2+\cdots+x^s)^n.$$
例如，对两个 4 面骰，有
$$D_2(5)=D_1(4)+D_1(3)+D_1(2)+D_1(1)=4,$$
因为有序对 \((1,4),(2,3),(3,2),(4,1)\) 都会得到总和 \(5\)。
一旦 \(P\) 和 \(C\) 两张表都求出，原题就不再是“掷骰子问题”，而是“比较总和问题”。如果 Pete 以 \(P(p)\) 种方式得到 \(p\)，Colin 以 \(C(c)\) 种方式得到 \(c\)，那么由于两人的投掷彼此独立，联合事件 \((p,c)\) 会出现
$$P(p)\,C(c)$$
次。
因此，全部联合结果总数为
$$\Omega=\sum_{p=9}^{36}\sum_{c=6}^{36} P(p)C(c)=4^9\cdot 6^6.$$
Pete 获胜当且仅当 \(p>c\)，所以获胜结果数为
$$W=\sum_{p=9}^{36}\sum_{c=6}^{36} [p>c]\,P(p)C(c).$$
于是所求概率就是
$$\Pr(\text{Pete 获胜})=\frac{W}{\Omega}.$$
因为题目要求的是严格大于，所以平局不会被计入胜利。
一个更小的版本可以同时检验递推和最终的严格比较。假设 Pete 掷 1 个 4 面骰，Colin 掷 1 个 6 面骰，那么
$$P(1)=P(2)=P(3)=P(4)=1,\qquad C(1)=C(2)=C(3)=C(4)=C(5)=C(6)=1.$$
此时共有 \(4\cdot 6=24\) 个等权联合结果。Pete 获胜的情况是
$$ (2,1),\ (3,1),\ (3,2),\ (4,1),\ (4,2),\ (4,3). $$
因此 \(W=6\)，从而
$$\Pr(\text{Pete 获胜})=\frac{6}{24}=\frac14.$$
这和正式题目 \(9\) 个 d\(4\) 对 \(6\) 个 d\(6\) 的思路完全一致，只是状态空间更小，便于人工核对。
C++、Python 和 Java 实现都维护一个“按总和索引”的数组。开始时只有总和 \(0\) 的计数为 \(1\)。随后每加入一个新骰子，就创建下一层的新数组，并把当前每个总和的计数分发到加上面值 \(1\) 到 \(s\) 后对应的新位置。
用参数 \((9,4)\) 运行这一过程，就得到 Pete 的精确计数表；用参数 \((6,6)\) 运行，就得到 Colin 的精确计数表。虽然数组长度按最大可能总和分配，但每一层真正非零的部分始终只出现在数学上允许的区间里。
两张表准备好以后，实现会把 Pete 的每一个可达总和与 Colin 的每一个可达总和逐一比较。对每一对 \((p,c)\)，先把两边计数的乘积加入总结果数；如果 \(p>c\)，再把同一个乘积加入 Pete 的胜利计数。所有计数全部累加完毕之后，才进行一次最终除法，得到概率。
其中一个实现还包含 1 d4 对 1 d6 的小型校验，另一个版本允许从命令行修改骰子参数。这些都是辅助功能，不改变核心算法：三种语言都遵循同一套“先做精确分布，再比较分布”的流程。
对 \(n\) 个 \(s\) 面骰，构造分布表需要做 \(n\) 层更新，每层扫描到 \(ns\) 为止的总和范围，并对每个可达总和尝试新骰子的 \(s\) 个面值。因此时间复杂度是 \(O(n\cdot ns\cdot s)=O(n^2s^2)\)。若记最大可能总和为 \(M=ns\)，也可以写成 \(O(n\cdot s\cdot M)\)。空间复杂度是 \(O(M)\)，因为只需要当前层和下一层两个数组。
两张表构造完后，最终比较阶段的代价是 \(O(S_P S_C)\)，其中 \(S_P\) 与 \(S_C\) 分别表示 Pete 和 Colin 的总和区间长度。在本题里，这两个区间都很小：Pete 只覆盖 \(9\) 到 \(36\)，Colin 只覆盖 \(6\) 到 \(36\)。因此即使底层样本空间有超过一百二十亿个联合结果，精确算法仍然非常快。
Пит бросает девять 4-гранных кубиков, поэтому его сумма может лежать только в диапазоне от \(9\) до \(36\). Колин бросает шесть 6-гранных кубиков, и его сумма лежит между \(6\) и \(36\). Нужно найти точную вероятность того, что сумма Пита строго больше суммы Колина.
Наивный перебор рассматривал бы по отдельности все \(4^9 \cdot 6^6\) совместных исходов. Главная идея решения состоит в том, чтобы не хранить всю последовательность выпавших граней, а считать только число способов получить каждую достижимую сумму.
Поэтому естественное состояние здесь не набор отдельных значений на кубиках, а текущая сумма после заданного количества бросков. Именно такую таблицу и строят реализации.
Для \(n\) кубиков с \(s\) гранями обозначим через \(D_i(t)\) число упорядоченных исходов первых \(i\) кубиков, сумма которых равна \(t\). Начальное состояние таково:
$$D_0(0)=1,\qquad D_0(t)=0 \text{ при } t\neq 0.$$
После \(i\) кубиков возможны только суммы \(i \le t \le is\). Кроме того, выполняется инвариант
$$\sum_t D_i(t)=s^i,$$
потому что \(D_i\) перечисляет все упорядоченные исходы \(i\) независимых \(s\)-гранных кубиков.
В задаче 205 итоговая таблица Пита равна
$$P(p)=D^{(4)}_9(p),\qquad 9\le p\le 36,$$
а итоговая таблица Колина равна
$$C(c)=D^{(6)}_6(c),\qquad 6\le c\le 36.$$
Если добавить еще один \(s\)-гранный кубик, прежняя сумма \(u\) может перейти в \(u+1,u+2,\dots,u+s\). Поэтому следующая строка удовлетворяет формуле
$$D_{i+1}(t)=\sum_{f=1}^{s} D_i(t-f),$$
где невозможные индексы считаются нулевыми. Именно эта дискретная свертка реализована во всех трех версиях программы.
То же самое можно записать через производящую функцию:
$$D_n(t)=[x^t]\,(x+x^2+\cdots+x^s)^n.$$
Например, для двух 4-гранных кубиков
$$D_2(5)=D_1(4)+D_1(3)+D_1(2)+D_1(1)=4,$$
поскольку упорядоченные пары \((1,4),(2,3),(3,2),(4,1)\) все дают сумму \(5\).
После того как построены \(P\) и \(C\), исходная игра сводится к сравнению пар сумм. Если Пит получает \(p\) ровно \(P(p)\) способами, а Колин получает \(c\) ровно \(C(c)\) способами, то совместное событие \((p,c)\) происходит
$$P(p)\,C(c)$$
способами благодаря независимости бросков.
Значит, общее число совместных исходов равно
$$\Omega=\sum_{p=9}^{36}\sum_{c=6}^{36} P(p)C(c)=4^9\cdot 6^6.$$
Пит выигрывает тогда и только тогда, когда \(p>c\). Поэтому число выигрышных исходов равно
$$W=\sum_{p=9}^{36}\sum_{c=6}^{36} [p>c]\,P(p)C(c).$$
Искомая вероятность имеет вид
$$\Pr(\text{Пит выигрывает})=\frac{W}{\Omega}.$$
Ничьи не учитываются, потому что в условии требуется строгое превосходство.
Уменьшенная версия той же игры полезна как проверка и рекуррентной формулы, и финального сравнения. Пусть Пит бросает 1 d4, а Колин 1 d6. Тогда
$$P(1)=P(2)=P(3)=P(4)=1,\qquad C(1)=C(2)=C(3)=C(4)=C(5)=C(6)=1.$$
Всего имеется \(4\cdot 6=24\) равновесных совместных исхода. Пит выигрывает в случаях
$$ (2,1),\ (3,1),\ (3,2),\ (4,1),\ (4,2),\ (4,3). $$
Следовательно, \(W=6\) и
$$\Pr(\text{Пит выигрывает})=\frac{6}{24}=\frac14.$$
Это ровно тот же принцип подсчета, что и в полном случае \(9\) d\(4\) против \(6\) d\(6\), только на значительно меньшем пространстве состояний.
Реализации на C++, Python и Java поддерживают массив, индексированный возможной суммой. Они начинают с вырожденного распределения, сосредоточенного в точке \(0\), а затем для каждого нового кубика создают следующий массив и переносят каждое текущее количество в позиции, получаемые прибавлением значений граней \(1,\dots,s\).
Запуск этой процедуры с параметрами \((9,4)\) дает точную таблицу Пита, а с параметрами \((6,6)\) точную таблицу Колина. Хотя массивы выделяются до максимальной суммы, после каждого шага ненулевыми остаются только те позиции, которые допустимы математически.
Когда обе таблицы уже построены, программа сравнивает каждую достижимую сумму Пита с каждой достижимой суммой Колина. Для каждой пары перемножаются два счетчика; произведение добавляется к общему числу исходов, а к числу побед Пита оно добавляется только при условии, что сумма Пита больше. Деление выполняется один раз в самом конце.
Одна из реализаций также содержит маленькую проверку для случая 1 d4 против 1 d6, а одна версия позволяет менять параметры кубиков через командную строку. Это вспомогательные детали; базовый алгоритм в C++, Python и Java один и тот же.
Для \(n\) кубиков с \(s\) гранями построение распределения делает \(n\) слоев обновления, просматривает суммы до \(ns\) и для каждой достижимой суммы рассматривает \(s\) граней нового кубика. Это дает \(O(n\cdot ns\cdot s)=O(n^2s^2)\) по времени, или эквивалентно \(O(n\cdot s\cdot M)\), если \(M=ns\) обозначает максимальную возможную сумму. Память равна \(O(M)\) для текущего и следующего массивов.
Финальная фаза сравнения стоит \(O(S_P S_C)\), где \(S_P\) и \(S_C\) — размеры диапазонов сумм Пита и Колина. В задаче 205 эти диапазоны малы: Пит принимает только значения от \(9\) до \(36\), а Колин от \(6\) до \(36\). Поэтому точный метод работает быстро, несмотря на то что исходное пространство совместных результатов содержит более двенадцати миллиардов вариантов.
يرمي Pete تسعة نرود رباعية الأوجه، ولذلك لا يمكن أن يكون مجموعه إلا بين \(9\) و\(36\). أما Colin فيرمي ستة نرود سداسية الأوجه، فيقع مجموعه بين \(6\) و\(36\). المطلوب هو حساب الاحتمال الدقيق لأن يكون مجموع Pete أكبر من مجموع Colin بشكل صارم.
العد المباشر سيتعامل مع جميع النتائج المشتركة وعددها \(4^9 \cdot 6^6\) على حدة. الفكرة الحاسمة هي ألا نحتفظ بالتتابع الكامل للوجوه الظاهرة، بل نعد فقط عدد الطرق التي تعطي كل مجموع ممكن.
إذن فضاء الحالات المناسب هنا ليس قائمة الوجوه الفردية، بل المجموع الجاري بعد عدد معين من الرميات. وهذا هو بالضبط ما تبنيه التطبيقات.
لـ \(n\) من النرود ذات \(s\) أوجه، نرمز بـ \(D_i(t)\) إلى عدد النتائج المرتبة لأول \(i\) نرود التي مجموعها \(t\). حالة البداية هي
$$D_0(0)=1,\qquad D_0(t)=0 \quad (t\neq 0).$$
بعد \(i\) نرود، لا يمكن أن تظهر إلا المجاميع التي تحقق \(i \le t \le is\). وهناك ثابت مهم أيضًا هو
$$\sum_t D_i(t)=s^i,$$
لأن \(D_i\) يعد جميع النتائج المرتبة الممكنة لـ \(i\) من النرود المستقلة ذات \(s\) أوجه.
في المسألة 205 يكون جدول Pete النهائي
$$P(p)=D^{(4)}_9(p),\qquad 9\le p\le 36,$$
ويكون جدول Colin النهائي
$$C(c)=D^{(6)}_6(c),\qquad 6\le c\le 36.$$
عند إضافة نرد جديد ذي \(s\) أوجه، يمكن للمجموع القديم \(u\) أن ينتقل إلى \(u+1,u+2,\dots,u+s\). لذلك يحقق الصف التالي العلاقة
$$D_{i+1}(t)=\sum_{f=1}^{s} D_i(t-f),$$
مع اعتبار الفهارس غير الممكنة مساوية للصفر. هذه هي علاقة الالتفاف المنفصل التي تنفذها الشيفرات في اللغات الثلاث.
ويمكن كتابة الفكرة نفسها بصيغة الدالة المولدة:
$$D_n(t)=[x^t]\,(x+x^2+\cdots+x^s)^n.$$
فعلى سبيل المثال، مع نردين رباعيي الأوجه نحصل على
$$D_2(5)=D_1(4)+D_1(3)+D_1(2)+D_1(1)=4,$$
لأن الأزواج المرتبة \((1,4),(2,3),(3,2),(4,1)\) كلها تعطي المجموع \(5\).
بعد بناء الجدولين \(P\) و\(C\)، تتحول اللعبة من مسألة رميات فردية إلى مسألة مقارنة مجموعين. إذا وصل Pete إلى القيمة \(p\) بعدد \(P(p)\) من الطرق، ووصل Colin إلى القيمة \(c\) بعدد \(C(c)\) من الطرق، فإن الحدث المشترك \((p,c)\) يحدث بعدد
$$P(p)\,C(c)$$
من الطرق بسبب الاستقلال.
إذن العدد الكلي للنتائج المشتركة هو
$$\Omega=\sum_{p=9}^{36}\sum_{c=6}^{36} P(p)C(c)=4^9\cdot 6^6.$$
ويفوز Pete فقط عندما \(p>c\)، ولذلك يكون عدد حالات الفوز
$$W=\sum_{p=9}^{36}\sum_{c=6}^{36} [p>c]\,P(p)C(c).$$
ومن ثم فإن الاحتمال المطلوب هو
$$\Pr(p>c)=\frac{W}{\Omega}.$$
حالات التعادل لا تدخل في العد لأن نص المسألة يشترط فوزًا صارمًا.
نسخة صغيرة من اللعبة نفسها مفيدة لفحص العلاقة التكرارية وفحص المقارنة النهائية معًا. إذا رمى Pete نردًا واحدًا من نوع d4 ورمى Colin نردًا واحدًا من نوع d6، فإن
$$P(1)=P(2)=P(3)=P(4)=1,\qquad C(1)=C(2)=C(3)=C(4)=C(5)=C(6)=1.$$
يوجد \(4\cdot 6=24\) ناتجًا مشتركًا متساوي الوزن. يفوز Pete في الحالات
$$ (2,1),\ (3,1),\ (3,2),\ (4,1),\ (4,2),\ (4,3). $$
إذًا \(W=6\)، ومن ثم
$$\Pr(p>c)=\frac{6}{24}=\frac14.$$
وهذه هي الفكرة العدّية نفسها المستخدمة في المسألة الأصلية \(9\) d\(4\) مقابل \(6\) d\(6\)، لكن على فضاء حالات أصغر بكثير.
تحتفظ تطبيقات C++ وPython وJava جميعًا بمصفوفة مفهرسة بحسب المجاميع الممكنة. تبدأ من توزيع متدهور متمركز عند المجموع \(0\)، ثم تكرر تحديثًا واحدًا لكل نرد: تُنشئ مصفوفة جديدة للمرحلة التالية، ثم تدفع كل عدد حالي إلى المواقع الناتجة عن إضافة قيم الوجوه من \(1\) إلى \(s\).
تشغيل هذه العملية على \((9,4)\) يعطي جدول Pete الدقيق، وتشغيلها على \((6,6)\) يعطي جدول Colin الدقيق. ورغم أن المصفوفات تُحجز حتى أكبر مجموع ممكن، فإن القيم غير الصفرية تبقى بعد كل مرحلة محصورة في المجال الصحيح رياضيًا.
بعد اكتمال الجدولين، تقارن الشيفرة كل مجموع ممكن لـ Pete مع كل مجموع ممكن لـ Colin. لكل زوج تضرب العدّين معًا، وتضيف حاصل الضرب إلى العدد الكلي للنتائج، ثم تضيفه أيضًا إلى عداد الفوز فقط إذا كان مجموع Pete أكبر. لا يتم تحويل العد إلى احتمال إلا في النهاية بعد اكتمال جميع المجاميع.
تتضمن إحدى النسخ أيضًا حالة تحقق صغيرة للمباراة 1 d4 مقابل 1 d6، كما تسمح إحدى النسخ بتغيير معاملات النرود من سطر الأوامر. هذه تفاصيل مساعدة فقط؛ أما الخوارزمية الأساسية فهي نفسها في C++ وPython وJava.
بالنسبة إلى \(n\) من النرود ذات \(s\) أوجه، فإن بناء التوزيع يمر عبر \(n\) مراحل، ويفحص المجاميع حتى \(ns\)، ولكل مجموع قابل للوصول يجرّب الوجوه \(s\) الخاصة بالنرد الجديد. لذلك يكون الزمن \(O(n\cdot ns\cdot s)=O(n^2s^2)\)، أو بصورة مكافئة \(O(n\cdot s\cdot M)\) إذا كان \(M=ns\) هو أكبر مجموع ممكن. أما الذاكرة فهي \(O(M)\) للمصفوفتين الحالية والتالية.
مرحلة المقارنة النهائية تكلف \(O(S_P S_C)\)، حيث يمثل \(S_P\) و\(S_C\) حجمي نطاقي المجاميع لـ Pete وColin. في المسألة 205 هذان النطاقان صغيران جدًا: Pete لا يأخذ إلا القيم من \(9\) إلى \(36\)، وColin من \(6\) إلى \(36\). ولهذا تكون الطريقة الدقيقة سريعة جدًا رغم أن فضاء النتائج الأصلي يحتوي على أكثر من اثني عشر مليار نتيجة مشتركة.