Detailed mathematical approach

Problem Summary

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)\).

Mathematical Approach

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.

Step 1: Moments of One Fair Die

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}.$

Step 2: Random-Sum Identity

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.

Step 3: A Recurrence for Each Layer

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\).

Step 4: Compute \(C\), \(O\), \(D\), and \(I\)

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.}$

Why the Checkpoint in the C++ Code Is Useful

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.

How the Code Works

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.

Complexity Analysis

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.

Footnotes and References

1. Problem page: https://projecteuler.net/problem=389
2. Law of total expectation: Wikipedia — Law of total expectation
3. Law of total variance: Wikipedia — Law of total variance
4. Discrete uniform distribution: Wikipedia — Discrete uniform distribution