東京大学後期 2005年第2問 (解答解説)

枚のカードにからまでの数がつづつ書かれている．これらのカードを用いた次のようなゲームを考える．を自然数とする．このゲームは最大ラウンドからなり，第一ラウンドから始まる．各ラウンドで，プレーヤーは，枚のカードから枚のカードを抜き出し，その数をみてから，「停止」または「続行」のいずれかを選択する．「停止」を選択した場合は，そのラウンドでゲームは終了し，最後に抜き出したカードに書かれた数が特典となる．「続行」を選択した場合は，抜き出したカードをもとに戻して，次のラウンドを実行する．最終ラウンドでは，「停止」しか選択できず，そのラウンドで抜きただしたカードに書かれた数が得点となる．ただし，各ラウンドで，どのカードも等しい確率で抜き出されるものとする．

抜き出したカードに書かれた数によって「停止」または「続行」を選択する規則を，そのラウンドにおける戦略という．戦略はラウンドごとに，またはの値をとる関数によって，ならば「続行」，ならば「停止」と定める．

はを満たす自然数とする．関数を

とする．最終ラウンドを除く全てのラウンドで，によって定まる戦略を採用した時の得点の期待値を，とで表せ．
ラウンド数がのとき，得点の期待値が最大となるような，第一ラウンドでの戦略を与え，その時の得点の期待値を求めよ．
ラウンド数がのとき，特典の期待値が最大となるような，第一ラウンドおよび第二ラウンドでの戦略をそれぞれ与え，その時の得点の期待値を求めよ．

【解答】

(1)

まずとする．をみたす自然数に対し，第ラウンドまでゲームが続く確率は，回目までをみたすのみがでる確率で，

である．の時はでこの表現で良いので，以下で考える．

したがって，第ラウンドでゲームが終了する時の得点の期待値は

である．

また，第ラウンドでゲームが終了する時の期待値は，

である．

ゲーム全体の期待値は，期待値の和の公式より各ラウンドでゲームが終了した時の期待値の和であり，

である．

最後にのときの期待値は

であり，(式10)の表現で良い．

以上から，自然数に対して，戦略を取った時の得点の期待値は

である．(答)

（2）まず最初に，以下の補題を示す．

補題

得点の期待値を最大にする戦略は(1)の形の関数で与えられる．

証明

とし，

だと仮定する．
この戦略をとるラウンドを $p\, (1 \le p \le r-1)$ とする．
このラウンドでの得点の期待値$E_p$は, $n$ に無関係な定数

　ラウンドが実施される確率
　以外を引いてゲームが終了する時の1ターンの期待値

を用いて

と表される．一方で

だとすると同様に

であり，$E'_n>E_n$が成り立つ．また，この変更によって$p$ラウンド以外への影響はない．
したがって, $f(1), f(2), \dots, f(10)$ を書き下した時， "1,0" という配列があればそれを入れかえることにより期待値を大きくできる．
これをくり返すことによって, 「補題」は示された．

□

「補題」と（1）から，の時の期待値の最大値は

の形で与えられる．従ってこの最大値はの時のである．

戦 略 期 待 値

(答)

(3)

第一ラウンドで，第二ラウンドでを採用するとする．（2）より，第二ラウンドでは最適解を採用する．この時のゲーム全体の期待値は第一ラウンドでゲームが終了する時の期待値と， (2)での期待値を用いて

である．ただしは(式3)で与えられていることを用いた．

について整理して，

である．これを最大にするはで, この時である．よって

戦略　第一ラウンドで , 第二ラウンドで
期待値

である．(答)

この問題のOpen Issue（1件）

東京大学後期 2005年第2問 (解答解説)

【解答】

(1)

(3)

【解説】