東京大学 2005年度後期・理系数学後期第2問解答・解説

問題

1から10のカードを毎ラウンド1枚等確率で引き、数を見て停止すればその数が得点、続行ならカードを戻して次へ進む。最大 $r$ ラウンドで、最終ラウンドは必ず停止する。 $f_{k}$ を1から $k$ なら続行、 $k + 1$ から10なら停止する戦略とする。

(1) 最終以外をすべて $f_{k}$ とした期待値を $r, k$ で表せ。

(2) $r = 2$ の最適な第1戦略と期待値を求めよ。

(3) $r = 3$ の最適な第1・第2戦略と期待値を求めよ。

出典：東京大学 2005年度後期日程第2次学力試験後期・理系後期第2問

(1)は各非最終ラウンドへ到達する確率が $(k /10)^{j - 1}$ であることを使い、停止時の得点寄与を等比級数で加える。(2)(3)は後ろのラウンドから最適期待値を求め、目の数が続行価値を上回るときだけ停止する後ろ向きの判断を行う。

非最終ラウンドで続行する確率は $k /10$ である。1回のラウンドで停止して得る得点の無条件の寄与は

\frac{1}{10} x = k + 1 \sum 10 x = \frac{55 - k ( k + 1 ) /2}{10} .

したがって期待値を $E_{r, k}$ とすると

E_{r, k} = \frac{55 - k ( k + 1 ) /2}{10} j = 0 \sum r - 2 (\frac{k}{10})^{j} + \frac{11}{2} (\frac{k}{10})^{r - 1} .

等比級数を整理すると

E_{r, k} = \frac{k + 11}{2} - \frac{k ^{r}}{2 \cdot 1 0 ^{r - 1}} .

最終ラウンドの期待値は

\frac{1 + 2 + \dots + 10}{10} = \frac{11}{2} .

第1ラウンドで $x > 11/2$ なら停止し、 $x < 11/2$ なら続行するのが最適である。よって1から5では続行、6から10では停止する戦略 $f_{5}$ を用いる。その期待値は

\frac{5 \cdot ( 11/2 ) + ( 6 + 7 + 8 + 9 + 10 )}{10} = \frac{27}{4} .

第2ラウンドでは (2)と同じ $f_{5}$ が最適で、そのラウンド以降の期待値は $27/4$ である。第1ラウンドでは $x > 27/4$ のとき停止すべきだから、1から6で続行、7から10で停止する $f_{6}$ が最適である。最大期待値は

\frac{6 \cdot ( 27/4 ) + ( 7 + 8 + 9 + 10 )}{10} = \frac{149}{20} .

したがって第1ラウンドは $f_{6}$ 、第2ラウンドは $f_{5}$ を用いる。