天秤パズル(一般解法編)

元の記事はこちら

http://anond.hatelabo.jp/touch/20160629132908

それへの考察「天秤パズル増田解法考察編」

http://amori.hatenablog.com/entry/2016/07/02/195420

の続き。

天秤パズルの最大値は、結局は天秤で量った結果の組み合わせが、試行回数に対して何通り意味を持つか、という問題である。

天秤の状態は、左傾き・釣り合い・右傾き(以下、左・合・右または/,=,＼と記す。釣り合わない場合をまとめて、傾または≠、傾きが変化するのを転、×とする)の3状態がある。よって最大でn回の天秤で $3^n$ 個の玉を区別できるはず。

実際、もし問題の条件が「ひとつだけ軽い(もしくは重い)玉がある」だと、3状態を完全に区別することがかのうなので、一回の天秤で、

左→右が軽いので右の皿の玉に答えがある

合→量ってない残りに答えがある

右→左が軽いので左の皿の玉にこたえがある

と完全な三分法で答えに辿り着ける。天秤パズルは3進法が基本(^_^)

さて、ここからが本題。

答えの玉が軽いか重いかがわからない場合、一回の天秤でわかるのは合か否かの2通りなので・・というのが先に想像した増田解法での考え方であるが、

実は、一度天秤で量って傾いた場合の玉については、この情報(仮情報と呼ぼう)を使うことで天秤の結果を3状態として解答を絞りこむことができるのである。

逆に、最初からずっと天秤が釣り合い続けると、仮情報を得られないので状況はほぼ変わらない。違うのは、2回目以降は正しい重さの玉を使うことができるということのみ。

では、仮情報をどのように使えるか説明する。

例えば、4個の玉ABCDを量って左(AB/CDと記す)になったとする。この場合ABCDの中に答えの玉があることがわかるだけでなく、ABが答えならば、それはそれは重くなくてはならず、CDならば軽くなくてはならない。

この情報を利用すれば次にA_Bを量ることで、

A/B →Bは軽くないので答えはA

A=B →CかDが答え

A＼B →Aは軽くないのでBが答え

と3状態で区分することがてきる。

この例でABCDではなく、ABCと、既に正しいとわかっている重さの玉Tを使えるのであれば、DのところにTに替えて

AB/CTを量り、

A=Bの時の時には答えをCに確定できる。

最後の一回の天秤は基本的にこのパターンである。天秤の3状態を区別できるように各玉について「これが答えなら重い、軽い」という情報を使えるように量る玉の選択と組み合わせを選ぶことで

ひとつ前の天秤では9個+T玉を、ふたつ前では、27個+T玉を量ることで $3^n$ のパターンを繰り返す。

天秤パズルの区別可能な最大個数とその解法は、この組み合わせで導ける。

それでは以上を踏まえて、試行回数が1回の場合から順番に、その考え方の具体例を示す。

・試行回数1回の場合

一回の天秤だから最大3個区別したいところだが、最初なので正しい重さを参照できる玉Tに相当すら玉がないので、2個しか量れない。これは必ず傾くし傾いたところでどっちが答えかわからない。

回数一回の天秤、つまり最後の一回の天秤が意味を持つのは、

1)無情報の2個ABと参照用のTがある場合:

A/TまたはA＼T →Aが答え(重さもわかる)

A=T →Bが答え(重さはわからない)

2)仮情報(答えの可能性がある)が同じABとその他のC(仮情報はなくてもよい)の3個がある場合:

A=B →Cが答え

A/B →仮情報に一致する傾きの方の玉が答えの玉

という場合である。これは試行回数が増えた時の最後の一回に適用できる。

・試行回数2回の場合

最初の天秤の結果で以下の2通りが考えられる。

3) 合→残りの玉を1)の方法で量る。よって区別できるのは2個

4) 右または左→最初に量った玉が2回目の天秤の対象となる。次の天秤で区別できるのは最大3個であるが、最初に量れるのは偶数個であり、4個だと最後の一回で区別ができない玉が残る。よって区別できるのは2個まで

以上から2+2=4個までなら2回の試行で正解の玉を決定できることがわかる。

具体的手順は、玉4個をABCDとして、

1回目:A_B: (_は、AとBを量ることとする)

A=B → C_T (Tは正しい重さの玉、AかB)

A / B → A_T

2回目:

C=T → 答えD

C≠T → 答えC

A=T → 答えB

A≠T → 答えA

・試行回数3回の場合

5) 最初の天秤で合の場合、残り2回の場合とほぼ同じになるが、2回目から正しい玉Tが使えるので、3個+Tを量り残り2個、つまり5個まで量れる。

6) 最初の天秤で傾の場合、仮情報を使えるので後は2回の天秤で最大で $3^2=9$ 個まで区別できるが、最初の天秤で偶数個になるので8個まで量れる。

よって13個が最大値となる。

13個をABCDEFGHIJKLMとして手順を具体化する。

1回目: 6)よりABCD_EFGH

ABCD=EFGH → IJ_KT

ABCD ≠ EFGH → ABE_CDF

※この組み合わせの変更で、重さの仮情報を利用して次の天秤で3個に絞りこめる。仮情報を重・軽と表すとして、ABCD ≠ EFGH が重重重重/軽軽軽軽として、 ABE_CDFは重重軽_重重軽となっている。もし ABE/CDFならば左の軽、右の重２つは答えではないことがわかり、答えの候補はABFに絞られる。

2回目:

IJ=KT → L_T

IJ ≠ KT → I_J

ABE=CDF → G_T ※GHが候補

ABE ≠ CDF → A_B ※ABFが候補

ABE × CDF →C_D ※CDEが候補

3回目

L=T →答えM、 L≠T →答えL

I=J →答え K、 I≠J →答え I

I×J →答え J (Jの移動で傾きが変わるから)

G=T →答えH、G≠T →答えG

A=B →答え F、A≠B →答えA、A×B→答えB

C=D→答えE、C≠D→答えC、C×D→答えD

以上を一般化すると、

玉の重さがわからない場合の天秤パズルは、天秤をn回使えるの場合の区別できる玉の最大値M(n)は、

最初の天秤で

a)合の時は、残りM(n-1)+1個を区別可能。

b)傾の時は、残りの天秤n-1回で $3^{(n-1)}$ 以下の偶数、すなわち $3^{(n-1)}-1$ 個が区別可能。

となる。よって、

M(n)=M(n-1)+3^(n-1)

これは、

[tex: M(n) - M(n-1) = 3^{(n-1)}\\

M(n-1) - M(n-2) = 3^{(n-2)}\\

・・・・\\

M(4) - M(3) = 3^{3}]

----合計して-----

[tex: M(n) - M(3) = 3^{(n-1})+3^{(n-2)}+・・+3^3

M(n) = M(3) +3^3｛3^{(n-4)}+・・+1｝

=13+3^3×rac{(3^{(n-3)}-1)}{(3-1)}

=13+(3^n - 27)/2

=(3^n - 1)/(3 - 1) ]

この式はn=2以上で一般に成立する

・・・あ、そうか。これ3の等比数列の和だったのか。

4、13、40って並びに見覚えがあったわけだ(^^;;

amori's blog

よろず技術系と趣味関係の雑記です。アニメの比重が高くなってます・・

天秤パズル(一般解法編)