2012年(平成24年)東京大学後期-総合科目ＩＩ[1]B - [別館]球面倶楽部零八式markIISR

[1] 与えられた状況の中で最適な結果を生み出すための戦略について考える．

B
重さが $1$ ， $2$ ，…， $N$ グラムのいずれかであることがわかっている物体があり，天秤を使ってこの物体の重さ $x$ グラムを決定したい．ここで $N$ は $2$ 以上の整数である．天秤は，1回の計測ごとに，任意に指定した整数値(ただし $1\leqq k\leqq N-1$ )に対して， $x\leqq k$ と $x\geqq k+1$ のどちらが成り立つかだけを判定できる．天秤を用いる回数がなるべく少なくてすむような方法で物体の重さ $x$ を決定したい．

Aさんの方法は，まず $k=1$ として， $x\leqq 1$ であるか $x\geqq 2$ であるかを判定する．もし前者であれば， $x= 1$ となり， $x$ の値が決まる．もし $x\geqq 2$ であれば，次に $k = 2$ として， $x = 2$ であるか $x\geqq 3$ であるかを判定する．このようにして， $k$ の値を一番小さいものから 1 ずつ上げていって，最終的に $x$ を決定するやり方である．

これに対しBさんの方法は，まず全体の中央値 $\dfrac{N+1}{2}$ を超えない最大整数を $k$ として， $x\leqq k$ であるか $x\geqq k+1$ であるかを判定することにより $x$ のとり得る範囲をほぼ半分の幅に狭める．次に，狭めた範囲の中央値を超えない最大整数を $k$ とおいて， $x$ がとり得る範囲をさらにほぼ半分に狭める．以下同様の操作を繰り返して $x$ の範囲を狭めていき，最終的に $x$ を決定するやり方である．

(B-1) Aさんの方法で $x$ を決定するのに必要な天秤の使用回数の最大値を $N$ で表せ．

(B-2) $1\leqq k\leqq N$ を満たすすべての整数に対して， $x = k$ である確率が $\dfrac{1}{N}$ であるとする．このとき，Aさんの方法で $x$ を決定するのに必要な天秤の使用回数の期待値を $N$ で表せ．

(B-3) $N = 2^m$ とする．ただし $m$ は正の整数である．このとき，Bさんの方法で $x$ を決定するのに必要な天秤の使用回数を $m$ で表せ．

次に，AさんやBさんの方法に限らない一般の方法も含めて考えてみよう．ここにいう「方法」とは，天秤を使用する際に指定する整数値 $k$ の選び方を，あらかじめ定めておくやり方を指す．ただし，2回目以降の計測の際には，それ以前の計測による判定結果をふまえて $k$ を定めてよいものとする．

(B-4) $N = 1000$ とし， $x$ は $1$ から $1000$ までの任意の整数値をとり得るとする．このとき，天秤をたかだか9回用いるだけで $x$ を必ず決定できる方法は存在しないことを示せ．

(B-5) $N = 1000$ とする．整数 $k$ に対して， $x =k$ である確率が， $1\leqq k\leqq 200$ のとき $\dfrac{1}{250}$ であり， $201\leqq k\leqq 1000$ のときは $\dfrac{1}{4000}$ であることがわかっているとする．このとき，天秤の使用回数の期待値を9以下にする方法を見いだせ．

2021.02.15記

[解答]