ちょまど問題という4選択肢10問の問題を考える(TokusiN法 13手)
ちょまど問題という4選択肢10問の問題がTwitterで流れてきていろいろ盛り上がっていました。 この問題というのは、数学、プログラミング系の問題で ・4選択肢の問題が10問与えられる ・考えても答はわからない ・回答するとが何問正解したかが返される ・回答する時は全部の問題で答を選択しないといけない ・全問の正解がわかるまでに何回の回答が必要か ・全問の正解がわかった後の最後の回答(全問正解で提出)は数に含めない というものです。 中でもこれが気に入りました。 ちょまど問題の13手で確定させるアルゴリズム。 11111 11111 11111 22222 11111 33333 22222 44444 33333 44444 の5回をとりあえず試す。前半5問と後半5問それぞれに対して1~4の回答分布が確定できる — TokusiN (@toku51n) 2014, 6月 20 ワーストケースは回答分布が両方2111になった時。両方とも1が2問だったとする。 11112 11112 11112 11121 11112 11211 11112 12111 の4回で、後半5問のどれが1で、どれが2で、どれが「3か4」であるかが確定する。 — TokusiN (@toku51n) 2014, 6月 20 11121 11111 11211 11111 12111 11111 で、前半も同じ事が確定する。 4,5,9,10問目が3 or 4の2択と分かった場合、 11131 11134で、全て確定させる事が出来る。 — TokusiN (@toku51n) 2014, 6月 20 10問を5問ずつの2つに分ける方法で13手でいけるようです。 やり方を詳しく見ていきます。 まずは「5問ごとの答分布」を調べます。 「5問ごとの答分布」というのは、次の8つが求まることです。 A1 : 前半の5問のうち、答が1の問題の個数 A2 : 前半の5問のうち、答が2の問題の個数 A3 : 前半の5問のうち、答が3の問題の個数 A4 : 前半の5問のうち、答が4の問題の個数 B1 : 後半の5問のうち、答が1の問題の個数 B2 : 後半の5問のうち、答が2の問題の個数 B3 : 後半の5問のうち、答が3の問題の個数 B4 : 後...