ちょまど問題（１２手） Version ３ 森勢将雅（山梨大学） ちょまど問題とは •４択の問題が１０問（全て正答は不明） •解答者は１０問同時に提出し「正答数」の みがフィードバック •１０問すべての回答を得るための「最少提 出回数」は？ •執筆者の直感では「１１回」 •ヒット・アンド・ブロー（マスターマイン ド）と似ている（性質は異なる） 1 予備知識：問題数が１の場合 パターンA パターンB ○ 1 ○ 2 3 パターンC 4 パターンD ○ ○ •パターンA, B, Cは「1, 2, 3」と順番に提出するこ とで確定（３手） •パターンDも「1, 2, 3」が不正解ならば自動的に ４で確定する（３手） これを「メソッド１」と定義 2 メソッド１の拡張（問題数10） •初手は「全て１」で提出（１手） •(1) １問目を2にして提出 – ＋１ならば１問目は2で確定 – －1ならば２問目は１で確定 •(2)正答数が±０ならば3にして提出 – ＋１ならば１問目は３で確定 – ±０ならば１問目は４で確定 •以下(1), (2)を問題数10まで繰り返す 初手＋2×１０＝２１手 ※結城先生の回答と同一です．以下からの引用 https://note.mu/hyuki/n/n7b3e0c44aedf 3 問題数2の解法のコンセプト •結城先生方式であれば問題数２は5回 – 1問×2で解く考え •ここでは，2問の全パターンを探索し，最 少回数が5以下となるメソッド2を提案 •初手は(1, 1)で確定し2手目以降を示す ○ ○ この場合正解は(1, 2)と定義 4 問題数２の場合の解法 ○ ○ ○ ○ ○ ○ ○ ○ 以上４つは(2, 2)→(3, 3)の３手で確定 5 問題数２の場合の解法 ○ •２手(2, 2) ○ ○ ○ – 正答数が±0 •３手(3, 3) – 正答数が－1 •４手(1, 2) ２手目，３手目で正答数の変動が ±０→－１のパターンは上記２パ ターンのみ – 正答数が＋２なら(1, 2)が正解 – 正答数が±０なら(2, 1)が正解 4手で確定 6 問題数２の場合の解法 ○ •２手(2, 2) ○ ○ ○ – 正答数が＋１ •３手(3, 3) – 正答数が±0 •４手(2, 3) ２手目，３手目で正答数の変動が ＋１→±０のパターンは上記２パ ターンのみ – 正答数が＋1なら(2, 3)が正解 – 正答数が－1なら(3, 2)が正解 4手で確定 7 問題数２の場合の解法 ○ •２手(2, 2) ○ ○ ○ – 正答数が±0 •３手(3, 3) – 正答数が＋1 •４手(3, 4) ２手目，３手目で正答数の変動が ±０→＋１のパターンは上記２パ ターンのみ – 正答数が＋1なら(3, 4)が正解 – 正答数が－1なら(4, 3)が正解 4手で確定 8 問題数２の場合の解法 ○ •２手(2, 2) ○ ○ ○ – 正答数が－1 •３手(3, 3) – 正答数が＋1 •４手(1, 3) ２手目，３手目で正答数の変動が －１→＋１のパターンは上記２パ ターンのみ – 正答数が＋1なら(1, 3)が正解 – 正答数が－１なら(3, 1)が正解 4手で確定 9 問題数２の場合の解法 ○ •２手(2, 2) ○ ○ ○ – 正答数が＋1 •３手(3, 3) – 正答数が－1 •４手(2, 4) ２手目，３手目で正答数の変動が ＋１→－１のパターンは上記２パ ターンのみ – 正答数が＋2なら(2, 4)が正解 – 正答数が±0なら(4, 2)が正解 4手で確定 10 問題数２の場合の解法 ○ •２手(2, 2) ○ ○ ○ – 正答数が－１ •３手(3, 3) – 正答数が±０ •４手(1, 4) ２手目，３手目で正答数の変動が －１→±０のパターンは上記２パ ターンのみ – 正答数が＋２なら(1, 4)が正解 – 正答数が±０なら(4, 1)が正解 4手で確定 11 メソッド２の拡張 •2問の全パターンを最多4手で確定 •結城先生と同様の考え方を10問の場合に当 てはめると – 初手は全て1 – 2手目以降は2問ずつメソッド2を当てはめる – 2問回答は4手だが初手の1を引くことが可能 初手１＋3手×5ペア＝16手 12 これで終わりか？ •メソッド２を4問（2問×2問）に拡張 – パターン1群は3手なので除外 •メソッド2は3手目の段階で2パターンに分 類可能 •2手目3手目の正答数の変動を – 「0→－1」「＋1→－1」「－1→０」 – 「＋1→0」「0→＋1」「－1→＋1」 •の2グループに分類する． – 前者をグループA，後者をグループB． 13 メソッド３ •前提知識 – グループAの場合は4手目で「＋2 or 0」グル ープBの場合は4手目で「±1」が確定 •メソッド３はこの性質を利用 – 初手(1, 1, 1, 1)から(2, 2, 1, 1), (3, 3, 1, 1) までは固定 – この段階で1, ２問目はグループA, Bのどちら かが確定する 14 ４手目 •４手目は – 問題1, 2はメソッド２の４手目と同様 – 問題3, 4は(2, 2)とする． •パターンAの場合は – ＋2 or 0（問題1, 2）に-2, -1, 0, 1, 2が加算 •パターンBの場合は •±１（問題1, 2）に-2, -1, 0, 1, 2が加算 15 ４手目の結果（パターンA） •＋４の場合 – 問題３，４で＋2が確定するので終了 •＋３の場合 – 問題１，２が＋２，問題３，４で＋１が確定 •－1の場合 – 問題１，２で0，問題３，４で－１が確定 •－２の場合 – 問題１，２で0，問題３，４で－２が確定 16 ４手目の結果（パターンA） •＋２の場合 – 問題1, 2が0，問題3, 4が＋2 – 問題1, 2が＋2，問題3, 4が0のどちらか •5手目で問題3, 4を（3, 3）にして提出 – －2であれば前者で確定 – それ以外であれば後者で確定 17 ４手目の結果（パターンA） •＋１の場合 – 問題１，２で0，問題３，４で＋１ – 問題１，２で2，問題３，４で－１のどちらか •５手目で問題1, 2を4手目の逆((X, Y)なら (Y, X))に，問題3, 4を(3, 3)で提出 – 前者ならば問題１，２は＋２，問題３，４は0 か－１なので，全体では「＋１，＋２」 – 後者ならば問題１，２は－２，問題３，４は 0，＋1なので，全体では「－２，－１」 18 ４手目の結果（パターンA） •±0の場合 – 問題１，２で２，問題３，４で－２ – 問題１，２で０，問題３，４で0の可能性 •５手目で問題1, 2を4手目の逆((X, Y)なら (Y, X))に，問題3, 4を(3, 3)で提出 – 前者ならば問題１，２は－２，問題３，４は0 なので「－2」で確定 – 後者ならば問題１，２は＋２，問題３，４は －1，0，1，2のどれかなので，＋1～4のど れかとなる（続く） 19 ４手目の結果（パターンA） •－2の場合は確定 •それ以外の場合は問題３，４の結果は「０ →結果－2」で確定 4問6手で確定 20 ４手目の結果（パターンB） •変動の候補は－３から＋３まで •－３の場合 – 問題3, 4で－２が確定するので終了 •＋３の場合 – 問題3, 4で＋２が確定するので終了 •－２の場合 – 問題1, 2で－１，問題3, 4で－1が確定 •＋２の場合 – 問題1, 2で＋１，問題3, 4で＋１が確定 21 ４手目の結果（パターンB） •＋１の場合 – 問題1, 2で＋１，問題3, 4で０ – 問題1, 2で－１，問題3, 4で＋２の可能性 •５手目で問題3, 4を(3, 3)で提出 – 前者の場合：－1～2の範囲 – 後者の場合：－2なので分離可能 22 ４手目の結果（パターンB） •－１の場合 – 問題1, 2で－１，問題3, 4で０ – 問題1, 2で＋１，問題3, 4で－２の可能性 •５手目で問題1, 2を4手目の逆((X, Y)なら (Y, X))に，問題3, 4を(3, 3)で提出 – 前者の場合：問題１，２は＋2，問題３，４は －1～2の範囲．全体で＋1～4の範囲． – 後者の場合：問題１，２は－2，問題3，4は0 なので「－2」で確定 23 ４手目の結果（パターンB） •±０の場合 – 問題1, 2で＋１，問題3, 4で－１ – 問題1, 2で－１，問題3, 4で＋１の可能性 •５手目で問題1, 2を4手目の逆((X, Y)なら (Y, X))に，問題3, 4を(3, 3)で提出 – 前者の場合，問題1, 2は－2，問題3, 4は0 or ＋1なので，－2 or －1 – 後者の場合，問題1, 2は＋2，問題3, 4は0 or －1なので，＋2 or ＋1 •（続く） 24 ４手目の結果（パターンB） •続き – 前者の場合，問題1, 2は－2，問題3, 4は0 or ＋1なので，－2 or －1 – 後者の場合，問題1, 2は＋2，問題3, 4は0 or －1なので，＋2 or ＋1 •－２の場合：問題3，４は「－1→０」 •－１の場合：問題3，4は「－1→＋1」 •＋2の場合：問題3，4は「＋1→0」 •＋1の場合：問題3, 4は「＋1→－1」 25 メソッド３の特徴 •問題を２問ずつ分割し，メソッド２を順番 に適用 •前半のメソッド２の４手目と後半のメソッ ド２の２手目を同時に進めることで，後半 の手順を１手削減 •６問の場合も３グループに分割し， •１，２グループのオーバーラップで１手， ２，３グループのオーバーラップで１手， 合計２手得することが可能． 26 結論 •問題数が１０の場合， – ２問のグループが５つあると考える – 「１，２」，「２，３」，「３，４」，「４， ５」それぞれで１手ずつ稼ぐことが可能 •よって，１６手から４手引き１２手で探索 できる 27
© Copyright 2024 ExpyDoc
