

次のようなゲームを考えます。

アルファベット 'A'~'Z'を全体集合とし、その部分集合が一つ与えられているとします。これを答えと呼びます。  
プレイヤーは1ターンにつき次の問い合わせを一回出来ます。

問い合わせ：アルファベット'A'~'Z'の集合を一つ入力とし、答えと入力の積集合が空集合であるか否かがYes/Noで返ってくる。

これで答えが確定するまでのターン数を競います。

プレイヤーの最善戦略はどのようなものになるでしょうか？  
またプレイヤーが最善戦略をとった時の最悪のターン数は何ターンでしょうか？

なお、ターン数の平均値が最も低い戦略を最善の戦略と呼ぶことにします。


CC BY-SA 4.0
2021-03-18T03:32:11.143
74735
2021-03-25T00:55:40.007
2021-03-18T04:00:22.910
3060
18637
question
アルゴリズム
集合当てクイズの解法


アルファベット何個が含まれているかは任意であるなら解は `2**26`
通りで、なおかつこの条件だと順序付けが困難なので二分法による探索ができない、ということになります。だからプレイヤー側の最善戦略っつか唯一の戦略は１文字づつ総当たり探索する、つまり

  * 部分集合 'A' に対してクエリする ... 'A' が含まれているかがわかる
  * 部分集合 'B' に対してクエリする ... 'B' が含まれているかがわかる
  * 部分集合 'Z' に対してクエリする ... 'Z' が含まれているかがわかる

で 26 回のクエリで正解に達することができる（最悪＝最善＝平均）でしょう。

* * *

正解に含まれている文字が任意個数である以上、１文字でないクエリをすると（例えば `AB` と `AC` と `ADE` )
これらすべての結果が「含まれている」である場合 `A` が含まれているか否かは不明なわけです。であれば２文字以上のクエリを行うことは無駄であると導けます。


CC BY-SA 4.0
2021-03-18T04:18:38.003
74737
2021-03-18T07:45:16.693
2021-03-18T07:45:16.693
8589
8589
74735
answer


一応自分なりの結論としては、一文字づつ調べるのが最善です。

初期状態として解の候補が2**26あります。  
そして問い合わせをするたびにyes/noが返ってくるのでその実行過程は2分木としてあらわされます。  
そして解の候補が1つになった時に葉となります。

2分木の最も効率の良いのは完全2分木ですが、一文字づつ調べる戦略はまさに完全2分木になります。  
よって一文字づづ調べるのが最善と思われます。


CC BY-SA 4.0
2021-03-25T00:55:40.007
74870
2021-03-25T00:55:40.007
18637
74735
answer