The experiment is a chain of random sums built from the five Platonic dice. First roll a 4-sided die and call the result \(T\). Then roll \(T\) fair 6-sided dice and sum them to obtain \(C\). Next roll \(C\) fair 8-sided dice to obtain \(O\), then \(O\) fair 12-sided dice to obtain \(D\), and finally \(D\) fair 20-sided dice to obtain \(I\). The task is to compute \(\operatorname{Var}(I)\).
The local solution files do not enumerate huge distributions. Instead, they propagate only the mean and the variance from one layer to the next. That works because every stage has the same structure: a random number of independent fair dice are rolled and summed.
For a fair \(s\)-sided die \(X_s\) with values \(1,2,\dots,s\), the code uses
$$\mathbb{E}[X_s]=\frac{s+1}{2},\qquad \operatorname{Var}(X_s)=\frac{s^2-1}{12}.$$
These are exactly the values returned by uniform_die_stats in C++, Python, and Java. For the first die,
$$T \sim \text{Unif}\{1,2,3,4\},\qquad \mathbb{E}[T]=\frac{5}{2},\qquad \operatorname{Var}(T)=\frac{5}{4}.$$
Suppose \(N\) is a nonnegative integer-valued random variable, and conditional on \(N\) we roll \(N\) independent copies \(X_1,\dots,X_N\) of the same fair die, each with mean \(\mu\) and variance \(\sigma^2\). Let
$$S=\sum_{j=1}^{N} X_j.$$
Conditioning on \(N\) gives
$$\mathbb{E}[S\mid N]=N\mu,\qquad \operatorname{Var}(S\mid N)=N\sigma^2.$$
Applying the laws of total expectation and total variance,
$$\mathbb{E}[S]=\mathbb{E}\!\left[\mathbb{E}[S\mid N]\right]=\mu\,\mathbb{E}[N],$$
$$\operatorname{Var}(S)=\mathbb{E}\!\left[\operatorname{Var}(S\mid N)\right]+\operatorname{Var}\!\left(\mathbb{E}[S\mid N]\right)=\sigma^2\mathbb{E}[N]+\mu^2\operatorname{Var}(N).$$
This is the whole algorithm. The function transition_sum_of_random_dice in C++ and transition_sum in Python/Java implement exactly these two formulas.
If the current stage has mean \(m\) and variance \(v\), and the next die has \(s\) sides, define
$$a_s=\frac{s+1}{2},\qquad b_s=\frac{s^2-1}{12}.$$
Then the next stage has
$$m' = a_s\,m,\qquad v' = b_s\,m + a_s^2 v.$$
The solution starts from \((m,v)=(5/2,5/4)\) for \(T\), then applies this update for \(s=6,8,12,20\).
For the 6-sided layer, \(a_6=7/2\) and \(b_6=35/12\). Therefore
$$\mathbb{E}[C]=\frac{7}{2}\cdot\frac{5}{2}=\frac{35}{4},$$
$$\operatorname{Var}(C)=\frac{35}{12}\cdot\frac{5}{2}+\left(\frac{7}{2}\right)^2\cdot\frac{5}{4}=\frac{1085}{48}.$$
For the 8-sided layer, \(a_8=9/2\) and \(b_8=21/4\):
$$\mathbb{E}[O]=\frac{9}{2}\cdot\frac{35}{4}=\frac{315}{8},$$
$$\operatorname{Var}(O)=\frac{21}{4}\cdot\frac{35}{4}+\left(\frac{9}{2}\right)^2\cdot\frac{1085}{48}=\frac{32235}{64}.$$
For the 12-sided layer, \(a_{12}=13/2\) and \(b_{12}=143/12\):
$$\mathbb{E}[D]=\frac{13}{2}\cdot\frac{315}{8}=\frac{4095}{16},$$
$$\operatorname{Var}(D)=\frac{143}{12}\cdot\frac{315}{8}+\left(\frac{13}{2}\right)^2\cdot\frac{32235}{64}=\frac{5567835}{256}.$$
For the 20-sided layer, \(a_{20}=21/2\) and \(b_{20}=133/4\):
$$\mathbb{E}[I]=\frac{21}{2}\cdot\frac{4095}{16}=\frac{85995}{32},$$
$$\operatorname{Var}(I)=\frac{133}{4}\cdot\frac{4095}{16}+\left(\frac{21}{2}\right)^2\cdot\frac{5567835}{256}=\frac{2464129395}{1024}.$$
So the requested variance is
$$\boxed{\operatorname{Var}(I)=\frac{2464129395}{1024}\approx 2406376.3623.}$$
The C++ version includes an explicit validation step. It computes the statistics of \(C\) in two independent ways:
First, it uses the moment formula above. Second, brute_one_layer_uniform_count(4, 6) constructs the full probability distribution when the number of dice is uniform on \(\{1,2,3,4\}\), by repeated convolution of one-die distributions. The program compares both mean and variance with a tight relative tolerance. This confirms that the recurrence is not merely plausible; it matches the exact distribution for the first nontrivial layer.
The three implementations share the same mathematical core. C++ stores the pair \((\text{mean}, \text{variance})\) in a Stats struct using long double, then chains four calls to transition_sum_of_random_dice. Python and Java do the same update in a loop or sequence of assignments. All three versions finally format the variance to four decimal places, which yields 2406376.3623.
The actual solver performs a fixed number of arithmetic operations, so its time complexity is \(O(1)\) and its memory usage is \(O(1)\). The optional C++ checkpoint also remains \(O(1)\) for this problem because it is hard-coded for the single small case \((4,6)\); it is a verification device, not part of the scalable algorithm.
Das Zufallsexperiment besteht aus einer Kette verschachtelter Summen mit den fünf platonischen Würfeln. Zuerst wird ein 4-seitiger Würfel geworfen; das Ergebnis heiße \(T\). Dann werden \(T\) faire 6-seitige Würfel geworfen und aufsummiert; diese Summe heiße \(C\). Danach entstehen \(O\) aus \(C\) Würfen mit d8, \(D\) aus \(O\) Würfen mit d12 und schließlich \(I\) aus \(D\) Würfen mit d20. Gesucht ist \(\operatorname{Var}(I)\).
Die lokalen Lösungsdateien berechnen keine riesigen Verteilungen. Sie transportieren nur Erwartungswert und Varianz von einer Ebene zur nächsten. Genau das genügt, weil jede Stufe dieselbe Form hat: Eine zufällige Anzahl unabhängiger fairer Würfel wird addiert.
Für einen fairen \(s\)-seitigen Würfel \(X_s\) mit Werten \(1,2,\dots,s\) verwendet der Code
$$\mathbb{E}[X_s]=\frac{s+1}{2},\qquad \operatorname{Var}(X_s)=\frac{s^2-1}{12}.$$
Genau diese Werte liefert uniform_die_stats in C++, Python und Java. Für den ersten Wurf gilt damit
$$T \sim \text{Unif}\{1,2,3,4\},\qquad \mathbb{E}[T]=\frac{5}{2},\qquad \operatorname{Var}(T)=\frac{5}{4}.$$
Sei \(N\) eine ganzzahlige Zufallsvariable und seien \(X_1,\dots,X_N\) bedingt auf \(N\) unabhängige Kopien desselben fairen Würfels mit Erwartungswert \(\mu\) und Varianz \(\sigma^2\). Setze
$$S=\sum_{j=1}^{N} X_j.$$
Dann gilt bedingt auf \(N\)
$$\mathbb{E}[S\mid N]=N\mu,\qquad \operatorname{Var}(S\mid N)=N\sigma^2.$$
Mit Satz von der totalen Erwartung und totalen Varianz folgt
$$\mathbb{E}[S]=\mu\,\mathbb{E}[N],$$
$$\operatorname{Var}(S)=\sigma^2\mathbb{E}[N]+\mu^2\operatorname{Var}(N).$$
Genau diese zwei Formeln implementieren transition_sum_of_random_dice in C++ und transition_sum in Python bzw. Java.
Hat die aktuelle Stufe Mittelwert \(m\) und Varianz \(v\), und der nächste Würfel besitzt \(s\) Seiten, so definiert man
$$a_s=\frac{s+1}{2},\qquad b_s=\frac{s^2-1}{12}.$$
Für die nächste Stufe erhält man dann
$$m' = a_s\,m,\qquad v' = b_s\,m + a_s^2 v.$$
Die Lösung startet also bei \((m,v)=(5/2,5/4)\) für \(T\) und wendet dieses Update anschließend für \(s=6,8,12,20\) an.
Für die 6-seitige Ebene sind \(a_6=7/2\) und \(b_6=35/12\). Damit
$$\mathbb{E}[C]=\frac{7}{2}\cdot\frac{5}{2}=\frac{35}{4},$$
$$\operatorname{Var}(C)=\frac{35}{12}\cdot\frac{5}{2}+\left(\frac{7}{2}\right)^2\cdot\frac{5}{4}=\frac{1085}{48}.$$
Für die 8-seitige Ebene mit \(a_8=9/2\) und \(b_8=21/4\):
$$\mathbb{E}[O]=\frac{9}{2}\cdot\frac{35}{4}=\frac{315}{8},$$
$$\operatorname{Var}(O)=\frac{21}{4}\cdot\frac{35}{4}+\left(\frac{9}{2}\right)^2\cdot\frac{1085}{48}=\frac{32235}{64}.$$
Für die 12-seitige Ebene mit \(a_{12}=13/2\) und \(b_{12}=143/12\):
$$\mathbb{E}[D]=\frac{13}{2}\cdot\frac{315}{8}=\frac{4095}{16},$$
$$\operatorname{Var}(D)=\frac{143}{12}\cdot\frac{315}{8}+\left(\frac{13}{2}\right)^2\cdot\frac{32235}{64}=\frac{5567835}{256}.$$
Für die 20-seitige Ebene mit \(a_{20}=21/2\) und \(b_{20}=133/4\):
$$\mathbb{E}[I]=\frac{21}{2}\cdot\frac{4095}{16}=\frac{85995}{32},$$
$$\operatorname{Var}(I)=\frac{133}{4}\cdot\frac{4095}{16}+\left(\frac{21}{2}\right)^2\cdot\frac{5567835}{256}=\frac{2464129395}{1024}.$$
Also lautet die gesuchte Varianz
$$\boxed{\operatorname{Var}(I)=\frac{2464129395}{1024}\approx 2406376.3623.}$$
Die C++-Version enthält eine explizite Validierung. Die Statistik von \(C\) wird auf zwei voneinander unabhängigen Wegen berechnet:
Zum einen über die Momentformeln oben. Zum anderen baut brute_one_layer_uniform_count(4, 6) die exakte Verteilung auf, wenn die Würfelanzahl gleichverteilt auf \(\{1,2,3,4\}\) ist. Dazu werden Ein-Würfel-Verteilungen wiederholt gefaltet und anschließend gemittelt. Danach vergleicht das Programm Erwartungswert und Varianz beider Methoden mit enger relativer Toleranz. So wird bestätigt, dass die Rekurrenz die erste nichttriviale Ebene exakt trifft.
Alle drei Implementierungen verwenden denselben Kern. In C++ speichert eine Stats-Struktur das Paar \((\text{mean}, \text{variance})\) als long double, danach folgen vier Aufrufe von transition_sum_of_random_dice. Python und Java führen dieselbe Aktualisierung in kompakter Form aus. Am Ende formatieren alle drei Programme die Varianz mit vier Nachkommastellen, also 2406376.3623.
Der eigentliche Solver braucht nur eine feste Anzahl arithmetischer Operationen. Deshalb gilt \(O(1)\) Zeit und \(O(1)\) Speicher. Auch der optionale C++-Checkpoint bleibt für dieses Problem \(O(1)\), weil er nur den festen kleinen Testfall \((4,6)\) auswertet; er ist ein Verifikationsschritt und nicht der Kernalgorithmus.
Deney, beş platonik zar üzerinden kurulan iç içe rastgele toplamlar zinciridir. Önce 4 yüzlü zar atılır ve sonuç \(T\) olur. Sonra \(T\) adet adil 6 yüzlü zar atılıp toplamları \(C\) olarak tanımlanır. Ardından \(C\) adet 8 yüzlü zarın toplamı \(O\), \(O\) adet 12 yüzlü zarın toplamı \(D\), son olarak da \(D\) adet 20 yüzlü zarın toplamı \(I\) olur. İstenen büyüklük \(\operatorname{Var}(I)\)'dir.
Yerel çözüm dosyaları devasa olasılık dağılımlarını açıkça üretmez. Bunun yerine her katmanda sadece ortalama ile varyansı bir sonraki katmana taşır. Bunun yeterli olmasının nedeni, her aşamanın aynı biçime sahip olmasıdır: bağımsız ve adil zarların rastgele sayıda kopyası toplanır.
\(1,2,\dots,s\) değerlerini alan adil \(s\) yüzlü bir zar \(X_s\) için kod şu formülleri kullanır:
$$\mathbb{E}[X_s]=\frac{s+1}{2},\qquad \operatorname{Var}(X_s)=\frac{s^2-1}{12}.$$
C++, Python ve Java içindeki uniform_die_stats tam olarak bu iki değeri döndürür. İlk zar için
$$T \sim \text{Unif}\{1,2,3,4\},\qquad \mathbb{E}[T]=\frac{5}{2},\qquad \operatorname{Var}(T)=\frac{5}{4}.$$
\(N\) tamsayı değerli bir rassal değişken olsun. Koşullu olarak \(N\) verildiğinde, aynı adil zarın birbirinden bağımsız \(X_1,\dots,X_N\) kopyaları atılsın; bunların ortalaması \(\mu\), varyansı \(\sigma^2\) olsun. Toplamı
$$S=\sum_{j=1}^{N} X_j$$
şeklinde yazalım. \(N\) sabitken
$$\mathbb{E}[S\mid N]=N\mu,\qquad \operatorname{Var}(S\mid N)=N\sigma^2$$
olur. Toplam beklenti ve toplam varyans yasalarıyla
$$\mathbb{E}[S]=\mu\,\mathbb{E}[N],$$
$$\operatorname{Var}(S)=\sigma^2\mathbb{E}[N]+\mu^2\operatorname{Var}(N)$$
elde edilir. C++ içindeki transition_sum_of_random_dice ile Python/Java içindeki transition_sum tam olarak bu iki denklemi uygular.
Mevcut katmanın ortalaması \(m\), varyansı \(v\) olsun ve sıradaki zar \(s\) yüzlü olsun. Şunları tanımlayalım:
$$a_s=\frac{s+1}{2},\qquad b_s=\frac{s^2-1}{12}.$$
Bir sonraki katmanın momentleri
$$m' = a_s\,m,\qquad v' = b_s\,m + a_s^2 v$$
olur. Çözüm, \(T\) için \((m,v)=(5/2,5/4)\) ile başlar ve sonra bu güncellemeyi sırasıyla \(s=6,8,12,20\) için uygular.
6 yüzlü katmanda \(a_6=7/2\) ve \(b_6=35/12\) olduğundan
$$\mathbb{E}[C]=\frac{7}{2}\cdot\frac{5}{2}=\frac{35}{4},$$
$$\operatorname{Var}(C)=\frac{35}{12}\cdot\frac{5}{2}+\left(\frac{7}{2}\right)^2\cdot\frac{5}{4}=\frac{1085}{48}.$$
8 yüzlü katmanda \(a_8=9/2\) ve \(b_8=21/4\):
$$\mathbb{E}[O]=\frac{9}{2}\cdot\frac{35}{4}=\frac{315}{8},$$
$$\operatorname{Var}(O)=\frac{21}{4}\cdot\frac{35}{4}+\left(\frac{9}{2}\right)^2\cdot\frac{1085}{48}=\frac{32235}{64}.$$
12 yüzlü katmanda \(a_{12}=13/2\) ve \(b_{12}=143/12\):
$$\mathbb{E}[D]=\frac{13}{2}\cdot\frac{315}{8}=\frac{4095}{16},$$
$$\operatorname{Var}(D)=\frac{143}{12}\cdot\frac{315}{8}+\left(\frac{13}{2}\right)^2\cdot\frac{32235}{64}=\frac{5567835}{256}.$$
20 yüzlü katmanda \(a_{20}=21/2\) ve \(b_{20}=133/4\):
$$\mathbb{E}[I]=\frac{21}{2}\cdot\frac{4095}{16}=\frac{85995}{32},$$
$$\operatorname{Var}(I)=\frac{133}{4}\cdot\frac{4095}{16}+\left(\frac{21}{2}\right)^2\cdot\frac{5567835}{256}=\frac{2464129395}{1024}.$$
Böylece aranan sonuç
$$\boxed{\operatorname{Var}(I)=\frac{2464129395}{1024}\approx 2406376.3623.}$$
C++ sürümünde açık bir doğrulama adımı vardır. \(C\) değişkeninin istatistikleri iki bağımsız yöntemle hesaplanır:
İlki yukarıdaki moment formülüdür. İkincisi ise brute_one_layer_uniform_count(4, 6) fonksiyonudur; bu fonksiyon zar sayısı \(\{1,2,3,4\}\) üzerinde düzgün dağılmışken tam dağılımı ardışık konvolüsyonlarla kurar. Program sonra ortalama ve varyansı çok sıkı bir göreli toleransla karşılaştırır. Böylece ilk ciddi katmanda kullanılan reküransın gerçekten tam dağılımla uyuştuğu doğrulanır.
Üç dildeki çözüm aynı matematiksel çekirdeği paylaşır. C++ tarafında \((\text{mean}, \text{variance})\) çifti long double kullanan bir Stats yapısında tutulur ve dört kez transition_sum_of_random_dice çağrılır. Python ve Java aynı güncellemeyi daha kısa bir akışla uygular. Üçü de sonunda varyansı dört ondalık basamakla biçimlendirir ve sonuç 2406376.3623 olur.
Asıl çözücü sabit sayıda aritmetik işlem yapar; bu yüzden zaman karmaşıklığı \(O(1)\), bellek kullanımı \(O(1)\)'dir. C++ içindeki isteğe bağlı kontrol de bu problemde \(O(1)\) kalır, çünkü yalnızca sabit küçük \((4,6)\) örneğini dener; ölçeklenen algoritmanın parçası değil, doğrulama mekanizmasıdır.
El experimento es una cadena de sumas aleatorias construida con los cinco dados platónicos. Primero se lanza un dado de 4 caras y se llama \(T\) al resultado. Luego se lanzan \(T\) dados justos de 6 caras y su suma es \(C\). Después se lanzan \(C\) dados de 8 caras para obtener \(O\), luego \(O\) dados de 12 caras para obtener \(D\), y finalmente \(D\) dados de 20 caras para obtener \(I\). Hay que calcular \(\operatorname{Var}(I)\).
Los archivos de solución locales no construyen distribuciones gigantes. En lugar de eso, propagan únicamente la media y la varianza de una capa a la siguiente. Eso basta porque cada etapa tiene exactamente la misma forma: se suma un número aleatorio de dados justos e independientes.
Para un dado justo de \(s\) caras \(X_s\), con valores \(1,2,\dots,s\), el código usa
$$\mathbb{E}[X_s]=\frac{s+1}{2},\qquad \operatorname{Var}(X_s)=\frac{s^2-1}{12}.$$
Eso es exactamente lo que devuelve uniform_die_stats en C++, Python y Java. Para el primer dado tenemos
$$T \sim \text{Unif}\{1,2,3,4\},\qquad \mathbb{E}[T]=\frac{5}{2},\qquad \operatorname{Var}(T)=\frac{5}{4}.$$
Sea \(N\) una variable aleatoria entera. Condicionado a \(N\), lanzamos \(N\) copias independientes \(X_1,\dots,X_N\) del mismo dado justo, cada una con media \(\mu\) y varianza \(\sigma^2\). Definimos
$$S=\sum_{j=1}^{N} X_j.$$
Condicionado a \(N\),
$$\mathbb{E}[S\mid N]=N\mu,\qquad \operatorname{Var}(S\mid N)=N\sigma^2.$$
Aplicando la ley de la esperanza total y la ley de la varianza total, resulta
$$\mathbb{E}[S]=\mu\,\mathbb{E}[N],$$
$$\operatorname{Var}(S)=\sigma^2\mathbb{E}[N]+\mu^2\operatorname{Var}(N).$$
Esta es toda la maquinaria del algoritmo. La función transition_sum_of_random_dice en C++ y transition_sum en Python/Java implementan exactamente estas dos ecuaciones.
Si la etapa actual tiene media \(m\) y varianza \(v\), y el siguiente dado tiene \(s\) caras, definimos
$$a_s=\frac{s+1}{2},\qquad b_s=\frac{s^2-1}{12}.$$
Entonces la etapa siguiente cumple
$$m' = a_s\,m,\qquad v' = b_s\,m + a_s^2 v.$$
La solución parte de \((m,v)=(5/2,5/4)\) para \(T\) y aplica esta actualización con \(s=6,8,12,20\).
En la capa de 6 caras, \(a_6=7/2\) y \(b_6=35/12\). Por tanto
$$\mathbb{E}[C]=\frac{7}{2}\cdot\frac{5}{2}=\frac{35}{4},$$
$$\operatorname{Var}(C)=\frac{35}{12}\cdot\frac{5}{2}+\left(\frac{7}{2}\right)^2\cdot\frac{5}{4}=\frac{1085}{48}.$$
En la capa de 8 caras, \(a_8=9/2\) y \(b_8=21/4\):
$$\mathbb{E}[O]=\frac{9}{2}\cdot\frac{35}{4}=\frac{315}{8},$$
$$\operatorname{Var}(O)=\frac{21}{4}\cdot\frac{35}{4}+\left(\frac{9}{2}\right)^2\cdot\frac{1085}{48}=\frac{32235}{64}.$$
En la capa de 12 caras, \(a_{12}=13/2\) y \(b_{12}=143/12\):
$$\mathbb{E}[D]=\frac{13}{2}\cdot\frac{315}{8}=\frac{4095}{16},$$
$$\operatorname{Var}(D)=\frac{143}{12}\cdot\frac{315}{8}+\left(\frac{13}{2}\right)^2\cdot\frac{32235}{64}=\frac{5567835}{256}.$$
En la capa de 20 caras, \(a_{20}=21/2\) y \(b_{20}=133/4\):
$$\mathbb{E}[I]=\frac{21}{2}\cdot\frac{4095}{16}=\frac{85995}{32},$$
$$\operatorname{Var}(I)=\frac{133}{4}\cdot\frac{4095}{16}+\left(\frac{21}{2}\right)^2\cdot\frac{5567835}{256}=\frac{2464129395}{1024}.$$
Por lo tanto, la respuesta pedida es
$$\boxed{\operatorname{Var}(I)=\frac{2464129395}{1024}\approx 2406376.3623.}$$
La versión en C++ incluye una comprobación explícita. Calcula las estadísticas de \(C\) por dos vías independientes:
La primera usa la fórmula de momentos anterior. La segunda, mediante brute_one_layer_uniform_count(4, 6), construye la distribución completa cuando la cantidad de dados es uniforme en \(\{1,2,3,4\}\), usando convoluciones repetidas de la distribución de un dado. Después compara media y varianza con una tolerancia relativa muy pequeña. Así se confirma que la recurrencia coincide con la distribución exacta en la primera capa no trivial.
Las tres implementaciones comparten el mismo núcleo matemático. C++ guarda el par \((\text{mean}, \text{variance})\) en una estructura Stats con long double y encadena cuatro llamadas a transition_sum_of_random_dice. Python y Java realizan la misma actualización en forma compacta. Las tres versiones formatean finalmente la varianza con cuatro decimales, obteniendo 2406376.3623.
El solucionador real efectúa un número fijo de operaciones aritméticas, por lo que su complejidad temporal es \(O(1)\) y su uso de memoria es \(O(1)\). La comprobación opcional de C++ también permanece en \(O(1)\) para este problema porque está fijada al pequeño caso \((4,6)\); es una validación, no la parte escalable del método.
这个题目是一个分层随机和过程。先掷一个 4 面骰子，结果记为 \(T\)。然后掷 \(T\) 个公平的 6 面骰子，点数总和记为 \(C\)。接着掷 \(C\) 个 8 面骰子得到 \(O\)，再掷 \(O\) 个 12 面骰子得到 \(D\)，最后掷 \(D\) 个 20 面骰子得到 \(I\)。目标是求 \(\operatorname{Var}(I)\)。
本仓库里的解法并没有去构造最后那个极其庞大的完整分布，而是只在每一层传递两个量：均值和方差。之所以可行，是因为每一层都属于同一种模型：掷出一个随机数量的独立公平骰子，然后把点数求和。
对于取值为 \(1,2,\dots,s\) 的公平 \(s\) 面骰子 \(X_s\)，代码使用
$$\mathbb{E}[X_s]=\frac{s+1}{2},\qquad \operatorname{Var}(X_s)=\frac{s^2-1}{12}.$$
C++、Python、Java 中的 uniform_die_stats 都返回这两个量。对第一层的 d4，有
$$T \sim \text{Unif}\{1,2,3,4\},\qquad \mathbb{E}[T]=\frac{5}{2},\qquad \operatorname{Var}(T)=\frac{5}{4}.$$
设 \(N\) 是一个整数值随机变量。给定 \(N\) 之后，掷 \(N\) 个独立同分布的骰子 \(X_1,\dots,X_N\)，每个骰子的均值为 \(\mu\)，方差为 \(\sigma^2\)。记
$$S=\sum_{j=1}^{N} X_j.$$
在 \(N\) 已知时，有
$$\mathbb{E}[S\mid N]=N\mu,\qquad \operatorname{Var}(S\mid N)=N\sigma^2.$$
再用全期望公式与全方差公式，就得到
$$\mathbb{E}[S]=\mu\,\mathbb{E}[N],$$
$$\operatorname{Var}(S)=\sigma^2\mathbb{E}[N]+\mu^2\operatorname{Var}(N).$$
这就是整个算法的核心。C++ 中的 transition_sum_of_random_dice，以及 Python/Java 中的 transition_sum，实现的正是这两条公式。
如果当前层的均值是 \(m\)，方差是 \(v\)，下一层使用 \(s\) 面骰子，那么定义
$$a_s=\frac{s+1}{2},\qquad b_s=\frac{s^2-1}{12}.$$
下一层的统计量就是
$$m' = a_s\,m,\qquad v' = b_s\,m + a_s^2 v.$$
程序从 \(T\) 的 \((m,v)=(5/2,5/4)\) 出发，依次对 \(s=6,8,12,20\) 应用这个更新。
对 6 面骰层，\(a_6=7/2\)，\(b_6=35/12\)，因此
$$\mathbb{E}[C]=\frac{7}{2}\cdot\frac{5}{2}=\frac{35}{4},$$
$$\operatorname{Var}(C)=\frac{35}{12}\cdot\frac{5}{2}+\left(\frac{7}{2}\right)^2\cdot\frac{5}{4}=\frac{1085}{48}.$$
对 8 面骰层，\(a_8=9/2\)，\(b_8=21/4\)：
$$\mathbb{E}[O]=\frac{9}{2}\cdot\frac{35}{4}=\frac{315}{8},$$
$$\operatorname{Var}(O)=\frac{21}{4}\cdot\frac{35}{4}+\left(\frac{9}{2}\right)^2\cdot\frac{1085}{48}=\frac{32235}{64}.$$
对 12 面骰层，\(a_{12}=13/2\)，\(b_{12}=143/12\)：
$$\mathbb{E}[D]=\frac{13}{2}\cdot\frac{315}{8}=\frac{4095}{16},$$
$$\operatorname{Var}(D)=\frac{143}{12}\cdot\frac{315}{8}+\left(\frac{13}{2}\right)^2\cdot\frac{32235}{64}=\frac{5567835}{256}.$$
对 20 面骰层，\(a_{20}=21/2\)，\(b_{20}=133/4\)：
$$\mathbb{E}[I]=\frac{21}{2}\cdot\frac{4095}{16}=\frac{85995}{32},$$
$$\operatorname{Var}(I)=\frac{133}{4}\cdot\frac{4095}{16}+\left(\frac{21}{2}\right)^2\cdot\frac{5567835}{256}=\frac{2464129395}{1024}.$$
因此最终答案是
$$\boxed{\operatorname{Var}(I)=\frac{2464129395}{1024}\approx 2406376.3623.}$$
C++ 版本包含一个显式校验。它用两种互相独立的方法计算 \(C\) 的统计量：
第一种是上面的矩递推公式。第二种是 brute_one_layer_uniform_count(4, 6)，它在骰子数量服从 \(\{1,2,3,4\}\) 上的均匀分布时，通过重复卷积构造完整分布。程序再用很严格的相对误差阈值比较两者的均值和方差。这样就验证了：递推公式不仅直观，而且和第一层的精确分布完全一致。
三个语言版本的核心都一样。C++ 用 Stats 结构保存 \((\text{mean}, \text{variance})\)，数据类型是 long double，然后连续调用四次 transition_sum_of_random_dice。Python 和 Java 也只是按同样的顺序更新这两个量。最后三份代码都把方差格式化为四位小数，所以输出是 2406376.3623。
真正的求解过程只做固定次数的算术运算，因此时间复杂度是 \(O(1)\)，空间复杂度也是 \(O(1)\)。C++ 中可选的检查步骤在本题里也仍然是 \(O(1)\)，因为它只验证固定的小例子 \((4,6)\)；它是校验逻辑，不是主算法的规模瓶颈。
Здесь возникает цепочка случайных сумм, построенная на пяти платоновых костях. Сначала бросается честная кость d4, и результат обозначается через \(T\). Затем бросаются \(T\) честных костей d6, и их сумма обозначается через \(C\). После этого из \(C\) бросков d8 получается \(O\), из \(O\) бросков d12 получается \(D\), а из \(D\) бросков d20 получается \(I\). Нужно найти \(\operatorname{Var}(I)\).
Локальные файлы решения не строят полное распределение финальной величины. Вместо этого они передают от слоя к слою только два момента: математическое ожидание и дисперсию. Этого достаточно, потому что каждая стадия имеет одинаковую структуру: суммируется случайное число независимых честных бросков.
Для честной \(s\)-гранной кости \(X_s\), принимающей значения \(1,2,\dots,s\), код использует формулы
$$\mathbb{E}[X_s]=\frac{s+1}{2},\qquad \operatorname{Var}(X_s)=\frac{s^2-1}{12}.$$
Именно эти значения возвращает функция uniform_die_stats в C++, Python и Java. Для первого броска имеем
$$T \sim \text{Unif}\{1,2,3,4\},\qquad \mathbb{E}[T]=\frac{5}{2},\qquad \operatorname{Var}(T)=\frac{5}{4}.$$
Пусть \(N\) — целочисленная случайная величина. При фиксированном \(N\) бросаются \(N\) независимых одинаково распределенных костей \(X_1,\dots,X_N\) с математическим ожиданием \(\mu\) и дисперсией \(\sigma^2\). Обозначим
$$S=\sum_{j=1}^{N} X_j.$$
Тогда условно по \(N\)
$$\mathbb{E}[S\mid N]=N\mu,\qquad \operatorname{Var}(S\mid N)=N\sigma^2.$$
По формулам полного математического ожидания и полной дисперсии получаем
$$\mathbb{E}[S]=\mu\,\mathbb{E}[N],$$
$$\operatorname{Var}(S)=\sigma^2\mathbb{E}[N]+\mu^2\operatorname{Var}(N).$$
Это и есть весь алгоритм. Функция transition_sum_of_random_dice в C++ и функция transition_sum в Python/Java реализуют ровно эти две формулы.
Если на текущем слое среднее равно \(m\), а дисперсия равна \(v\), и следующая кость имеет \(s\) граней, введем
$$a_s=\frac{s+1}{2},\qquad b_s=\frac{s^2-1}{12}.$$
Тогда для следующего слоя
$$m' = a_s\,m,\qquad v' = b_s\,m + a_s^2 v.$$
Решение стартует с \((m,v)=(5/2,5/4)\) для \(T\), после чего последовательно применяет этот переход для \(s=6,8,12,20\).
Для слоя с d6 имеем \(a_6=7/2\) и \(b_6=35/12\), поэтому
$$\mathbb{E}[C]=\frac{7}{2}\cdot\frac{5}{2}=\frac{35}{4},$$
$$\operatorname{Var}(C)=\frac{35}{12}\cdot\frac{5}{2}+\left(\frac{7}{2}\right)^2\cdot\frac{5}{4}=\frac{1085}{48}.$$
Для слоя с d8, где \(a_8=9/2\) и \(b_8=21/4\):
$$\mathbb{E}[O]=\frac{9}{2}\cdot\frac{35}{4}=\frac{315}{8},$$
$$\operatorname{Var}(O)=\frac{21}{4}\cdot\frac{35}{4}+\left(\frac{9}{2}\right)^2\cdot\frac{1085}{48}=\frac{32235}{64}.$$
Для слоя с d12, где \(a_{12}=13/2\) и \(b_{12}=143/12\):
$$\mathbb{E}[D]=\frac{13}{2}\cdot\frac{315}{8}=\frac{4095}{16},$$
$$\operatorname{Var}(D)=\frac{143}{12}\cdot\frac{315}{8}+\left(\frac{13}{2}\right)^2\cdot\frac{32235}{64}=\frac{5567835}{256}.$$
Для слоя с d20, где \(a_{20}=21/2\) и \(b_{20}=133/4\):
$$\mathbb{E}[I]=\frac{21}{2}\cdot\frac{4095}{16}=\frac{85995}{32},$$
$$\operatorname{Var}(I)=\frac{133}{4}\cdot\frac{4095}{16}+\left(\frac{21}{2}\right)^2\cdot\frac{5567835}{256}=\frac{2464129395}{1024}.$$
Следовательно, ответ равен
$$\boxed{\operatorname{Var}(I)=\frac{2464129395}{1024}\approx 2406376.3623.}$$
В версии на C++ есть явная проверка корректности. Статистика величины \(C\) вычисляется двумя независимыми способами:
Первый способ использует приведенную выше формулу для моментов. Второй способ, реализованный в brute_one_layer_uniform_count(4, 6), строит полное распределение суммы, когда число костей равномерно распределено на \(\{1,2,3,4\}\), с помощью последовательных сверток одношагового распределения. Затем программа сравнивает среднее и дисперсию с очень жесткой относительной точностью. Это подтверждает, что рекуррентная формула совпадает с точным распределением на первом нетривиальном слое.
Во всех трех реализациях математическое ядро одинаково. В C++ пара \((\text{mean}, \text{variance})\) хранится в структуре Stats с типом long double, после чего четыре раза вызывается transition_sum_of_random_dice. Python и Java делают то же обновление в более компактном виде. В конце все три программы форматируют дисперсию до четырех знаков после запятой и получают 2406376.3623.
Основной решатель выполняет фиксированное число арифметических операций, значит его время работы равно \(O(1)\), а потребление памяти тоже \(O(1)\). Необязательная проверка в C++ также остается \(O(1)\) для этой задачи, потому что она зашита на один маленький пример \((4,6)\); это механизм верификации, а не часть масштабируемого решения.
التجربة هنا عبارة عن سلسلة من المجاميع العشوائية المبنية على النردات الأفلاطونية الخمس. نرمي أولًا نردًا عادلًا من 4 أوجه ونسمّي الناتج \(T\). بعد ذلك نرمي \(T\) نردات عادلة من 6 أوجه ويكون مجموعها \(C\). ثم نرمي \(C\) نردات من 8 أوجه فنحصل على \(O\)، ثم \(O\) نردات من 12 وجهًا فنحصل على \(D\)، وأخيرًا \(D\) نردات من 20 وجهًا فنحصل على \(I\). المطلوب هو حساب \(\operatorname{Var}(I)\).
ملفات الحل المحلية لا تبني التوزيع الاحتمالي النهائي الضخم بصورة مباشرة. بدلًا من ذلك فهي تنقل من طبقة إلى الطبقة التالية مقدارين فقط: المتوسط والتباين. وهذا يكفي لأن كل مرحلة لها البنية نفسها: مجموع عدد عشوائي من رميات نرد عادلة ومستقلة.
إذا كان \(X_s\) نردًا عادلًا ذا \(s\) أوجه وقيمه \(1,2,\dots,s\)، فإن الكود يستخدم
$$\mathbb{E}[X_s]=\frac{s+1}{2},\qquad \operatorname{Var}(X_s)=\frac{s^2-1}{12}.$$
وهاتان القيمتان تعيدهما الدالة uniform_die_stats في C++ وPython وJava. بالنسبة إلى أول نرد نحصل على
$$T \sim \text{Unif}\{1,2,3,4\},\qquad \mathbb{E}[T]=\frac{5}{2},\qquad \operatorname{Var}(T)=\frac{5}{4}.$$
لتكن \(N\) متغيرًا عشوائيًا صحيح القيم. وبعد تثبيت \(N\)، نرمي \(N\) نسخًا مستقلة \(X_1,\dots,X_N\) من النرد نفسه، بحيث يكون متوسط كل رمية \(\mu\) وتباينها \(\sigma^2\). نعرّف
$$S=\sum_{j=1}^{N} X_j.$$
عند الشرط على \(N\) نحصل على
$$\mathbb{E}[S\mid N]=N\mu,\qquad \operatorname{Var}(S\mid N)=N\sigma^2.$$
وباستخدام قانون التوقع الكلي وقانون التباين الكلي ينتج
$$\mathbb{E}[S]=\mu\,\mathbb{E}[N],$$
$$\operatorname{Var}(S)=\sigma^2\mathbb{E}[N]+\mu^2\operatorname{Var}(N).$$
وهذا هو لب الخوارزمية بالكامل. فالدالة transition_sum_of_random_dice في C++ والدالة transition_sum في Python وJava تطبقان هاتين المعادلتين حرفيًا.
إذا كانت الطبقة الحالية ذات متوسط \(m\) وتباين \(v\)، وكان النرد التالي ذا \(s\) أوجه، فنعرّف
$$a_s=\frac{s+1}{2},\qquad b_s=\frac{s^2-1}{12}.$$
عندها تصبح إحصاءات الطبقة التالية
$$m' = a_s\,m,\qquad v' = b_s\,m + a_s^2 v.$$
يبدأ الحل من \((m,v)=(5/2,5/4)\) الخاصة بـ \(T\)، ثم يطبق هذا التحديث بالتتابع عند \(s=6,8,12,20\).
في طبقة النرد ذي 6 أوجه لدينا \(a_6=7/2\) و\(b_6=35/12\)، ولذلك
$$\mathbb{E}[C]=\frac{7}{2}\cdot\frac{5}{2}=\frac{35}{4},$$
$$\operatorname{Var}(C)=\frac{35}{12}\cdot\frac{5}{2}+\left(\frac{7}{2}\right)^2\cdot\frac{5}{4}=\frac{1085}{48}.$$
وفي طبقة 8 أوجه، حيث \(a_8=9/2\) و\(b_8=21/4\):
$$\mathbb{E}[O]=\frac{9}{2}\cdot\frac{35}{4}=\frac{315}{8},$$
$$\operatorname{Var}(O)=\frac{21}{4}\cdot\frac{35}{4}+\left(\frac{9}{2}\right)^2\cdot\frac{1085}{48}=\frac{32235}{64}.$$
وفي طبقة 12 وجهًا، حيث \(a_{12}=13/2\) و\(b_{12}=143/12\):
$$\mathbb{E}[D]=\frac{13}{2}\cdot\frac{315}{8}=\frac{4095}{16},$$
$$\operatorname{Var}(D)=\frac{143}{12}\cdot\frac{315}{8}+\left(\frac{13}{2}\right)^2\cdot\frac{32235}{64}=\frac{5567835}{256}.$$
وفي طبقة 20 وجهًا، حيث \(a_{20}=21/2\) و\(b_{20}=133/4\):
$$\mathbb{E}[I]=\frac{21}{2}\cdot\frac{4095}{16}=\frac{85995}{32},$$
$$\operatorname{Var}(I)=\frac{133}{4}\cdot\frac{4095}{16}+\left(\frac{21}{2}\right)^2\cdot\frac{5567835}{256}=\frac{2464129395}{1024}.$$
إذن النتيجة المطلوبة هي
$$\boxed{\operatorname{Var}(I)=\frac{2464129395}{1024}\approx 2406376.3623.}$$
نسخة C++ تحتوي على خطوة تحقق صريحة. فهي تحسب إحصاءات \(C\) بطريقتين مستقلتين:
الطريقة الأولى هي صيغة العزوم السابقة. أما الطريقة الثانية فتستخدم brute_one_layer_uniform_count(4, 6) لبناء التوزيع الكامل عندما يكون عدد النردات موزعًا بانتظام على \(\{1,2,3,4\}\)، وذلك عبر التفاف متكرر لتوزيعات الرمية الواحدة. ثم يقارن البرنامج بين المتوسط والتباين الناتجين باستخدام سماحية نسبية شديدة الصغر. وبهذا يتأكد أن علاقة التحديث توافق التوزيع الدقيق في أول طبقة غير بديهية.
النسخ الثلاث تشترك في الجوهر الرياضي نفسه. في C++ تُخزَّن الثنائية \((\text{mean}, \text{variance})\) داخل بنية Stats باستخدام long double، ثم تُستدعى transition_sum_of_random_dice أربع مرات متتالية. أما Python وJava فتطبقان التحديث نفسه بصورة مختصرة. وفي النهاية تقوم جميع النسخ بتنسيق التباين إلى أربع منازل عشرية، فيظهر الناتج 2406376.3623.
الحل الأساسي ينفذ عددًا ثابتًا من العمليات الحسابية، لذا فزمنه \(O(1)\) وذاكرته \(O(1)\). وحتى فحص التحقق الاختياري في C++ يبقى \(O(1)\) في هذه المسألة، لأنه محصور في الحالة الصغيرة الثابتة \((4,6)\)؛ فهو أداة تحقق وليس الجزء القابل للتوسع من الخوارزمية.