『にせ金を探せPart4』

『にせ金を探せPart4』解答

◆東京都　eikiさんからの解答。

【問題１の解答の前に】

まず、２枚の中に１枚だけ軽い『にせ金』があるときの手順を説明します。
（２枚のコインをＡ、Ｂとし、ＡがＢより軽いことを「Ａ＞Ｂ」のように表わします）
ＡとＢを天秤にかけると１回の計量で『にせ金』が発見できます。

Ａ＞Ｂのとき・・・・・・Ａが『にせ金』、Ｂは『本物』
Ａ＜Ｂのとき・・・・・・Ｂが『にせ金』、Ａは『本物』
Ａ＝Ｂのとき・・・・・・ありえません

この手順を「基本判定１／２」と呼ぶことにします。

次に、３枚の中に１枚だけ軽い『にせ金』があるときの手順を説明します。
（３枚のコインをＡ、Ｂ、Ｃとします）
ＡとＢを天秤にかけると１回の計量で『にせ金』が発見できます。

Ａ＞Ｂのとき・・・・・・Ａが『にせ金』
Ａ＜Ｂのとき・・・・・・Ｂが『にせ金』
Ａ＝Ｂのとき・・・・・・Ｃが『にせ金』

この手順を「基本判定１／３」と呼ぶことにします。

これら２つの基本判定は「確実に『にせ金』が含まれていること」がポイントです。

【問題１の解答】（６枚のコインをＡ、Ｂ、Ｃ、Ｄ、Ｅ、Ｆとします）

３種類の方法を考えました。

　３つの方法それぞれで発見する確率（計量回数の期待値）が違うような気がするのですが。
もっと感覚的な表現をすると、優れている方法と優れていない方法とがあるような気がするのですが、数学的に答が求められますでしょうか？

【コメント】

　解答が３通りあるとは思いませんでした。
実は、「最も運のよいときは、何回の計量で発見できるか」という問題も考えていたのですが、難しいかと思って断念したのです。
面白そうなので、ｅｉｋｉさんの３通りの方法のいずれが優れているのか、どなたか考えていただけませんか。

◆広島県　清川　育男　さんからの解答。

【問題２】

答え　２回

　コインを仮にＡ，Ｂ，Ｃ，Ｄ，Ｅ，Ｆ，Ｇ，Ｈ，Ｉとする。

  1. Ａ＋Ｂ＋Ｃ＝Ｄ＋Ｅ＋Ｆの時

    　Ｇ＝Ｈ　>>>Ｉ
    　Ｇ＞Ｈ　>>>Ｈ
    　Ｇ＜Ｈ　>>>Ｇ

  2. Ａ＋Ｂ＋Ｃ＞Ｄ＋Ｅ＋Ｆの時

    　Ｄ＝Ｅ　>>>Ｆ
    　Ｄ＞Ｅ　>>>Ｅ
    　Ｄ＜Ｅ　>>>Ｄ

  3. Ａ＋Ｂ＋Ｃ＜Ｄ＋Ｅ＋Ｆの時

    　Ａ＝Ｂ　>>>Ｃ
    　Ａ＞Ｂ　>>>Ｂ
    　Ａ＜Ｂ　>>>Ａ

以上です。

【コメント】

一回で終わらないのはほとんど明らかですから、２回で可能なことが示されれば十分でしょう。

◆広島県　清川　育男　さんからの解答。

【問題４】

Ａ＝１のとき　題意に合わない。
Ａ＝２のとき　判定不能。
Ａ＝３のとき　２回の計量が必要。

Ａ≧４のとき
　Ａ≦４×３n，ｎは自然数で式を満たす最小の数。
　最高で（ｎ＋２）回の計量が必要。

Ａ＝４のとき　ｎ＝１，４≦１２，
　最高で３回の計量が必要。

Ａ＝１２のとき　ｎ＝１，１２≦１２，
　最高で３回の計量が必要。

Ａ＝１６のとき ｎ＝２，１６≦３６，
　最高で４回の計量が必要。（問題３の場合）

Ａ＝３６のとき　ｎ＝２，３６≦３６，
　最高で４回の計量が必要。

例えば３６個の場合を考える。
１２個と１２個を載せて釣り合った場合、残りの１２個のなかに重さの違ったものがあることになる。
その後は、最高３回の計量で判定可能。

釣り合わなかった場合、２４個のなかにそれがあることになるが、２４÷２＝１２。
「二分の一判明の理論」によると１２個分の情報と同じになるから、その後は、最高３回の計量で判定可能。
したがって、いずれにしても最高で４回の計量で判定可能。

以上のことが予想されます。

●３６個のときの手順

A1,A2,...,A12,B1,B2,...,B12,C1,C2,....,C12とする。

1) A1+A2+....+A12=B1+B2.....+B12 の時，
C1,C2,..,C12の１２個の中にあることになる。
これは１２個、３回の計量の問題に還元される。

2) A1+A2+....+A12＞B1+B2.....+B12 の時、

i)A1+A2+A3+A4+B1+B2+B3+B4＝A5+A6+A7+A8+B5+B6+B7+B8の時

A9,A10,A11,A12,B9,B10,B11,B12の中にあることになる。

i-1) A1+A9+B9=B10+B11+A10
(A1は本物。A11,A12,B12の中にあることになる。)

i-1-1) A11＝A12 →B12が軽い。
i-1-2) A11＞A12 →A11が重い。
i-1-3) A11＜A12 →A12が重い。

i-2) A1+A9+B9>B10+B11+A10
(A1は本物。A9,B10,B11の中にあることになる。)

i-2-1) B10＝B11 →A9が重い。
i-2-2) B10＜B11 →B10が軽い。
i-2-3) B10＞B11 →B11が軽い。

i-3) A1+A9+B9＜B10+B11+A10
(A1は本物。A10,B9の中にあることになる。)

i-3-1) A1＝A10 →B9が軽い。
i-3-2) A1＜A10 →A10が重い。
i-3-3) A1＞A10 →矛盾。

ii)A1+A2+A3+A4+B1+B2+B3+B4>A5+A6+A7+A8+B5+B6+B7+B8の時

A1,A2,A3,A4,B5,B6,B7,B8の中にあることになる。

ii-1) A10+A1+B5=B6+B7+A2
(A10は本物。A3,A4,B8の中にあることになる。)

ii-1-1) A3＝A4 →B8が軽い。
ii-1-2) A3＞A4 →A3が重い。
ii-1-3) A3＜A4 →A4が重い。

ii-2) A10+A1+B5>B6+B7+A2
(A10は本物。A1,B6,B7の中にあることになる。）

ii-2-1) B6＝B7 →A1が重い。
ii-2-2) B6＜B7 →B6が軽い。
ii-2-3) B6＞B7 →B7が軽い。

ii-3) A10+A1+B5＜B6+B7+A2
(A10は本物。A2,B5の中にあることになる。）

ii-3-1) A10＝A2 →B5が軽い。
ii-3-2) A10＜A2 →A2が重い。
ii-3-3) A10＞A2 →矛盾。

iii)A1+A2+A3+A4+B1+B2+B3+B4＜A5+A6+A7+A8+B5+B6+B7+B8の時

A5,A6,A7,A8,B1,B2,B3,B4の中にあることになる。
以下はii)の場合と同様の手続きにより特定できる。

3) A1+A2+....+A12＜B1+B2+....+B12の時

以下は2)の場合と同様の手続きにより特定できる。

以上により３６個のコインの場合、４回の計量で特定できることになる。

これ以上の個数は無理だと思われます。
「３分割法」と「二分の一判明（１回天びんに載ると半分の情報がわかる。）」は、有力な方法だと思います。

【コメント】

　３６個の手順は本物を混ぜて測定するのが巧妙ですね。
一般の場合の証明は数学的帰納法（あるいはいわゆる山登り法）を使うのでしょうか。
私自身は予想が正しいのかどうか、まだ確認できていないのですが、証明ができた方はぜひお知らせください。

◆広島県　清川　育男　さんからの解答。

コイン１３個の場合

　４個，４個の載せて、釣り合わないときは、１２個の問題に還元される。
釣り合った場合、残り５個のなかにあることになり、それらのコインをＡ，Ｂ，Ｃ，Ｄ，Ｅとする。

Ｄ，Ｅの２個を残す。

i) Ａ＋Ｂ＝Ｃ＋Ｘ (Ｘは本物)の時

　i-1) Ｄ＝Ｘ → Ｅが違う。
　i-2) Ｄ＞Ｘ → Ｄが重い。
　i-3) Ｄ＜Ｘ → Ｄが軽い。

ii) Ａ＋Ｂ＞Ｃ＋Ｘの時、Ｂを残す。

　ii-1) Ａ＋Ｃ＝Ｘ＋Ｘ → Ｂが重い。
　ii-2) Ａ＋Ｃ＞Ｘ＋Ｘ → Ａが重い。
　ii-3) Ａ＋Ｃ＜Ｘ＋Ｘ → Ｃが軽い。

iii) Ａ＋Ｂ＜Ｃ＋Ｘの時、Ｂを残す。

　iii-1) Ａ＋Ｃ＝Ｘ＋Ｘ → Ｂが軽い。
　iii-2) Ａ＋Ｃ＞Ｘ＋Ｘ → Ｃが重い。
　iii-3) Ａ＋Ｃ＜Ｘ＋Ｘ → Ａが軽い。

以上より、１２個の場合は軽いか重いかが特定できるが、１３個の場合は１個は違うということしか判らない。

【コメント】

　これはコイン１３枚の場合は、３回の測定では、にせ金はどれかを決定できるが、重いか軽いかを指摘することはできないということの説明です。

◆神奈川県　わかさひ君からの解答。

☆準備

その１：枚数が少ないとき
Ａ＝３で考えてみます。
この場合、１枚どうしを比較するしか天秤を使う方法はありません。
にせ金が本物より重いかどうかは分からないのですから、天秤がつりあわなかったからといってすぐに偽物は分かりません。
２回使えば、偽物は見つかります。

# Ａ＝２のときは、見つけようがありませんね。

でもＡ＝１２のときは３回で見つかる(重さの区別も付く）ので、面白いですね。
Ａ＝１３のときも３回で計れますが、重さの区別がわからない場合があります。
これがちょっと厄介になります。

その２：偽物の重さの特徴が分かっているとき〜問題２の考察

一般的に、３n個の中の一つの偽物（本物より重いか軽いかが分かっている）を見つけ出すために必要な操作の回数がｎです。

# 詳しく書くと問題２の一般化の解答になるので省略。

☆解の予測（少なくともこれ以下で計れる保証は出来ると思います）

ｎ回の操作で計れる最大の個数は、

A(n) = 4×3n-2 + R(n)

でしょう。

３回計ったときに重さの区別の付かなかったもので
そのあと(n-3)回で計れる金貨の枚数を示す 剰余項R(n) については後述します。

すくなくとも１２個(=4x3)は３回で重さの区別付きで分かるので、最初に金貨を１２グループに分けることによって、偽物の入っている １グループが、重さの区別付きで判断できます。
（もしくは、３回の操作で、R個の中に偽物がある事が分かります）

したがって、この１グループの中から偽物を判別するためには、上記「その２」をそのまま利用できるので、
都合 4×3n-2 となります。

さて、R(n)のところですが、

n=3 のときに R(3) =1 はいいでしょう。
n=3+k のとき、 R(3+k)=A(k) とでもしたくなるんですが、
この部分では、すでに4×3n-2個が本物であることが分かっているので、これを利用すると少々状況が変わってきます。
本物が分かっている状態では、５個までが２回で計りきることが出来ます。
ただし、このときは偽物の重さがわからない場合があります。
４個なら、重さの区別付きで２回で計りきれるのは変わりません。

# １回で計れるのは２個（重さの区別無し）、１個（区別あり）

したがって、k=n-3 , k≧2 とすると

R(k) = 4×3k-2 + 1

となります。（ちょっと端折りすぎかな？）

したがって、これらをまとめると、

A(1) = 1 , A(2) = 4, A(3) = 13, A(4) = 36+2=38
A(n) = 4×3n-2 + 4×3n-5 + 1 (n≧5)

となります。たぶん。

◆妹尾　さんからの解答。

【問題４】

「重いか軽いか確実に区別をつける」場合は
３N−３
２		個のコインまで対応できる。
(それ以上は無理)

◆５回で１２０個まで判定する手順

それぞれを 1 から 120 と番号をつけると次のようになります。 


1回目 [1-40] と [41-80] を比較 (40枚づつ)

●左が重かった場合：
[1-40] のどれかが重いか、[41-80]のどれかが軽い  ... (a)

　２回目 [1-14 41-53] と [15-28 54-66] を比較 (27枚づつ)

　◎左が重かった場合：
　 [1-14] のどれかが重いか、[54-66]のどれかが軽い ... (b)

　３回目 [1-5 54-57] と [6-10 58-61] を比較 (9枚づつ)

　　○左が重かった場合：

　　 [1-5] のどれかが重いか、[58-61]のどれかが軽い ... (c)

　　４回目 [1 2 58] と [3 4 59] を比較 (3枚づつ)

　　　□左が重かった場合：
　　 　[1 2] のどれかが重いか、[59]のどれかが軽い ... (d)

　　　５回目 [1] と [2] を比較 (1枚づつ)
　　　　・左が重かった場合：1 が贋物(重い)
　　　　・右が重かった場合：2 が贋物(重い)
　　　　・つりあった場合：59 が贋物(軽い)

　　　□ つりあった場合：
　　　[60 61]のどれかが軽いか、[5] のどれかが重い
　　　(d)と同じパターンと見なして続ける。
　　　(重い/軽いは反転することに注意)
               
　　○つりあった場合：
　　 [62-66]のどれかが軽いか、[11-14] のどれかが重い
　　 (c)のパターンと見なして続ける。
　　 (重い/軽いは反転することに注意)

　◎つりあった場合：
　[67-80]のどれかが軽いか、[29-40] のどれかが重い
　(b)のパターンと見なして続ける。
　(b) よりも 1枚少ないが、同様な方法で続ける事は可能。
　(重い/軽いは反転することに注意)

●つりあった場合：
[81-120]のどれかが重いか軽い

　２回目  [1-27] と [81-107] を比較 (27枚づつ)

　◎左が重かった場合：
　[81-107]のどれかが軽い
　あとは ２７枚から ３回で 軽いコインを見つけるだけ。

　◎右が重かった場合：
　[81-107]のどれかが重い
　あとは ２７枚から ３回で 重いコインを見つけるだけ。

　◎つりあった場合：
　[108-120]のどれかが重いか軽い

　３回目  [1-9] と [108-116] を比較 (9枚づつ)
 
　　○左が重かった場合：
 　　[108-116]のどれかが軽い
　　あとは ９枚から ２回で 軽いコインを見つけるだけ。

　　○つりあった場合：
　　[117-120]のどれかが重いか軽い

　　４回目  [1-3] と [117-119] を比較 (3枚づつ)

　　　□左が重かった場合：
　　　 [117-119]のどれかが軽い
　　　あとは 3枚から 1回で 軽いコインを見つけるだけ。

　　　□つりあった場合：
　　　[120]のどれかが重いか軽い

　　　５回目  [1] と [120] を比較 (1枚づつ)

　　　　・左が重かった場合：120が贋物 (軽い)
　　　　・右が重かった場合：120が贋物 (重い)
　　　　・つりあった場合：ありえない。
＃ ちょっと疲れた。^^;

なお、４回ならば ３９個 (≠３８個) までいけるハズです。

詳細はこちらです。

贋物コイン判定プログラムはこちらです。

コインの数 に １２１を入力してやると５回の測定で１２０枚のコインから重い、軽いの判定も含めて、贋物を見つける事ができます。
この場合は１２１番目のコインは天秤には一度も乗りません。

◆広島県　清川　育男　さんからの解答。

重いか軽いかが判っていれば、
　Ｎ回の測定で最大３Ｎ個、識別可能と言うのが基本になるのですね。 


１）　　　　１−１＝０　　　　　０÷２＝０　 　　　 ０×３＝０　　
２）　　　  ３−１＝２　　　  　２÷２＝１        　１×３＝３
３）　　　  ９−１＝８　　　　  ８÷２＝４      　４×３＝１２
４）　　２７−１＝２６　　　２６÷２＝１３    　１３×３＝３９
５）　　８１−１＝８０　　　８０÷２＝４０  　４０×３＝１２０
６）２４３−１＝２４２　２４２÷２＝１２１　１２１×３＝３６３
．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．
．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．



Ｎ）　
３N−３
２
よく理解できました。やっとスッキリしました。ありがとうがざいました。

◆東京都　vic.R さんからの解答。

【問題４】

A個のコイン中1個のニセコインを天秤で何回の秤量で発見できるか

●１

天秤で量ることによって得られるのは3個の情報
（左重、右重、平衡）。
A個のコインから1個のニセコインのあるケースの数は

軽重がわかっていれば A
軽重不明ならば軽重わけて 2A

すなわち、
天秤秤量から得られた（有効な）情報≧Aないし2A

である必要がある

したがって、
3k-1＜A≦3k (k自然数)とすると、軽重がわかっている場合、少なくともk回の天秤秤量が必要

●２

まず 軽重がわかっている場合について考察する。

(1)A＞Bならば、ニセコイン発見秤量回数を
それぞれF(A),F(B)とすると

F(A)≧F(B)

もしも、F(B)＞F(A)であれば、B-A個の正常コインを追加することにより、
F(B)=F(A)とできるので、この条件が満足されないケースをのぞき、上記は成立する。

この条件は下記の操作の場合、正常コインの判別がなされる操作なので（数値の少ないときを除けば）正常コイン追加が可能。

(2)Aをほぼ等分の３つのグループに分ける。
つまり A=3A1-a1(a1=0,1,2)とすると

a1=0のとき (A1, A1, A1)
a1=1のとき (A1-1,A1,A1)
a1=2のとき (A1-1,A1-1,A1)

同一数のコインを天秤で秤量しその結果により、どのグループにニセコインがあるか判明する

ニセコインが重いときは、天秤が傾くときは重い方（軽いときは軽い方）に、平衡のときは秤量しなかったグループにニセがある。
また正常コインは傾いたときはその一つは天秤に載らなかったグループ、平衡のときは平衡な２つが正常なコイン。
各グループもっとも大きい数値はA1であり、F(A1)が(1)にみるように最大である

つぎにA1についてAと同様の操作をする
(A=32A2-3a2-a1)
これを繰り返してAn-1=(3,2)にできる。

An-1=3An-an

an=(0,1,2)であるから、An=1

3k-1＜A≦3kであるから

A=3k- k
Σ
i=0		3iai

すなわち、k回の秤量でニセコインを発見できる。

(3)上記はコインの軽重が一意的に決まっている場合だが、秤量の結果、あるグループは重いニセコインを含む 可能性があり、別のグループは軽いニセコインを含む可能性があるといった情報が得られた場合はどうだろうか 。

必要情報量としてはAなので、(2)と同様のkの可能性があるが、アルゴリズムは同様にはいかない。

ここでは以下の議論で必要な場合すなわち3k個のコインかつ軽重可能性コインの個数差は１のときを考える。

多い方の個数は(3k+1)/2,
少ない個数は(3k-1)/2となる 。

これを3分して、多い方は

((3k-1+1)/2,(3k-1+1)/2,(3k-1-1)/2)と少ない方は

((3k-1-1)/2,(3k-1-1)/2,(3k-1+1)/2)と配分。

各3分されたグループは3k-1個のコインかつ、多い方の個数は
(3k+1)/2,
少ない個数は(3k-1)/2となる。

これをくりかえせば、3個（2個、1個）に帰着する。
これは1回の秤量でニセコインを軽重をふくめ発見できる。 したがって(2)同様ｋ回で秤量可能。

●３

軽重が不明な場合について考察する

(1)k回で量れるコインの個数は3k/2＞Aであるから

(3k-1)/2≧A

(2)1回の秤量で量れるコインの個数は0、しかしほかに1個の正常コインがあれば、1個のコインの場合、正常コインに対する軽重が判明する。

2回の秤量で量れる個数は3個。
4個の場合は、1個の正常コインがあれば以下の操作で2回の秤量で可能。

なお、2回の秤量で得られる情報量は
32=9であり、4個の場合もあと1個の情報があるので、これをいかすと5個について、軽重の判断ができないケースもあるが、ニセコインは発見可能
（注 × 秤量対象、 S 正常コイン、
　＝平衡　＞左重　＜右重）

個数3個
コインA1 A2 A3
秤量A1× A2
結果（可能性 ）＝A3+ A3-
＞ A1+A2-
＜ A1- A2+

個数4個
コインA1 A2 A3 A4
秤量(A1 A2)×(A3 S)
結果（可能性 ）＝A4+ A4-
＞ A1+ A2+ A3-
＜ A1- A2- A3+

個数5個
コインA1 A2 A3 A4 A5
秤量(A1 A2)×(A3 S)
結果（可能性 ）＝A4+ A4- A5
＞ A1+ A2+ A3-
＜ A1- A2- A3+

結果で得られたケースはいずれも1回の秤量で可能
（5個については、平衡の場合、次にA4と正常コインを秤量して平衡の場合が生ずる、
このときA5がニセコイン ただし、軽重は判断できず）

(3)次に3回の秤量で量れる最大を考える。

第1回の秤量で正常コインは判明するので、上記(2)の
4個×3=12個が3回で可能

13個となると、同様の操作では3組の1つ（秤量しない）が

5、2・5=10＞32となり2回の秤量で発見できない。

しかし、(2)の4個と同様、ほかに正常コインがあれば13個でも3回の秤量で可能となる

以下の通り

個数12個
コイン A1〜A12
グループA1〜A4,A5〜A8,A9〜A12
秤量(A1〜A4)×(A5〜A8)
結果（可能性 ）＝A9〜A12±
＞A1〜A4+ A5〜A8-
＜A1〜A4- A5〜A8+

個数13個
コイン A1〜A13
グループA1〜A5,A6〜A9,A10〜A13
秤量(A1〜A5)×(A6〜A9,S)
結果（可能性 ）＝A10〜A13±
＞A1〜A5+ A6〜A9-
＜A1〜A5- A6〜A9+

個数14個
コイン A1〜A14
グループA1〜A5,A6〜A9,A10〜A14
秤量(A1〜A5)×(A6〜A9,S)
結果（可能性 ）＝A10〜A13±，A14
＞A1〜A5+ A6〜A9-
＜A1〜A5- A6〜A9+

結果で得られたケースはいずれも2回の秤量で可能
(平衡なら4個の場合、他は9ケースで2(3)で述べた）
（14個については、5個と同様のケースで、軽重は判断できないケースが生ずる）

(4)
0=(31-3)/2, 1=(31-1)/2,

31/2, 2=(31+1)/2

3=(32-3)/2, 4=(32-1)/2, 32/2, 5=(32+1)/2

12=(33-3)/2,13=(33-1)/2, 33/2,14=(33+1)/2
である。

そこで k回の秤量で可能な最大個数が(3k-3)/2

正常コイン1個あったときが(3k-1)/2 が成立するとしたとき、k+1回での秤量を考えると第1回の秤量で正常コインは判明するのでk回の正常コイン1個必要な場合の3倍が可能となる。
すなわち、
3×(3k-1)/2=(3k+1-3)/2
（これを3Ｎ個とおく）

(3)と同様にして、

個数(3k+1-3)/2個
コイン A1〜A3N
グループA1〜AN,AN+1〜A2N,A2N+1〜A3N
秤量(A1〜AN)×(AN+1〜A2N)
結果（可能性 ）＝A2N+1〜A3N ±
＞A1〜AN+AN+1〜A2N-
＜A1〜AN- AN+1〜A2N+

個数(3k+1-1)/2個
コインA1 〜 A3N+1
グループA1〜AN+1,AN+2〜A2N+1,A2N+2〜A3N+1
秤量(A1〜AN+1)×(AN+2〜A2N+1,S)
結果（可能性 ）＝A2N+2〜A3N+1±
＞A1〜AN+1+ AN+2〜A2N+1-
＜A1〜AN+1- AN+2〜A2N+1+

個数(3k+1＋1)/2個
コインA1 〜 A3N+2
グループA1〜AN+1,AN+2〜A2N+1,A2N+2〜A3N+2
秤量(A1〜AN+1)×(AN+2〜A2N+1,S)
結果（可能性 ）＝A2N+2〜A3N+1±,A3N+2
＞A1〜AN+1+ AN+2〜A2N+1-
＜A1〜AN+1- AN+2〜A2N+1+

結果で得られたケースは平衡のときはk回の秤量の場合であり、どちらかに傾くときはケース数は
2Nまたは2N+1、
すなわち3k-1または3kであり、2(3)でのべたように、k回の秤量で可能である。

すなわち、全体でk+1回で秤量可能

以上から、k回の秤量で可能な最大個数が
(3k-3)/2

正常コイン1個あったときが
(3k-1)/2が成立するとしたときk+1回でも成立する。

(2)(3)でk=1,2,3で成立しているので、この式は成立する。

以上整理すると

ニセコインの軽重が不明なとき、ｋ回の秤量で判定可能な個数は
最大 (3k-3)/2

ただし、これ以外に正常コインが1個あれば判定可能な個数は

最大 (3k-1)/2

なお(3k-1)/2は(1)でのべたようにk回で秤量可能な限度額であり、軽重不明な場合これ以上は不可能である。
しかし、3k-2×(3k-1)/2=1であり、この情報をいかすと、軽重は判断できないケースが生ずるものの
(3k＋1)/2まで可能
（上記5,14の場合参照）

◆東京都　vic.R さんからの解答。

にせ金 Part４問題１ 追加問題

eikiさんの解答のどれが優れているかに関連して、これを平均的に秤量回数の少ないものはどれかにおきかえて解答します。
（アルゴリズムの簡明さなど、他にも基準があると思いますが、秤量回数だけにしぼった基準）

各方法について平均回数を以下で定義する。
各ケースごとにきまる秤量回数をケースすべてについて加え、ケースの合計で割る

例）4個のコインから一個の軽いニセコインを見つける
方法(1) まず1個同士で比較
A×B ＝ C×D C-
> D-
A-
> B-

この場合は 平均は((2×2)+(1×2))/4=1.5回

(2)まず2個同士で比較
(A B)×(C D) A×B A-
> B-
> C×D C-
> D-

この場合はすべて2回なので平均も2回以上で(1)の方が平均的には回数が少ないといえる。

問題の6個中2個の軽いニセコインの場合は

(1)まず 3個同士で比較
(A B C)×(D E F) = A× B D× E AD AE AF BD BE BF CD CE CF
A× B AB BC AC
> D× E DE DF EF

((9×3)+(6×2))/15=13/5=2.6

(2)まず2個同士で比較
(A B)×(C D) = A×B = EF
C×D AC AD
> C×D BC BD
C×D = CD
E×F CE CF
> E×F DE DF
> A×B = AB
E×F AE AF
> E×F BE BF

((12×3)+(3×2))/15=14/5=2.8

(3)まず1個同士で比較
A × B = (A B C)×(D E F) = D×E CD CE CF
AB
> D×E DE DF EF
Aと CDEFのどれか
例（4個）の手順
> Bと CDEFのどれか
例（4個）の手順

後の2行は例として計算したものに等しい、これを1.5とすると

((6×3)+(1×2)+(8×2.5))/15=8/3=2.666666
または((10×3)+(5×2))/15=8/3)

以上3法を比較すると(1)がもっとも平均回数が少ない

◆埼玉県　工藤　晴一 さんからの解答。

【問題４】

Ａ個のコインを何回で判定可能か、への一般解になりえると思います。

なお、例として、３回、１２個の場合を取り上げていますが これは同時に、Part２の私の解答の説明になってます。

＜解答＞

この解法のポイントは３進数（法）です。

まず、考え方を簡単にするため、偽物はあらかじめ重いと判っているとします。
（軽い場合も同様に考える事が、もちろん可能です。）

この場合、１回の操作で３つまでのなかから偽物を見つける事はたやすい事です。
３つのうち２つを天秤にかけ、下がった方が偽物。
つりあえば残したのが偽物です。

よって、すべてのコインをなるべく同じ数になるように３等分しながら偽物を絞っていく事により、全部でｋ個のコインがあるとき、

３n-1≦Ｋ≦３nを満たす、ｎ回の天秤操作で偽物を発見できます。

では、これを解く手法として、３進法を導入します。

天秤を３回使う場合を例にします。
２回や４回でも同様にできます。

３3＝２７個のコインに、０〜２６の番号を振り、３桁の３進数に書き換えます。

　０…０００　　１…００１　　２…００２　　３…０１０
　10…１０１　　20…２０２　　25…２２１　　26…２２２
といった具合です。

この、０、１、２を組み合わせた表記に、一つとしてダブりがないのがポイントです。

この数字を、以下のように読みます。

　(1)　各桁を左から、１回目、２回目、３回目の天秤操作
　(2)　”０”は、天秤に乗せない。”１”は左の天秤に、”２”は右の天秤に乗せる。

つまり、
１…００１は、１、２回目は天秤に乗せずに、３回目は左に乗せる。
23…２１２は、１回目右、２回目左、３回目右に乗せる。という具合です。

この結果、３回の天秤操作の要領は以下のようになります。

１回目
　乗せない：{0,1,2,3,4,5,6,7,8}
　左の天秤：{9,10,11,12,13,14,15,16,17}
　右の天秤：{18,19,20,21,22,23,24,25,26}

２回目
　乗せない：{0,1,2,9,10,11,18,19,20}
　左の天秤：{3,4,5,12,13,14,21,22,23}
　右の天秤：{6,7,8,15,16,17,24,25,26}

３回目
　乗せない：{0,3,6,9,12,15,18,21,24}
　左の天秤：{1,4,7,10,13,16,19,22,25}
　右の天秤：{2,5,8,11,14,17,20,23,26}

こうすることで、３回の天秤操作の結果を３進数に直す事で、偽物の番号をズバリ言い当てる事が出来ます。

つりあった場合を”０”、左が下がった場合を”１”、右が下がった場合を”２”として、
（偽物が軽い場合は、上がった場合、に読み替えて下さい）
３回の天秤操作の結果を３進数表記し、１０進数に変換すれば良いのです。

たとえば、１回目に左が下がり、２回目右が下がり、３回目はつりあったとしますと
３進数標記では”１２０”１０進数に直すと”１５”

よって、１５番のコインが偽物とわかります。

３n個のコインから、重軽が判っている偽物をｎ回の操作で見つけ出すには、
３n個のコインに、３進法でｎ桁の数字を割り振れば、あとはその数値にしたがった場所にコインをのせて天秤を使えばよいわけです。

ちなみに、コインの数が３nより少ない場合は、天秤の左右の数があうようにバランスを考えて 数字を抜き取って番号付けを行なえばＯＫです。

２６個の場合、２７個から０番を除く。
２５個の場合、２７個から１番と２番を除く。
２４個の場合、0,1,2を、
２３個の場合は1,2,3,6を．．．といった具合です。
（ただし、これが一般のｎで確実に出来るかの証明はしていません。
　厳密には必要でしょうが、いまの主題はそれではないため省略します。）

では、偽物が重いか、軽いか判らない場合はどうなるでしょう？

たとえば、１番（001）と２番（002)のコインについて考えますと、１番が重い偽物だった場合と２番が軽い偽物だった場合で、結果が同じ
（１、２回目でつりあい、３回目は左が下がる）
になってしまう事が容易に想像できます。

他に、３番(010)と６番(020)や、４番(011)と８番(022)のように３進数表記で、１と２を入れ替えた番号同士は、重軽の判別がついてない場合、この方法では区別をつけられないことがわかります。

また、一度も天秤に乗せなかった０番(000)についても、３回の天秤操作で、ぜんぶつりあったときに、偽物である事は特定できますが、重いか、軽いかは判りません。

よって、これら区別がつかないもの同士は、どちらか一つをあきらめる必要が有り、また、０番の判別もあきらめる事にします。

結果、ｎ回の天秤操作にて判別が可能な個数は、

（３n−１）／２個　　までということになります。
（ただし、これはまだ不十分な結論です）

Part２で私が呈示した、１２個のコインに振った飛び飛びの番号は、こうしてあきらめた半分の数字を除いたものだったわけです。

では、どのようにして０〜２６の数字を半分に減らせばいいのでしょうか？

以下は、こうしたらうまく行きそうだという例です。証明はしていません。
でも、わりと規則的なアルゴリズムなので、一般解に届いているように思います。

１番(001)を天秤に乗せる（採用する）とします。
この場合、２番(002)は使えません。
３番（010)を採用すれば６番(020)は使えません。

こうして、なにも考えずに小さい方から半分に減らしていくとどうなるでしょう？

やってみれば判りますが、左右の天秤のバランスが大きく崩れてしまいます。
１〜２６のうち、
1,3,4,5,9,10,11,12,13,14,15,16,17の１３個がのこりますから、
前述した１回目の天秤操作、

　乗せない：{0,1,2,3,4,5,6,7,8}
　左の天秤：{9,10,11,12,13,14,15,16,17}
　右の天秤：{18,19,20,21,22,23,24,25,26}

のうち、右側がまるまる無くなります。これではいけません。

半分に減らすには、各天秤（それも、１〜３回目の試行すべて）からバランス良く取り除く必要があるわけです。

よって、以下のように考えます。

まず、１番(001)を採用する、と決めたら、

０→１、１→２、２→０と数字を読み替えた物（112：14番）と
０→２、１→０、２→１と数字を読み替えた物（220：24番）を
必ず採用する事にします。
これで、０、１、２のバランスが取れます。

この場合、２番(002)、25番(221)、12番(110）はこれらと区別がつかないので使えません。

同様に、３番(010)、16番(121)、20番(202)を採用し、
６番(020)、23番(212)、10番(101)を消します。

このようにして、採用する番号と、区別がつかないため消去する番号が以下のように求まります。

　○採用　(1,14,24)、(3,16,20)、(4,17,18)、(5,15,19)
　○消去　(2,25,12)、(6,23,10)、(8,22,9)、(7,21,11)
ということで、使える数は1,3,4,5,14,15,16,17,18,19,20,24と求まり、
この数字を１２個のコインに振り分ける事で、偽物を発見する事ができるのです。

ここで出てこなかった数があります。

13番(111)と26番(222)です。
これらは０番(000)に関係する数と認識でき、ちょっと特別扱いしたいと思います。

とりあえずは邪魔なので、今回は抜けていてもらいましょう。

以上より、ｎ回の試行で偽物を発見できるコインの最大数は、

（３n−３）／２　個となります。
（13番、26番の分だけ減りました）

ｎ＝１のとき　０個
ｎ＝２のとき　３個
ｎ＝３のとき　12個
ｎ＝４のとき　39個　といった具合です。

今回の問題は。Ａ個のコインを何回で判定できますか？ですから、

(３n-1−３)／２≦Ａ≦(３n−３)／２

を満たす自然数ｎが答えになります。

さて、13番（と０番と26番）を除いた理由は以下の通りです。

これらを除かずに上記の方法で数を半分に減らすと、
必ず（３の倍数＋１）になるため、
（なぜなら、
（３n−１）／２
＝[(3-1)x{3n-1+3n-2+…+3+1}]／２
＝3n-1+3n-2+…+3+1
＝3×{3n-2+3n-3+…+3+1}＋１とできるため）

左右の天秤に乗せる数と余らせる数があわなくなります。
このとき、どちらかの天秤に毎回乗る（移動しない）事になる、
111や222は無いほうが都合が良いわけです。

しかし、これも使える情報の一つです。無理に捨てる事はありません。
なにか良い利用法はないでしょうか？

もし、ここに「これは本物である！」と特定できるコインが１個あるとしましょう。

この場合、13番(111)を採用して、３進数の通りに３回とも左にのせ、右にこの本物コインを乗せる事で、 他の物が偽物だった場合に全く影響をあたえず、かつ１３番が偽物だった場合にそれの重軽を含めて特定する事ができるようになります。

よって、もし、「これは本物！」と特定できるコインが他に１個あるならば、そのコインを含めて、

（３n−３）／２＋２＝（３n＋１）／２個

のコインの中から、ｎ回で偽物を特定できる事になる訳です。

この本物確定コインをのぞけば、
（３n−１)／２個となります。

ｎ＝１のとき　２個　（本物確定１個を含む。以下同じ）
ｎ＝２のとき　５個
ｎ＝３のとき　14個
ｎ＝４のとき　41個

ということです。

これは、以下の情報理論によっても確認できます。
（といっても、この「情報理論」というのを、私は正確に理解していません。
　このような検討方法もある、と聞いているだけです。）

「ｋ個のコインの中からニセモノの軽重も含めて必要な情報量は、
”log2(2k)bit”である。

天秤1回の試行で得られる情報量は”log2(3)bit”なので、偽物を見つけ出す為には、
log2(2k)÷log2(3) 以上の整数回数だけの試行が必要である。」

ｎ−１≦log2(2k)÷log2(3)≦ｎ

ｎ−１≦log3(2k)≦ｎ

３n-1≦2k≦３n（n、kは自然数）

これを満たす最大のｋは、

ｎ＝１のとき　１
ｎ＝２のとき　４
ｎ＝３のとき　13
ｎ＝４のとき　40

というように、本物確定のコインを除いた判別可能個数と一致します。

◆東京都　ニャンチャロフ さんからの解答。

ｎ回の天秤操作で何枚の金貨まで偽金貨が判別できるか考えて見ましょう。
これを読めば、システマチックに偽金貨を判別する方法が分かると思います。

量った結果には、つりあう、右に傾く、左に傾く、の３パターンがあります。
したがって、ｎ回天秤を使った結果には、３ｎのパターンがあります。
ただし、ｎ回すべてつりあうことはありませんので、　３ｎ−１パターンです。

また、金貨がＭ枚あるとすると、偽金貨のパターンは、1枚目の金貨が重い場合、軽い場合、２枚目の金貨が重 い場合、軽い場合、・・・と２Ｍ通りあるので、

2M≦３ｎ−１

M≦ ３ｎ−１
２		・・・(1)

一方、金貨と秤の関係には、(1)右に乗せる、(2)左に乗せる、(3)乗せない、の３パターンがあります。
例えば、4回量るとすると、1回目乗せない、2回目乗せない、３回目右に乗せる、４回目左に乗せる、といった感じになります。

ｎ回量るとすると、左右対称のパターンは同じと考えなければならないことに注意すれば、
３ｎ−１
２		枚の金貨に、乗せ方のパターンがダブらないように割り当てることができます。・・・(2)

このように割り当てることにより、天秤の傾き方の組み合わせで、偽金貨とそれが重いか軽いがが一意に決まります。

このように割り当てられる最大数のコインに乗せ方を割り当てた場合、
秤に乗せないことになるコインの数は、 ３ｎ-1−１
２		、
乗せるコインの数は、
３ｎ−１
２		− ３ｎ-1−１
２		＝３ｎ-1＝ ２×（３ｎ-1−１）
２		＋１

秤には、左右同数のコインを乗せる必要があり、かつ、すべての乗せ方のパターンを使い切る必要があるので、 コインの数を1枚減らすか、あらかじめ正しいと分かっているコインを1枚追加する必要があります。・・・(3)

題意より、あらかじめ正しいと分かっているコインを使うことは不適当ですので、 ｎ回の天秤操作で偽金貨が判別できる金貨の枚数は、
(1)、(2)、(3)より、M＝ ３ｎ−１
２		−１

例えば、ｎ＝４の場合は、３９枚まで偽金貨が判別できます。

金貨に１〜３９の番号をつけ、それぞれにダブらないように乗せ方を割り当てます。
分かりやすい方法は、金貨の番号を３進法に直して、０を右、１を乗せない、２を左に対応させる方法です。

こうすると1111を中心にして、1111から同じ数だけ離れた数同士は対称（左右が逆なだけ）になるので、対称の ものを含まない金貨の乗せ方が割り当てることができます。

その後、天秤の両方に１３枚づつ乗るように、いくつかの金貨の０と２を反転させます。上桁から調整していくのがコツです。

◆山形県　Shoji　さんからの解答。

問題を少し整理して一般的に解いたほうがわかりやすい様な気がします。
Ｎ枚中に偽コインが1枚含まれていることが判っているが、その軽重は不明。

R回天秤を使うとき、

  1. どのコインが偽物かを判定できる最大のNを求めよ

    (@)　Ｎ枚のコインのみを用いて判別する
    (A)　Ｎ枚の他に本物のコインを利用可能

  2. 偽物を判定するだけでなくそれが重いか軽いかまでを判別できる最大のNを求めよ

    (@)　Ｎ枚のコインのみを用いて判別する
    (A)　Ｎ枚の他に本物のコインを利用可能

結論は

[1-@]　N≦ ３R−１
２
[1-A]　N≦ ３R＋１
２
[2-@]　N≦ ３R−３
２
[2-A]　N≦ ３R−１
２

証明は、http://www.geocities.jp/sakuradajuku/kuizu2.htmを参照

　『にせ金を探せPart4』へ

　数学の部屋へもどる