偽金貨を探そう
松井知己，松井泰子
Il……………………………ll………l…‖‖‖‖‖＝‖‖‖‖‖‖‖‖‖‖＝＝‖‖＝‖‖＝‖‖＝‖‖‖‖‖‖‖‖＝‖＝‖‖＝‖‖＝‖‖＝………………ll…l……………………………I………ll………ll……………‖川‖‖川＝‖＝‖‖………lI……………ll…ll…

1．偽金貨パズル

考えてみましょう。20個の金貨のうちどれか1つだけ、次のパズルは誰でもどこかで読んだことのあるもので金貨が重い」，「2番目の金貨が重い」，…）「20番目のしょう。

問題1 いまここに金貨が20個ある。見た目はすべてそっくりなのだが、実は1個だけ重い偽金貨が混じっている。この偽金貨を、天秤を使って見つけだしたいのだが、いったいどうやったら良いだろう。ただし天秤を使う回数はできるだけ少なくしてほしい。

さて答は？ここで、「やり方は解らないけど、答は3回」と即答できる方はこの記事を読む必要はありません。次の記事に進んでください。
この手の問題が書いてある多くのパズルの本では、答●重い偽金貨が混じっているのですから、答は「1番目の金貨が重い」の20通りあるはずです。そう、すなわち2回天秤を使っただけでは9通りの答しかできないのですから、20通りの答が存在する上の問題に答えることは不可能なのです。ちなみに3回天秤を使うと、3×3×3＝27通りの答が可能であり、20通りより多いので、答が可能となりそうです。興味のある人は実際の手順を考えてみて下さい。

2．金貨を増やすと…？
3回天秤を使うと27通りの答が可能なのですから、は3回と書いてあり、そのやり方も示されているのです

問題1で金貨を27個まで増やしても良さそうですね。

が、3回が最小回数なのでしょうか？この手数の最小性

実際その通りです。27個の金貨の中から1つだけ重いについて書かれているパズル本には、残念ながら私はお偽金貨を3回の天秤で見つけ出すことができます。では目にかかった事がありません。そのため、私はずっと消その手順を考えてみましょうか！というと「そういう面化不良状態を起こし続けていました。そして大学に入っ倒なパズルは嫌いだ！」とばかり、うんざりしてこの先て初めてこの問題に回答することができるようになったを読むのをやめててしまう人もいるでしょう。ちょっとのです（もしかしたら普通より遅いのかもしれない）。

待って下さい。実際の手順を考えるには、非常に重要な「この答は3回が最小なのです。そしてこの事実は非常「コツ」があるのです。もう一度先ほどの議論に戻ってに重要な問題を含んでいるのです。」

みましょう。答は2−7個の金貨のうちどれかであり、3回さて、なぜ3回必要なのでしょう？天秤を1回使う

天秤を使うことによって27通りのパターンがあるのですと、「右が重い」、「つりあう」、「左が重い」の3通から、この数はぴったり一致しています。すなわち無駄りの答があります。天秤を2［司使うと、1回目の結果がは絶対に許されないのです。1回目に天秤を使うことに3通りあり、2回目の結果が3通りあり、全体で9通りよって、答は3通りありました。1回目の天秤を使ったの結果があります。すなわちある計り方をした結果、9時の答がなんであろうと、その後もう2回しか天秤は使通りの答を返すことができます。では今の問題についてえないのですから、場合は9通りしか残っていません。ということは、1回目に天秤を使って「右が重い」場合
まついともみ東京大学大学院工学系研究科計数工学専攻

も「つりあう」場合も「左が重い」場合でも、それぞれ〒133東京都文京区本郷7−3−1の場合にどの金貨が重いか9個に絞られる必要がありそ

e−mail：tOmOmi＠misoJlrO．t．u−tOkyo．ac．Jp

うです。とすると、1回目の天秤がたまたま「つりあらまついやすこ東京都立大学理学部数学教室た」場合は1回目に天秤にのせなかった金貨の中に偽金〒192−03東京都八王子市南大沢1−1

貨が混じっているはずですから、天秤にのせない金貨はe−mail：yaSuko＠math・metrO−u．aCJP9個でなければなりません。なるほど！ということは、1回目は天秤の右に9個の金貨をのせ、左にも9個の金1996年3 月号© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

（5）141

貨をのせるしかないわけです（正確にいうならば、もし金貨があるか、右のた個の中に軽い偽金貨がある」こと3回でできるとするならば、これしかないわけです）。

がわかります。そして「つりあった」ならば、「残りのもし1回目で「つりあった」ならば、偽金貨は残りの13−2た個の中に（重いまたは軽い）偽金貨があるか、す9個の中にあります。1回目の天秤で「右（左）が重べて本物」となります。先の議論と同じように、3回のかった」ならば、偽金貨は右（左）にのせた9個の中に天秤を使った結果のパターンが27通りで、答の種類数もあるわけです。ではこの9個の中からどうやって偽金貨27通りですから無駄は許されません。すなわち、1回目を見つけるのでしょう。この時も前と同様▲に、9個のうが終わった時点で答の可能性が9通りに絞られなければ

ちの3個を天秤の右に、3個を左にのせます。もしこのならないのです。もし「右（左）が重かった」ならば答2回目が「つりあった」ならば、偽金貨は残りの3個のは2た通りに絞られ、「つりあった」ならば答は2（13−中にあります。2回目の天秤で「右（左）が重かった」2た）＋1通りに絞られます。ちなみにこれらを全て加える

ならば、やはり偽金貨は右（左）にのせた3個の中にあと、2た＋2た＋2（13−2た）＋1＝27通りになっていまります。最後も同様に、3個のうちの1個を天秤の右すね。さてどの場合でも答が9通りに絞られなければなに、もう1個を左にのせます。天秤のどちらかが下がれらないのですから、2た≦9かつ2（13−2た）＋1≦9ば、そちらが偽金貨、つりあえば最後の1個が偽金貨とが成り立たなければならないのですが、これは成り立ちなるわけです。

ません。なぜならば、2式を整理すると、た＝4．5が導なるほど！毎回天秤を使う毎に、偽金貨の候補が1／3になっていくのですね。だから、3回天秤を使えば27個かれますが、たは金貨の個数なので整数でなければならないからです。ということで、問題2は「できない」が答なのです。の候補が27×（1／3）×（1／3）×（1／3）＝1

訳です。ということわあ‥、8 1個の金貨だったら4回

ちなみに問題2において、本物の金貨と同じ重さであるで、243個の金貨だったら5回で解くことができ、これことが分かっているおもりが1つあれば、天秤を3回使より少ない手数は存在しない訳ですね。

用するだけで質問に答えることができます。興味のある方はチャレンジしてみて下さい。手順を見つけるコツ

3．全部本物？

は、先ほど言ったものと同じです（本文の最後に簡単な次はもうちょっと面倒なパズルを紹介しましょう。

ヒントを付け加えておきましょう。）

問題2 いまここに金貨が13個ある。見た目はす

4．軽い順に並べよう

べてそっくりなのだが、実は1個だけ重さの違う偽金貨が混じっている可能性がある。さて天秤を3回だ・・

さて次はこんな問題を考えてみましょう。

け使って、「偽金貨が混じっていない」のか、あるい

問題3 いまここに金貨が10個ある。見た目はすは「偽金貨を見つけ出し」、それが「重い」のか「軽べてそっくりなのだが、実はみな重さがすこしずつ違い」のかを答えて欲しい。さてこれは可能だろうか？

う。これを重さの軽い順に並べるには、天秤を何回使天秤を使える回数は3回だから、答の通り数は27通りう必要があるか？

まで可能ですね。では問題2の答の通り数は何通りあどうやって解きますか？とても簡単な方法をお教えしるでしょう。「すべて本物」、「1番目が重い」、「2ましょう。まず最初に一番軽い金貨を見つけます。これ番目が重い」、、「13番目が重い」、「1番目が軽には天秤を9回使えば可能です（さてどうやるのでしょい」、、「13番目が軽い」とちゃんと27通りです。

う？）。次にこの1番軽い金貨を取り除いて、残りの9そっか、じゃ大丈夫だ！とは言えません。ここで分かる個の中で最も軽い金貨を見つけます。これは天秤を8回のは、天秤を最低3回は使わなければならないというこ使えば可能です。そしてまた取り除いて、以下同じようとです。では本当に3回でできるのでしょうか？実は答に見つけます。さて天秤は何回使ったのでしょうか？9＋は NO です。1回目の天秤で両側にた個づつ金貨を8＋7＋6＋5＋4＋3＋2＋1＝45回ですね。では問のせたとしましょう。「右が重かった」ならば答の可能

題3をもうちょっと一般化してた個の金貨があったとし性は、「右のた個の中に重い偽金貨があるか、左のた個て考えてみましょう。すると上記の方法で天秤を使う回の中に軽い偽金貨がある」ことがわかります。「左が重数は（た−1）＋（た−2）＋…＋1＝た（た−1）／2回となかった」ならば答の可能性は、「左のた個の中に重い偽りますね。

142（6）© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

オペレーションズ・リサーチさてこれは最小手数でしょうか？そこで、最低でもき軽い方が、全体の中で最も軽い金貨となることは分か何回かかるのか見積もってみましょう。考え方は前と同りますね。例えば第1グループの（中で最も軽い）金貨じものです。すなわち、答の通り数はいったい何通りでが「全体で最も軽い金貨」だと分かったとしましょう。

しょうか？10個の金貨にはaからjまでの名前がついてそうしたら、その金貨を第1グループから取り除き、机いるとすると、答えはaからjまでの名前を1列に並べの上にでも置いておきます。そしてまた、第1グループることに対応します。最初に名前をつけた時は重さにつの金貨の中で最も軽いものと、第2グループの金貨の中いてどう並んでいるか分からないのですから、答の通で最も軽いものを天秤にのせます。このときの軽い方り数はaからjの金貨を1列に並べる順列の数だけ存在の金貨が「全体で2番目に軽い金貨」になります。このするわけです。10個のものを並べる順列の数は10！＝「全体で2番目に軽い金貨」をその所属するグループか3，628，800ですね（ずいぶん大きいな）。では天秤を何ら取り除き、先ほどの「全体で1番軽い金貨」の隣に置回使えばいいでしょう？3回使えば3×3×3 ＝ 27のいておきます。以下同様の手続きを行ない、どちらかの場合があり、4回使えば34 ＝ 81、だから…13回使えグループの金貨がなくなるまで続けます。例えば第1グば313 ＝1，594，323、14回では314 ＝ 4，782，969とループの金貨が無くなったら、残った第2グループ中のなって、どうも14回は必要なようです（なんだ割と少な金貨はそれまでに取り除いた金貨のどれよりも重く、享いや）。先ほどの方法では4早回でしたから、ずいぶん違たこれらの金貨は既に軽い順にならんでいます。ですかいますね。もしかすると、もっと減らせるのかもしれまら、残った金貨を先ほど取り除いて机に並べた金貨の後せん。

ろに続けて並べれば終わりです。いまの手続きでは、1ではこの議論も一般化して、た個の金貨がある時の問回天秤を使うたびに1個の金貨が取り除かれますから、題3を考えてみましょう。すると答の通り数はた！あり最悪でも9回天秤を使えば、金貨は1個になって手続きますね。天秤をp回使うと3Pの場合があります。といは終了します。では、2つのグループの5個の金貨はどうことはた！≦ 3pが成り立たなければならないので、うやって軽い順に並べるのでしょう？これも同様の方法

log3（㍍）≦■pとなります。すなわちlog3（射）回ぐらい天で行ないます。すなわち、金貨2憎からなる第1グルー

秤を使わないといけないようです。

プと金貨3個からなる第2グループに分け、それぞれのでもこの議論はあまりフェアではありません。
だって金貨の重さが本当にばらばらだったら、天秤の左右にどのように金貨をのせても「つりあう」ことなどありっこないのですから。「つりあう」ことがないならば、天秤を1回使う毎に「右が重い」か「左が重い」のどちらの場合が成り立ちます。ゆえに天秤を2回使えば4つの場合が存在し、3回使えば8つの場合が存在し、・、天秤を21回使えば場合は221＝2，097，152、22回使えば222 ＝4，194，303の場合が存在します。10！＝3，628，800だったから、天秤を使う回数は22回くらいは必要かし

グループの金貨を「何らか」の方法で軽い順に並べます。そうしたら、2つのグループの最も軽い金貨同士を天秤で比べ、軽い方を取り除き…（以下続く）。この手続きは、最悪◆でも天秤を4回使えば終了します。では3個の金貨を軽い順に並べるには？これは3回天秤を使えばできますね。2個の金貨でしたら1回天秤を使えばできます。さて全体で何回天秤を使ったでしょう？5個の金貨からなる2つのグループから10個全体を並べるのに9回。2個と3個の金貨からなるグループから5個全体を並べるのに4回、ただし5個のグループは2つあります。3個の金貨を並べるのに3回、ただし3個のグループは2つあります。2個の金貨を並べるのに1回、ただし2個のグループも2つあります。全体で9＋4×2＋3×ら。

2＋1×2＝25回というわけです（25回という数字は最実は天秤を25回使うだけで問題3を解く、驚くべき方法があります（併合整列法と呼ばれる方法です）。それに悪のケースで、もっと早く終わるときもあります）。
ではこの手順も、ちょっと一般化して、た個の金貨がは、まず10個の金貨を5個ずつ二つのグループに分けまある時の問題3を考えてみましょう。といっても手順がす。そして「なんらかの」方法で二つのグループの金貨

大分複雑ですから、kが2のべき乗の時だけ考えてみまを軽い順に並べます（この方法は後で述べます）。さてしょう。例えば金貨の数がた ＝ 24 ＝16個ならば、次第1グループの金貨の中で最も軽いものと、第2グルーのようになります。8個と8個に分けたのをまとめるのプの金貨の中で最も軽いものを天秤にのせます。このと1996年3 月号© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

（7）143

に天秤を15回使う。4個と4個に分けたのをまとめるのとはできないのです。（ただし、本稿に記した問題1やに7回、これが2つ。2個と2個に分けたのをまとめる

問題2を解く算法を計算機上で実行する際は、「天秤にのに3回、これが4つ。2個のものを並べるのに1回、のせる金貨の重さを加え合わせる」等の計算の時間が必

これが8つ。合計で、15＋7×2＋3×4＋1×8＝49回

要ですから、実際の計算時間がもっと速い「計算機上のになります。もした＝2nならば、算法」は他に存在するかもしれません。）たとえその計（2n−1）＋（2n￣1−1）×2＋（2n￣2−1）×22＋‥・＋1×2n−1

算機が、マッキントッシュであろうとIBMであろうとNECであろうとこれは絶対の事実なのです。また未来においてどんな速い計算機が出現しても、これは変わるこ＝（m−1）2n＋1＝（log2た−1）た＋1との無い事実なのです（この事実を越えるためには、計算機の概念が、あるいは「計算」の概念そのものが変わとなります。少し面倒な計算をすると、るしか無いのです）。
（log2た−1）た＋1≦2log3（㍍）そもそも問題1のパズルは、第2次世界大戦の頃ロシアの数学者の間で流行したという話があります（真偽であること一が分かります。すなわち上記の手順は、最小手数を見積もった値の高々2倍程度であることがわかります（上記の「つりあう」が無い状況でしたら、最小手の程は私は知りません）。計算機が本格的に出現したのが、第2次世界大戦において弾道計算をするためであったことを考えると、上記のパズルのよう．な問題の重要性

数の見積もりはlog2岬）となり、が認識されはじめた時期と丁度一致しているのは事実で（log2た−1）た＋1≦1・2log2（か）すね。

が成り立ちます）。まあ、2倍程度なら良いのではないでしょうか。なぜって、最初のた（た−1）／2の手続きはと宿題パズルのヒント

天秤を1回目に使う時、右に金貨をた個のせ、左に金てつもなく多過ぎましたから。以下にちょっと、その違貨た−1個とおもりを1個のせたとしましょう。「右がいを記しておきましょう。

重い」、「つりあう」、「左が重い」のどの場合でも答た log3（か）log2（射）の候補は9通りに絞られなければなりません。まず「右α た（た−1）／242．94．65689．7

15．3 1728

答は「右のた個の金貨の中に本物より重い偽金貨がある

1627．944．3 49120

か、左のた−1個の中に本物より軽い偽金貨がある」とな

3274．2117．7 129496ることがわかります。すなわち答はた＋（た−1）＝2た−1

64186．8296．0 3212016

通りに絞られます。すると2た−1＝9が成り立たなけれ128451．8

716．2 7698128

ばならないので、た＝5でなければなりません。すなわ注）ただし、α＝（log2た−1）た＋1。

が重かった」場合を考えましょう。すると可能性のあるち右に金貨を5個のせ、左に金貨4個とおもりをのせる

表中の数値は小数点以下第1桁までです。のが正しいようです。

ちなみに、残りの状況もチェックしておきましょう。

5． おわりに1回目の天秤で「左が重かった」ならば、「左の4個の金貨のパズルにおいて天秤を何回使うのか？という金貨の中に本物より重い偽金貨があるか、右の5個の金問題を考えて来ましたが、これは計算機の話と密接に貨の中に本物より軽い偽金貨がある」の9通りに絞られ関わっています。例えば上記の問題を計算機に解かせよます。また1回目の天秤で「つりあった」ならば、「天うとしたとき、計算機では2つの数字の大小を比べるこ

秤にのせなかった4個の金貨の中に軽いあるいは重い偽とができますが、これは天秤で重さを比べることに他金貨が含まれているか、金貨はすづて本物」という答になりません。そしてどんな計算機でも、数字の大小比較絞られます。この場合も答はちゃんと4＋4＋1＝9通を3回より少ない回数行なうだけで問題1を解くことはりに絞られていますね。

できないのです。同様に、問題2を3回の大小比較だけでは2回目以降の天秤の使い方を考えてくださいね。

で解くことはできません。そして最後の問題3では、大小比較をlog3（封）より少ない回数で、軽い順に並べるこ144（8）© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

オペレーションズ・リサーチ