質問: 次のようなゲームを考えます。 アルファベット 'A'~'Z'を全体集合とし、その部分集合が一つ与えられているとします。これを答えと呼びます。 プレイヤーは1ターンにつき次の問い合わせを一回出来ます。 問い合わせ:アルファベット'A'~'Z'の集合を一つ入力とし、答えと入力の積集合が空集合であるか否かがYes/Noで返ってくる。 これで答えが確定するまでのターン数を競います。 プレイヤーの最善戦略はどのようなものになるでしょうか? またプレイヤーが最善戦略をとった時の最悪のターン数は何ターンでしょうか? なお、ターン数の平均値が最も低い戦略を最善の戦略と呼ぶことにします。
回答: 一応自分なりの結論としては、一文字づつ調べるのが最善です。 初期状態として解の候補が2**26あります。 そして問い合わせをするたびにyes/noが返ってくるのでその実行過程は2分木としてあらわされます。 そして解の候補が1つになった時に葉となります。 2分木の最も効率の良いのは完全2分木ですが、一文字づつ調べる戦略はまさに完全2分木になります。 よって一文字づづ調べるのが最善と思われます。