4択10問テストの正解探索回数＝最大16回（破られた）
本日twitter上でエンジニアの間で話題になった問題。
4択問題10問のテストを全部埋めて提出すると正解数がわかります。 何回提出すればすべての正解を知ることができますか。
10問すべての正解は、最大16回の試行で知ることができます。
（2014-06-20追記：これは算数の範囲内での答なのですが、算数の範囲内でもさらに改善できました。14手です。 http://cs.hatenablog.jp/entry/2014/06/20/132605 ）
まず、回答の分布がわからない場合の最大 = 21回
1問目の正解を知るためには最大何回試行する必要があるでしょう。
AAAAAAAAAA BAAAAAAAAA CAAAAAAAAA DAAAAAAAAA
の4回必要だと思いますか？ いえ、3回で十分です。
AAAAAAAAAA BAAAAAAAAA CAAAAAAAAA
この3回の正解数が同じだった時点で、1問目の正解はDで決定ですから。
さて次、2問目です。1問目の正解を*で表すとして
*AAAAAAAAA *BAAAAAAAA *CAAAAAAAA
の3回必要だと思いますか？ いえ、
*BAAAAAAAA *CAAAAAAAA
の2回で十分です。だって、*AAAAAAAAAはもう試行済みですものね。たしかにDAAAAAAAAAはスキップしましたが、これの点数は試行しなくてもわかります（問1の正解がDだったなら、他の試行結果に1足すだけです）。
同様にして2問目以降は2回ずつ試行すれば十分。
3 + 2 * 9 = 21（回）が最大の試行回数となります。
回答の分布がわかると試行回数が減らせる
問1では最大3回、問2以降では最大2回、試行する必要があったのですが、試行の最初か2番目で正解に当たれば続きを省略できます。
例えば問1、正解がAかBかであれば、
AAAAAAAAAA BAAAAAAAAA
の時点で決定できます。問2以降であれば
*BAAAAAAAA
の時点で決定できます。
つまり最初に出した21回という数字は、正解がAかBかである問の数だけ試行回数が減るわけです。
では、先に正解の分布を知って、正解の多い選択肢を優先で試行していくようにしてみましょう。最初に3回、
AAAAAAAAAA BBBBBBBBBB CCCCCCCCCC
と試行すれば各選択肢の正解数がわかります。DDDDDDDDDDを調べる必要はありませんね。上記3つの和を10から引けばわかります。
最悪のケース、正解が均等に散っていた場合、各選択肢の正解数は3,3,2,2個ですから、上位2選択肢の合計は6個。
つまり最悪でも試行を6回減らせます。先に3回の試行をしておくことで6回減らせることが保証できたのだから3回分得しました。
さらに、AAAAAAAAAAをしてしまったので問1の試行がすでに一つ消化されています。-1。
そして、問10を試行する必要がもはやありません。問9までの全正解がわかっていれば各選択肢の正解数から問10の正解はわかります。-1。
あわせると、21 - 3 - 1 - 1 = 16（回）の試行で全正解を知ることができたことになります。
これで最小？
15回以下で求まらないのか証明したわけではないのでもっと減らせるかも。
