4選択肢10問の問題を考える(TokusiN法 13手)

4選択肢10問の問題がTwitterで流れてきていろいろ盛り上がっていました。

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

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






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 : 後半の5問のうち、答が4の問題の個数

手順1から手順5を行います。
手順1(11111 11111)
手順2(22222 11111)
手順3(33333 11111)
手順4(44444 22222)
手順5(44444 33333)

1つずつ見ていくと
手順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◯

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

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

A1◯
A2◯◯◯
A3◯

A1
A2◯◯
A3

の2つが予想できます。

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

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

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

A1◯
A2◯◯◯
A3◯
A4

または

A1
A2◯◯
A3
A4◯◯◯

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

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

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

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

B2 + B3
= (手順4の結果 - A4) + (手順5の結果 - A4)
= (手順4の結果 + 手順5の結果) - (2 × A4)

これに2通りの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
後半も同様です。

次に
手順6(11112 11112)
手順7(11112 11121)
手順8(11112 11211)
手順9(11112 12111)
を実行します。ここでの数字の1や2も答数の順番(多い方から1,2,3,4)を表しています。

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

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

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

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

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

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

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

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

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

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

これで全ての問題に対して
・答は1
・答は2
・答は3か4
のどれなのかが求められました。

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

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

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

C3 0
C4 0

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

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

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

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

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

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

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



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

コメント

このブログの人気の投稿

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

Swift2.2からSwift3.0への変換を行ってみて

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