概要

公式解説と同じく、求める期待値を \(f(N)\) とします。 また、問題における操作\(2\)つを順に操作A、操作Bと呼びます。

元の問題に対して素直に立式すると以下のとおりになります。

\[ f(N) = \min \left( X + f \left( \left\lfloor \frac{N}{A} \right\rfloor \right), Y + \frac{1}{6} \sum_{i = 1}^6 f \left( \left\lfloor \frac{N}{i} \right\rfloor \right) \right). \]

公式解説では少し曖昧になっていますが、\(\min\)があるため、公式解説のような単純な式変形では右辺から\(f(N)\)を削除することができません。

そこで、以下の\(2\)種類の操作に置き換えて考えてみましょう。 これによって、公式解説と同じ式を立てられます（後述）。

• \(X\) 円払う。\(N\) を \(\left\lfloor N / A \right\rfloor\) に置き換える。（そのまま）
• 「 \(Y\) 円払い、\(1\) 以上 \(6\) 以下の整数が等確率で出るサイコロを振る。」を \(2\) 以上の整数が出るまで繰り返す。 その \(2\) 以上の出目を \(b\) としたとき、\(N\) を \(\left\lfloor N / b \right\rfloor\) に置き換える。

\(N\)に対して操作Bが期待値を最小化する最適な操作であるとき、操作Bを行って\(1\)の目が出たあと操作Aをしても得はしません。したがって上記のとおり操作を置き換えても、期待値は元の問題から変わりません。

後者の操作の期待値

後者の期待値については、以下のように考えることで立式できます。

\(2\)以上の目が出るまでに支払う金額の期待値

\(i \geq 1\) 回以上サイコロを振る確率、すなわち \(i\) 回目も \(Y\) 円払ってサイコロを振る確率は、\((1/6)^{i-1}\) です。 したがって支払う金額の期待値は以下のとおりです。

\[ \sum_{i = 1}^{\infty} Y \cdot \left( \frac{1}{6} \right)^{i-1} = \frac{6}{5} Y. \]

参考: 無限等比級数の収束，発散の条件と証明など | 高校数学の美しい物語

\(2\)以上の目が出たあとの期待値

それぞれ \(1/5\) の確率で、 \(\lfloor N / 2 \rfloor, \lfloor N / 3 \rfloor, \lfloor N / 4 \rfloor, \lfloor N / 5 \rfloor, \lfloor N / 6 \rfloor\) のいずれかへ置き換えられます。 すなわち、以下のとおりです。

\[ \frac{1}{5} \cdot f \left(\left\lfloor \frac{N}{2} \right\rfloor \right) + \frac{1}{5} \cdot f \left(\left\lfloor \frac{N}{3} \right\rfloor \right) + \frac{1}{5} \cdot f \left(\left\lfloor \frac{N}{4} \right\rfloor \right) + \frac{1}{5} \cdot f \left(\left\lfloor \frac{N}{5} \right\rfloor \right) + \frac{1}{5} \cdot f \left(\left\lfloor \frac{N}{6} \right\rfloor \right). \]

以上の\(2\)つを合計すると、公式解説の式における \(\min\) の中身の\(2\)つ目と一致します。