「コーホート法」っていうのを使って将来人口推計やりました、高校の研究で(ちょっと久しぶりにやってみたくなった)。
こんにちは。コンちゃんこと佐々木です。
今日は、ちょまどさん問題について考えます。
難しく書くつもりはないので、良かったら皆さん読んでねー。
ちょまど産さん問題とは？
ちょまどさん（twitter/chomado）のツイートを発端にした、数学的なある問題。
ちょまどさんは文系卒の新人女子システムエンジニアらしいこともあり、Twitterによく出没するエンジニア系の人が多くこの問題を考えていたようです。
(本人は周囲のハイレベルなリプライ解答に圧倒されていたようですが、理系の私もとてもハイレベル解答などできなくて同じように圧倒されたので安心してください…？)
※検索時は「さん」を除いて「ちょまど問題」「#ちょまど問題」とすると良いです。
問題（佐々木的まとめ）
__________________________________________________________________________
「今から今日の復習テストをやりまーす。」
「えー」
…
4択問題(選択肢：1,2,3,4)が10問ある。
今、全問の答えを知りたい。
(全問正解するまで居残りなのでさっさと終わらせたいところである)
解答用紙を提出すると、「10問中○問正解」だと教えてくれる。ただしどの問題が正解しているかは分からない。
また、提出は全問解答しないとできない・選択肢以外の解答を書いてはいけない。
全問の答えを知るために必要な、最悪の場合の提出回数を最小化し、その提出(解答)方法を示せ。
(「最悪でも100回提出すれば分かる」「いやこっちのやり方だと最悪でも30回で済むぞ！」→最小化、ってことを言いたい)
__________________________________________________________________________
解く→提出する→正解数を教えてもらう→(全問正解でなければ)再び解く→…という流れ。
さて、考えていきましょう。
なお、「問1の答え：1、問い2の答え：3、…」と書くと長いので、
「1122334412」(左から問1の答え、問2の答え、…)と書くことにします。
・上の問題部分に、4択問題の実際の問題を書いてないけど、これ何のテスト…？プログラミングの知識の問題？一般常識？W杯の各組1位チーム予想？やっぱり地元ブラジルかスp(ry
何でも良いです。
数学的・機械的に解いていくので、どんな問題文だろうと適用できます。
(つまり、問題文を1文字も読まないで解こってことさ！これなら機械にも任せられる！)
・全パターン試そう
1111111111
1111111112
1111111113
1111111114
1111111121
1111111122
1111111123
1111111124
1111111131
…
4444444443
4444444444
みたいな！
これは、何通り？
→4*4*4*4*4*4*4*4*4*4= 4^10 = 1048576通り
…全パターン104万って、こりゃ居残り続けますわ！！
もちろん、これは最悪の場合(答えが4444444444で1111111111から提出してきたとき)ですよ。
ここから、いろいろ工夫していきます。
・正解判明までの最長パターン
解答用紙を提出すると、「10問中○問正解」だと教えてくれるんですよ、これを活かさずにはいられないっ！
今、正解を4444444444として、最初の提出を1111111111として、正解を探していきます。
まず1111111111を提出する → 0/10 (0/10は10問中0問正解の意味)
次に2111111111を提出する → 0/10
次に3111111111を提出する → 0/10
ここまで提出して、1問目の答えが4と確定できましたが、okです！？
1を提出しても、2を提出しても、3を提出しても正解数が変わらないって、これは提出しなくても4が正解だと分かりますね。
ここまでの提出回数合計は、3回です。
次は2問目の正解を探していきます。
次に4211111111を提出する → 1/10
次に4311111111を提出する → 1/10
ここまで提出して、2問目の答えが4だと確定できますね。
ここまでの提出回数合計は、3+2=5回です。
3問目以降の正解は、2問目と同じく探していくと、最終合計提出回数は…
3+2+2+2+2+2+2+2+2+2 = 21回
となりますね！
なお、全問正解判明まで21回なので、最終提出して晴れて帰宅するには22回の提出です。