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

この記事の所要時間: 529

No. 389 Platonic Dice

Project Euler です.

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

確率の問題です.

問題.

偏りのない4面のサイコロ1個を投げて,出た目を \(T\) として記録する.
\(T\) 個の偏りのない6面のサイコロを投げて,出た目を足し合わせた和を \(C\) として記録する.
\(C\) 個の偏りのない8面のサイコロを投げて,出た目を足し合わせた和を \(O\) として記録する.
\(O\) 個の偏りのない12面のサイコロを投げて,出た目を足し合わせた和を \(D\) として記録する.
\(D\) 個の偏りのない20面のサイコロを投げて,出た目を足し合わせた和を \(I\) として記録する.
このとき,\(I\) の分散を求め,四捨五入して小数第4位まで答えよ.
サイコロの面の数は 4, 6, 8, 12, 20 なので,正多面体ですね.次々に出た目の和の個数のサイコロを投げるので,サイコロの数がどんどん増えていきます.
前にこの問題の出た目の和をプログラムで頑張って求めようとしましたが,計算量が多すぎて解けませんでした.
今回は,数学的な解析によって求めることができました.

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

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

確率変数 \(X\) は,確率 \(p_i\) で値 \(n_i\) をとる(\(i=1, 2, \ldots, N, p_1+p_2+\cdots+p_N=1\)) として,\(X\) 個の偏りのない \(m\) 面のサイコロを投げたときの出た目を足し合わせた和を \(Y\) とします.このとき,\(Y\) の平均(期待値) \(E(Y)\) 及び分散 \(V(Y)\) はどうなるでしょうか.

\(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(X^2)-E(X)^2\\
&= \dfrac{1}{12}(m+1)(m-1)E(X)+\dfrac{1}{4}(m+1)^2V(X).
\end{align*}

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

答えはこの下にあります.

A. 2406376.3623

スポンサーリンク
sub2
sub2
  • このエントリーをはてなブックマークに追加