★ 13枚の金貨★





*****************************************************
金貨が13枚あり、このうち一つは偽物である。
偽金貨は本物と重さが異なるが、重いか軽いかは分かっていない。
天秤を3回使って、偽物を見つけるにはどうすれば良いか。
(必ずしも重いか軽いかまで特定する必要は無いとする。)
*****************************************************



**以下に使う記号の定義**
・◎は本物だと判明している任意の金貨を表す
・{ A }{ B } はAとBを天秤に乗せて比べると言う意味
・金貨13枚を A1,A2,A3,A4,B1,B2,B3,B4,C1,C2,C3,C4,C5 と名前をつける。


以下が解答の一例。
最後の詰めの段階については、これ以外にもいくつか方法はある。



1回目の測定で{A1A2A3A4}{B1B2B3B4}を比べる。
(1).{A1A2A3A4}={B1B2B3B4}
(2).{A1A2A3A4}>{B1B2B3B4}
(3).{A1A2A3A4}<{B1B2B3B4}
の3通りの可能性があるが、対称性から(1)と(2)だけ考えれば一般性を失わない。


(1).{A1A2A3A4}={B1B2B3B4}のとき
・分かることは『A1-A4,B1-B4は◎』かつ『C1-C5に重いか軽いか分からないもの がある』
・2回目の測定では{C1C2}と{C3◎}を比べる

(一) {C1C2}={C3◎}の時
  ・C4かC5かが軽いか重いかのどちらかである
  ・3回目の測定で{C4}{◎}とし、つりあえばC5、傾けばC4が偽物と特定できる
(二) {C1C2}>{C3◎}
  ・C1かC2が重い、またはC3が軽い
  ・3回目で{C1}{C2}とし、つりあえばC3、つりあわなければ重い方と特定
(三) {C1C2}<{C3◎}
  ・C1かC2が軽い、またはC3が重い
  ・3回目で{C1}{C2}とし、つりあえばC3、つりあわなければ軽い方と特定


(2). {A1A2A3A4}>{B1B2B3B4}のとき
・分かることは、『C1-C5は◎』かつ『A1-A4の何れかが重い、又は、B1-B4の何れ かが軽い』
・2回目の測定では{A1A2A3B1B2}と{◎◎◎◎◎}を比べる

(一){A1A2A3B1B2}={◎◎◎◎◎}の時
  ・A4が重い、又はB3B4の何れかが軽い
  ・3回目で{B3}{B4}とし、つりあえばA4、つりあわなければ軽い方と特定
(二){A1A2A3B1B2}>{◎◎◎◎◎}
  ・A1A2A3の何れかが重い
  ・3回目で{A1}{A2}とし、つりあえばA3、つりあわなければ重い方と特定
(三){A1A2A3B1B2}<{◎◎◎◎◎}
  ・B1とB2の何れかが軽い
  ・3回目で{B1}{B2}とし、軽い方が偽物




★応用問題★
*****************************************************************
金貨N枚の中に、一枚、重いか軽いか分かっていない偽物が混じっている。
天秤をn回用いて偽物を見分けることの出来る、最大の金貨数N_nを求めよ。
(必ずしも偽物が重いか軽いか特定する必要は無いとする。nは1以上の自然数)
*****************************************************************


答え:
N_n = (3^n - 1)/2 (n=1,2,3,4,...)




考え方:
結構面倒くさいので、3ステップに分けて考えることにする。

★step1.偽の金貨が"重い"ことが分かっている場合、
   天秤をn回用いて偽物を特定できる金貨の最大枚数を求める。


天秤の状態数は、つりあう、右に傾く、左にかたむく、の3通りなので、答えは3^n。

*注意:
現実には、最初の測定で3^nを3等分したうちの二つを比べ(例えばABCのグループに分けAとBを比べる)、
次の測定でつりあっていれば残りの一つ(C)を3等分したうちの二つを比べる、
傾いていれば重いほうにあるのが分かっているので、それをやはり3等分したうちの二つを比べれていけば出来る。




★step2.もし『本物だということが確定している金貨』を測定の際に好きなだけ使っていい場合、
   天秤をn回用いて、最大何枚の『”本物か偽物か分からない”かつ”偽物は重いか軽いかわからない”金貨』を特定出来るかを考える。



n回での天秤測定で特定可能な金貨の最大枚数をG_nと置く。◎は本物の金貨を表すとする。
とりあえずn=1から見ていくと

・n=1 で G_1=2 (2枚のうちの1枚と◎を比べる)
・n=2 で G_2=5 (1回目の測定で5枚のうちの3枚と◎3枚を比べる)
・n=3 で G_3=14 (1回目で4枚と4枚を比べる。後は妄想でどうぞ。)
:

これを論理的に解釈すると以下の事実が非常に重要になってくることに気づく。
・”重いか軽いかが分からない”金貨を秤を用いて一度で見分けることの出来る最大の枚数は2。
・”重いか軽いかが分かっている”金貨を一度で見分けることが出来る最大の枚数は3。


以下、G_nを論理的に導出していく。

・n=1での最大枚数G_1は”重いか軽いかが分からない”金貨を秤を用いて
一度で見分けることの出来る最大の枚数である。

即ちG_1 = 2

・n=2での最大枚数G_2
一回目の測定で、G_2枚のうちの ?枚 と ◎?枚を比べる。
- これで傾けば、?枚のうちどれかが”重いか軽いかが確定した”偽金貨である。
あと一回の測定で偽物を確定させるには?は最高で3枚。
- 一方、一回目の測定でつりあえば、残り(G_2 - ?)枚のいずれかが”重いか軽いか分からない”
偽金貨であるが、あと一回で確定させるには最高2枚。

よってG_2 = 2 + 3 = G_1 + 3^1

・n=3ではこうなる。
一回目の測定で{A}{B}{C}のグループに分けて、AとBを比べるとする。
- AとBがつりあう場合、Cの中に”重いか軽いか不明な”金貨がある。
あと2回で確定するためにはCは G_2=5枚以内であるべし。
- AとBが傾く(例えばA>B)場合、例えばAの中に偽がいれば偽物は軽い、
Bにいれば重い、という情報が確定することになる。
よって、あと2回の測定で原理的に3^2枚の金貨が確定できる。

G_3 = G_2 + 3^2


以下同様に
G_4 = G_3 + 3^3
G_5 = G_4 + 3^4
:
G_n = G_{n-1} + 3^{n-1}

これは単なる数列なので簡単に解けて
G_n = G_{n-1} + 3^{n-1}
  = G_{n-2} + 3^{n-2} + 3^{n-1}
= G_{n-3} + 3^{n-3} + 3^{n-2} + 3^{n-1}
:
= G_1 + 3^1 + 3^2 + .... + 3^{n-3} + 3^{n-2} + 3^{n-1}
= 2 + 3*(3^{n-1}-1)/(3-1) ←等比級数の和。懐かしい。←オイ。
  = (3^n + 1)/2

と求まる。ふう。




これで準備が揃って、やっと本題に入ることになる。

★step3.『本物だということが確定している金貨』が最初から与えられていない時に
    天秤測定n回で、重いか軽いか分かっていない偽物が特定出来る, 最大金貨数N_nを求める。(本当に求めたかったもの!)



まず、実際に手を動かしてみると
・n=1ではN_1=1 (金貨一個しかないので、それが偽だということは確定←寧ろ測定する必要なし。。)

・n=2 ではN_2=4 (最初にひとつずつ天秤に乗せるやり方ね。)


以降では、n>2の場合を考える。
step2と同様、一回目の測定で{A}{B}{C}のグループに分けて、AとBを比べるとする。
◎は本物と確定できた金貨を表すとする。


・AとBがつりあう場合、Cの中に”重いか軽いか不明な”金貨がある。
step2で見たように、あと(n-1)回の天秤測定で確定するためにはCは最大G_{n-1}枚まで取りうる。

*注意:
ここで、一回目の測定でAとBの全ての金貨が◎になり、
Cの測定の際に用いる本物金貨数はこれらの総計で十分であることを仮定している。
以下の過程で明らかになるように、A+Bの枚数は必ずCの枚数よりも多い。
 *このことの証明:(A+Bの枚数)-(Cの枚数)=(3^n - 1) - G_{n-1} = 3/2 * (3^{n-2} - 1) > 0 (n>2だから)
◎の数はCと同等数以上あればそれ以上あっても無意味なので
(最大で”全てのC”と”同じ数の◎”を天秤に乗せれば十分)この仮定は最もである。



・一回目の測定でAとBが傾いた(例えばA>B)場合、
Aが重い又はBが軽いという状態が確定していたので、
原理的にあと(n-1)回の測定で3^{n-1}枚の金貨が確定可能。
しかし!A+Bの数は必ず偶数でならなく、3^{n-1}は必ず
奇数であることから、A+Bの最大枚数は常に3^{n-1} - 1 。



以上より、n回目の測定で確定できる最大枚数は
N_n= G_{n-1}  +   3^{n-1}
↑Cの総数  ↑AとBの総数

= (3^{n-1} + 1)/2 + (3^{n-1} - 1)

= (3^n - 1)/2

n=1,2の時も上記の式を満たす。


よって、最終的な答えは以下。
N_n= (3^n - 1)/2 (n=1,2,3,4,..) 



(cf)
この式を用いると、
N_1 = 1
N_2 = 4
N_3 = 13
N_4 = 40
N_5 = 121
: