プロジェクトオイラー389. ~Platonic Dice

No. 389 Platonic Dice

Project Euler です．

前に一度あきらめていた問題がようやく解けたので，書きます．

確率の問題です．

問題．

考え方とプログラム例．(Python3)

まず，一般的な話として，次のような問題を考えます．

\(X\) の平均と分散は定義から
\begin{align*}
E(X) &= \sum_{i=1}^N p_in_i\\
V(X) &= \sum_{i=1}^N p_in_i^2
\end{align*}
であることを確認しておきます．
さて，\(X=n_i\) であるとき，\(n_i\) 個のサイコロを投げて出る目の組
\begin{align*}
(\overbrace{1, 1, \ldots, 1, 1}^{n_i個})\\
(1, 1, \ldots, 1, 2)\\
\vdots\quad\quad\quad\\
(1, 1, \ldots, 1, m)\\
(1, 1, \ldots, 2, 1)\\
\vdots\quad\quad\quad\\
(m, m, \ldots, m)
\end{align*}
はそれぞれ確率 \(1/m^{n_i}\) であることに注意して，\(Y\) の平均と分散を求めていきます．途中の計算が大変ですが，次のようになります．
\begin{align*}
E(Y) &= \sum_{i=1}^N p_i\times\dfrac{1}{m^{n_i}} \times\left\{\sum_{m_1=1}^m\sum_{m_2=1}^m\cdots\sum_{m_{n_i}=1}^m(m_1+m_2+\cdots+m_{n_i})\right\}\\
&= \sum_{i=1}^N p_i\times\dfrac{1}{m^{n_i}} \times n_im^{n_i-1}\times \dfrac{1}{2}m(m+1)\\
&= \dfrac{m+1}{2}\sum_{i=1}^N p_in_i\\
&= \dfrac{m+1}{2}E(X).
\end{align*}
同様に，
\begin{align*}
E(Y^2) &= \sum_{i=1}^N p_i\times\dfrac{1}{m^{n_i}} \times\left\{\sum_{m_1=1}^m\sum_{m_2=1}^m\cdots\sum_{m_{n_i}=1}^m(m_1+m_2+\cdots+m_{n_i})^2\right\}\\
&= \sum_{i=1}^N p_i\times\dfrac{1}{m^{n_i}} \\
&\quad \quad \times\left\{\sum_{m_1=1}^m\sum_{m_2=1}^m\cdots\sum_{m_{n_i}=1}^m\left(m_1^2+m_2^2+\cdots+m_{n_i}^2+2\sum_{1\leq j\leq k\leq n_i}m_jm_k\right)\right\}\\
&= \sum_{i=1}^N p_i\times \dfrac{1}{m^{n_i}}\times n_im^{n_i-1}\times \dfrac{1}{6}m(m+1)(2m+1)\\
&\quad\quad+\sum_{i=1}^N p_i\times \dfrac{1}{m^{n_i}}\times2m^{n_i-2}\times \left(\dfrac{1}{2}m(m+1)\right)^2\times \binom{n_i}{2}\\
&= \dfrac{1}{6}(m+1)(2m+1)\sum_{i=1}^N p_in_i+\dfrac{1}{4}(m+1)^2\sum_{i=1}^N p_i(n_i^2-n_i)\\
&= \dfrac{1}{12}(m+1)(m-1)E(X)+\dfrac{1}{4}(m+1)^2E(X^2)
\end{align*}
よって，\(Y\) の分散は次のように \(X\) の平均と分散を用いて表すことができます．

\begin{align*}
V(Y) &= E(Y^2)-E(Y)^2\\
&= \dfrac{1}{12}(m+1)(m-1)E(X)+\dfrac{1}{4}(m+1)^2V(X).
\end{align*}

これで，平均や分散を数式で書けたので，\(T, C, O, D, I\) の平均，分散を順番に求めていけばいいです．