ちょまど問題という４選択肢10問の問題を考える(TokusiN法 13手)

ちょまど問題という４選択肢10問の問題がTwitterで流れてきていろいろ盛り上がっていました。

この問題というのは、数学、プログラミング系の問題で
・４選択肢の問題が10問与えられる
・考えても答はわからない
・回答するとが何問正解したかが返される
・回答する時は全部の問題で答を選択しないといけない
・全問の正解がわかるまでに何回の回答が必要か
・全問の正解がわかった後の最後の回答（全問正解で提出）は数に含めない
というものです。

中でもこれが気に入りました。






10問を5問ずつの２つに分ける方法で13手でいけるようです。

やり方を詳しく見ていきます。

まずは「５問ごとの答分布」を調べます。

「５問ごとの答分布」というのは、次の8つが求まることです。
A1 : 前半の5問のうち、答が１の問題の個数
A2 : 前半の5問のうち、答が２の問題の個数
A3 : 前半の5問のうち、答が３の問題の個数
A4 : 前半の5問のうち、答が４の問題の個数
B1 : 後半の5問のうち、答が１の問題の個数
B2 : 後半の5問のうち、答が２の問題の個数
B3 : 後半の5問のうち、答が３の問題の個数
B4 : 後半の5問のうち、答が４の問題の個数

手順１から手順５を行います。
手順１(11111 11111)
手順２(22222 11111)
手順３(33333 11111)
手順４(44444 22222)
手順５(44444 33333)

１つずつ見ていくと
手順1(11111 11111)により
A1 + B1 がわかります。

手順2(22222 11111)により
A2 + B1 がわかります。
A2 - A1 も求められます。

手順3(33333 11111)により
A3 + B1 がわかります。
A3 - A2 も求められます。

ここで
A2 - A1
A3 - A2
がわかったことにより前半の答の分布をある程度予想できます。

例えば
A2 - A1 が3
A3 - A2 が-2
のときは

A1
A2◯◯◯
A3◯

です。答の数が前半５問で６以上にならないことも条件なのでこれしかありません。

ところが１つに決まらない場合もあります。例えば
A2 - A1 が2
A3 - A2 が-2
のときは

A1◯
A2◯◯◯
A3◯

A1
A2◯◯
A3

の２つが予想できます。

予想が３通りになる場合は無いです。

とりあえずこの段階で
A1 A2 A3の組み合わせが１通りまたは２通りに絞れました。

またA4は
A1 + A2 +A3 + A4 = 5
より求められますが、A1が２通り考えられる場合、A4も２通りになります。
上の例だと

A1◯
A2◯◯◯
A3◯
A4

または

A1
A2◯◯
A3
A4◯◯◯

となります。また、A4の２つの値の差は3になります。

次に手順４(44444 22222)により
A4 + B2 がわかります。

次に手順５(44444 33333)により
A4 + B3 がわかります。

ここで先ほどと同じように後半部分の答の分布を考えたいのですが、その前に前半部分が２通りある場合どちらなのかを確定させます。
それには B2 + B3 を求めます。この値が取りうる範囲は0〜５です。

B2 + B3
= (手順４の結果 - A4) + (手順５の結果 - A4)
= (手順４の結果 + 手順５の結果) - (2 × A4)

これに２通りのA4をそれぞれ当てはめます。
A4は正しくない方を選択した時に正しい値より3大きくなるか小さくなります。その結果 2 × A4 は6ずれた値になり、B2 + B3 は0〜5の範囲を外れます。
正しい値なら0〜5の範囲になります。これによりA4およびA1〜A3が確定します。

あとは
A1 + B1
A4 + B2
A4 + B3
の値が分かっていることにより B1〜B3 も確定し、
B1 + B2 + B3 + B4 = 5 よりB4も確定します。

A1〜B4まで全部確定しました。
次に進みます。

引用したツイートでは省かれていますが、ここで前半、後半それぞれを答数の多い順に並べます。

A1 B1
A2 B2
A3 B3
A4 B4

を答数の多い順にして

C1 D1　多
C2 D2
C3 D3
C4 D4　少

とします。名前もABからCDに変えました。数字も答数の多い方から順に付けられています。
例えば

A1 1
A2 1
A3 3
A4 0

の場合、

C1 3
C2 1
C3 1
C4 0

となります。以降、C1やC2の数字は答が1とか2とかではなく、答数の順番になります。ABとCDの対応表（C1はもともとA3の値であることなど）をどこかに記録しておきます。

それぞれの取りうる範囲は、
C1は2〜5
C2は0〜2
C3は0〜1
C4は0〜1
後半も同様です。

次に
手順６(11112 11112)
手順７(11112 11121)
手順８(11112 11211)
手順９(11112 12111)
を実行します。ここでの数字の1や2も答数の順番（多い方から1,2,3,4）を表しています。

手順６の実行前の時点で(11111 11111)の値はすでにわかっていますが、(11112 11111)の値はわかっていません。それでもこれをベースにして手順６から９を実行します。ここで何がわかるかというと、後半グループでどれが1で、どれが2で、どれが「3か4」であるかです。手順６から手順９の値の増減よりこれらを確定させます。(11112 11111)の値も確定させます。

結構複雑なことをやっています。
１０問目から７問目の選択を順番に２にしています。２にしたの問題の正しい答が何であるかによって結果はどう変わるかというと
答が１のとき(11112 11111)より1小さい値になります(-1)。
答が２のとき(11112 11111)より1大きい値になります(+1)。
答が３か４のとき(11112 11111)と同じ値になります(0)。
この考え方を使います。

D1による場合分けを行います。

D1が5のとき
手順６から手順９は同じ値になります。その値は(11112 11111)の値-1。（まあ全部やる必要はないですが）

D1が4のとき
２が答の問題が７問目から１０問目の中にあるか、６問目かによって場合分けされます。
手順６から手順９の結果が同じとき、６問目の答が2、その他は１。その値は(11112 11111)の値-1、
手順６から手順９の結果がどれか一つが大きいとき、そこの答が２です。その他は１。小さい方の値は(11112 11111)の値-1。

D1が３か２のとき
手順６から手順９の結果は７問目から１０問目の答の分布によってこうなります。
答２があり、答３か４もあるとき、結果は３パターン(+1,0,-1)
答２があるが、答３か４はないとき、結果は２パターン(+1,-1)
答２がないが、答３か４はあるとき、結果は２パターン(0,-1)
答２も答３か４もない場合はありません。D1が3以下なので、D2〜D4は全部で2以上だからです。

結果が小さい(-1)ときに2を選択している問題の答が１。数がD1に足りないときは問６の答も１。
結果が大きい(+1)ときに2を選択している問題の答が２。D2に足りないなら問６も答が２。
結果が真ん中(0)のものは答が3か４。問６が決定していないなら問６も3か４。
３つとも小さい方の値は(11112 11111)の値-1。

相対的に大きい値(+1)、小さい値(-1)、真ん中の値(0)を得ることで確定出来ました。(11112 11111)も求めました。

次に進みます。
手順10(11121 11111)
手順12(11211 11111)
手順13(12111 11111)

こちらも同じようにやります。(11111 11111)がわかっているのでこちらは若干簡単になります。説明はほぼ同じなので省略。

これで全ての問題に対して
・答は１
・答は２
・答は３か４
のどれなのかが求められました。

最後です。
答が３あるいは４の問題を決定させます。

手順13 前半、後半それぞれ２問が、3 or 4の2択と分かった場合、その問題に対して(31 34)で、全て確定させる事が出来る
それ以外のパターンの時はこのやり方を単純化したやり方で出来ます。

取りうる範囲は
C3は0〜1
C4は0〜1
です。

C3 0
C4 0
と
C3 1
C4 0
の時は答が決定するので前半グループは終了。後半もそのパターンなら終了。

C3 1
C4 1
の時にはまだわかりません。わかっていない問題が２問あってどちらかが3、どちらかが4です。後半も同じことが言える。

わかっていない問題の数が片方のグループだけ２つ（もう片方は０か１）の時はわかっていない２つに対して(34)を実行すれば
(34)の正解数が０の時、(43)が答になります。
(34)の正解数が２の時、(34)が答になります。

わかっていない問題が前半２つ、後半２つのパターンの時は、その問題に対して(31 34)を実行します。
前半の３が正解の場合、前半の31で正解数が１になります。不正解の場合は０になります。
後半の34が正解の場合、後半の34で正解数が２になります。不正解の場合は０になります。
それより
(31 34)の正解数が０の時、(43 43)が答になります。
(31 34)の正解数が１の時、(34 43)が答になります。
(31 34)の正解数が２の時、(43 34)が答になります。
(31 34)の正解数が３の時、(34 34)が答になります。

これにより全て確定しました。

この他のやり方は、森勢将雅さん(山梨大学)による12手もあります。
http://ml.cs.yamanashi.ac.jp/media/chomado.pdf

また、TokusiNさんは次のようにも述べています。



考えてみてはいかがでしょうか。

コメント

コメントを投稿

このブログの人気の投稿

Swiftのコンパイルエラー寄せ集め

Appleが2014年6月に出してきた新しいプログラミング言語Swiftのコンパイルエラーの収集。こんなプログラムでこんなエラーが出ました、という例をいくつか集めたものです(仕様を読みながらわざとエラーを出したものもかなり含む)。理想を言うならコンパイルの工程を理解した上でそれぞれの説明をしたいのだが、かなり専門的になるのでそこまでは出来ない。 宣言、初期化の実行文 Type annotation missing in pattern 型の指定がない（型がわからない） 【確認ver】Swift 3.0.2【語】annotation 注釈 //Swift 3.0.2 var abc //エラー abcが何の型かわからない。 var abc: Int や var abc = 0 なら型が決まる(推測できる)のでOK。 //Swift 3.0.2 var a, b, c: Int = 0 //エラー Intと=0はcのみに対して適用されるようで、aとbが不確定になる。 var a, b, c: IntならOK。 //Swift 3.0.2 var a, b = 0, c: Int //エラー aに対して、= 0は適用されない（bに対して適用）、Intもaに対して適用されない（間に= 0が適用されたbがあるため？） Cannot assign to value: '***' is a 'let' constant 値を代入できません。***はletで定義された定数です。 【確認ver】Swift 3.0.2【語】assign 割り当てる 値を初期値以外にするならvarで宣言すること。 //Swift 3.0.2 let abc = 0 abc = 1 //エラー //Swift 3.0.2 func funcA(a: Int) { a = 0 //エラー } 関数の引数で与えられたものを関数内で変更しようとした。関数の引数はデフォルトで定数扱い。関数内で変数として使いたいなら関数の頭でvar a = aなどとして書き換え可能にする。 Cannot assign to value: '***' returns immutable value 値を代入できません。***は変更できない
続きを読む

コンパイルエラー覚え書き(Objective-C)

((赤のほう)) Variable length array declaration can not hava 'static' storage duration メソッド内でstaticで配列を宣言するときに要素数が変数だと出る。 incompatible types in assignment 宣言に*を付け忘れ variable-sized object may not be initialized 宣言に*を付け忘れ expected ';' before '}' token ;忘れ Expected expression before '〜' token '〜'の前がおかしい '〜' undeclared (first use in this function) 宣言忘れ、宣言の位置がおかしい stay '3桁の数字' in program 日本語入力モードでなにか入力した wrong type argument to unary minus メソッドの引数がおかしいという意味 原因はほんとにメソッドの引数がおかしい場合と、すこし上のメソッドの}の閉じカッコ忘れでエラー部分が前のメソッドの一部と認識されている場合がある。 expected specifier-qualifier-list before '****' ２つの.hが互いに#importしあったときなどにおこる。 片方を @class ****; に変更するとエラーが出なくなることがよくある。 @class **** は.hのインポートではなく、ソースの中に「****」というクラスが出てきますが気にしないでください、と言うニュアンス。インポートはどこかでする必要があることがほとんどと思うが、.mの先頭でしてやればよい。 設計の見直しというのも解決方法のひとつ。 Lvalue required as left operand of assignment 代入可能じゃない(?) Initializer element is not constant int型の変数をstaticで宣言して同時に初
続きを読む

AVAudioSession細かいことまとめ(late 2014)

以前も書きました「AudioSessionの細かいことまとめ」のlate 2014版を書きます。 個人的なあらすじ 以前アプリを作る際に、AudioSession(C言語)とAVAudioSession(Obj-C)のどちらを使おうかと検討したことがありました。そのときはAVAudioSession(Obj-C)の方に機能が足りない部分が多少あって、これは主流にならないのではと思い、AudioSession(C言語)の方で実装しました。しかし予想は外れ、AudioSession(C言語)の方がiOS7より非推奨となったので、今回改めてAVAudioSession(Obj-C)の方でまとめてみます。せっかくなのでSwiftの方も併記して書いてみようと思います。基本的にAVAudioSessionのクラスリファレンスを読んでまとめるだけなので詳しく知りたいことがある場合はそちらを見て下さい。 ちなみに作っているアプリは SilentBonusTrack というカセットテープアプリで、iPodのような音楽再生機能が中心となっています。私の興味の対象はその辺の音楽再生系が中心になります。 重要な項目 まずは音を扱う場合には目を通しておく必要があるAudioSession関係です。 importするもの //Swift import AVFoundation //Objective-C #import <AVFoundation/AVFoundation.h> インスタンスの取得 このインスタンスに対して音の扱いに関するいろいろなメソッドを実行出来ます。 //Swift let session: AVAudioSession = AVAudioSession.sharedInstance() //Objective-C AVAudioSession *audioSession = [AVAudioSession sharedInstance]; Swiftの方はもしvarにする必要があればvarにしてください。 カテゴリーの指定 アプリの音の扱い方法を数パターンの中から選んで指定します。 //Swift var error: NSError? session.setCategory(AVAudioSessionCategoryPlayba
続きを読む