ちょまど問題への素朴な解答(21回の場合)

参照

何回で満点とれる?【ちょまど問題に挑む人々】

http://togetter.com/li/682030

問題

4択の問題(正解はそのうち1個)が10問出題される。解答は10問すべてに答えて提出しなければならない。提出するたびに、10問のうち何問正解だったかという数だけを教師は教えてくれる。全問正解の解答が判明するまでに、少なくとも何回提出する必要があるか。

手順例

以下では4択を(1),(2),(3),(4)と表現する。

手順1. 全問すべて(1)で提出する。この回をベースとする。nを1とする。
手順2. ベースのn問目の解答を(2)に変更して提出する。正解数が減ったならn問目の正解は(1)である(正解確定)。正解数が増えたなら正解は(2)である(正解確定)。変わらなければ正解は(3)か(4)である(正解未確定)。正解確定したならば手順3を飛ばして手順4へ進む。
手順3. n問目の正解は未確定である。ベースのn問目の解答を(3)に変更して提出する。正解数が増えたら正解は(3)である(正解確定)。正解数が変わらなかったら正解は(4)である(正解確定)。正解数が減ることはない。
手順4. n問目の正解は確定している。nが10であれば、ここまでで全問の正解は確定しているので終了する。nが10未満ならばnを1増やして手順2に戻る。

提出数

手順1で1回提出する。手順2と3で最悪2回提出するのを10回繰り返すから最悪で20回提出する。

以上より、少なくとも21回あれば全問正解の解答を確定できる。

真の問題

下限は?


いただいたサポートは、本やコンピュータを買い、さまざまなWebサービスに触れ、結城が知見を深める費用として感謝しつつ使わせていただきます! アマゾンに書評を書いてくださるのも大きなサポートになりますので、よろしくお願いします。 https://amzn.to/2GRquOl