問題. 12 枚の金貨があり、 1 枚だけは重さが違う。 てんびんを 3 回だけ使ってその金貨を見つけ出せ。
これは古くからある問題のようであるが、 2001 年十二月ごろ奥村晴彦氏のページでまた話題になった。 私は、このようなパズルは苦手であり、 個数や回数の特殊性を使って解くのであればあまり興味がわかないのだが、 インターネットにおける解答のありかなども書き込まれていたので見たところ、 その一つに 「解があれば『より重い』か『より軽い』かまでわかる」 と私には解釈できるような説明があった。 本当だろうか、と考えているうち、 12 枚に限らず一般の場合もわかったので、ここにまとめてみた。
なお、奥村氏は「12 枚の硬貨」としていた。 勝手に「金貨」に変えてしまったのは私である。
問題 (k, n). k は 3 以上の整数、n は正の整数とする。 k 枚の金貨があり、 そのうちの k-1 枚は同じ重さであるが残りの 1 枚は重さが違う。 ほかにてんびんがあり、 左右の皿に何枚かの金貨を乗せて 「左のほうが重い」か「同じ重さである」か「右のほうが重い」 かを知ることができる。 このてんびんを n 回だけ使って重さの違う金貨を見つけ出せ。 金貨は、 皿に乗せたり皿から降ろしたりしているうちにどれがどれだかわからなくなりはしない、 と仮定する。
答え. 正の整数 n が n-1 < log3(2k + 1) <= n すなわち (3n-1 - 1) / 2 < k <= (3n - 1) / 2 を満たすとき、問題 (k,n) には解が存在する。 問題 (k,n-1) には存在しない。 等号が成り立たないときは重さの違う金貨が「より重い」のか 「より軽い」のかまでわかる解が存在する。
いくつかの n に対する (3n - 1) / 2 の値は下の表のようになる。
| n | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|---|
| (3n - 1) / 2 | 0 | 4 | 13 | 40 | 121 | 364 | 1093 |
1 枚だけ重さの違う金貨を「求める金貨」、 それ以外の金貨を「普通の金貨」、 てんびんの左右の皿に何枚かの金貨を乗せて結果を知る行為を 「比較」と呼ぼう。
金貨に 1, 2, ..., k と番号を振る。 たとえば左の皿に金貨 1, 2, 3 を、 右の皿に金貨 4, 5, 6 を乗せて比較することを {1,2,3|4,5,6} と書く。 比較の結果によって次にてんびんの皿に乗せるべき金貨は変わってくるから、 解は比較を行なうごとに三つに分岐する「三分木」として書き表せる。 分岐点では
+- ありえない
+- {2|3} -+- 4 が軽い
| +- 3 が重い
|
| +- 2 が重い
{3|4} -+- {2|3} -+- 1 が違う
| +- 2 が軽い
|
| +- 3 が軽い
+- {2|3} -+- 4 が重い
+- ありえない
「ありえない」と記したところに到達することはありえない。
「1 が違う」には、
「1 が重い」場合も「1 が軽い」場合も到達する。
これらの「ありえない」「1 が違う」「2 が重い」「2 が軽い」などを 「結論」と呼ぶことにしよう。
次は問題 (8,3) の解の一つである。
+-
+---------+- 8 が重い
| +-
|
| +- 7 が軽い
+- {3,8|2,4} -+- {5|7} -+- 6 が重い
| | +- 5 が軽い
| |
| | +- 4 が重い
| +- {4|2} -+- 3 が軽い
| +- ありえない
|
| +-
| +---------+- 2 が重い
| | +-
| |
| | +- 1 が重い
{4,6,8|3,5,7} -+- {2|3} -----+- {1|2} -+- ありえない
| | +- 1 が軽い
| |
| | +-
| +---------+- 2 が軽い
| +-
|
| +- ありえない
| +- {4|2} -+- 3 が重い
| | +- 4 が軽い
| |
| | +- 5 が重い
+- {3,8|2,4} -+- {5|7} -+- 6 が軽い
| +- 7 が重い
|
| +-
+---------+- 8 が軽い
+-
この例で、「8 が重い」には 2 回の比較で到達している。 3 回目は比較を行なわなかったので、 そこには「{ }」を書かず
+-
+---------+- 8 が重い
+-
としておいた。
三つに分かれるように書いたのは形を整えるためである。
ここに、意味のない比較を挿入することも可能である。 例えば
+- 8 が重い
+- {5,6|8} -+- 8 が重い
+- 8 が重い
とするなどである。
ここでどちらへ分岐するかは、
金貨 8 の重さと金貨 5, 6 を合わせた重さとの関係による。
正しい解であるならば、 求める金貨と普通の金貨との重さの違いがごくわずかの金貨セットについても正しい結論に到達する。 よって、異なる枚数の金貨を比較するところでは無条件に 「枚数の多いほうが重い」として先へ進んでも正しい結論に到達する。 ゆえに、その比較を解から取り去ることができる。 これで次が証明できた。
| 補題 A. もしも問題 (k, n) に解が存在するなら、 異なる枚数の金貨を比較することのない解も存在する。 |
以下では、異なる枚数の金貨を比較することのない解だけを考えよう。
毎回てんびんがつりあった場合の結論は、 そこまでに一度も皿に乗っていない金貨についての 「〜が違う」か、「ありえない」である。 「〜が重い」「〜が軽い」はありえない。 その金貨がより重くてもより軽くてもその結論に到達するからである。
それ以外の場所に書かれる結論は「〜が重い」「〜が軽い」か、 「わからない」である。「〜が違う」はありえない。 てんびんは少なくとも一度は傾いた。 そのとき、結論が言及している金貨はどちらかの皿に乗っているはずであり、 乗った皿のほうが重かったか軽かったかによって 「〜が重い」「〜が軽い」かが決まる。
異なる枚数の金貨を比較することのない解で、 「ありえない」以外の同一の結論が二箇所以上に書かれていたとしよう。 それは「〜が重い」か「〜が軽い」である。 たとえば「1 が重い」が二箇所にあったとしよう。 二組の金貨セットで、どちらも「1 が重い」のだが、 一方のセットではこちらの「1 が重い」に、 他方のセットでは別の「1 が重い」に到達するものがあるはずである。 それらのセットをこの図式にそっててんびんで比較してゆくとき、 両者のたどる道はどこかの比較で分岐する。 その比較では、金貨 1 が皿に乗っていればそちらが重くなり、 乗っていなければつりあうのであるから、分岐することはありえない。 「〜が軽い」の場合も同様である。 これは矛盾。 よって、次が証明された。
| 補題 B. 異なる枚数の金貨を比較することのない解では、 「ありえない」以外の結論はすべて互いに異なる。 |
問題 (k, n) に解が存在したとする。 結論の書かれる位置は 3n 箇所以下である。 すべての金貨について結論「〜が重い」「〜が軽い」が書かれていれば 2k <= 3n が成り立ち、 1 枚の金貨については結論「〜が違う」が、残りの金貨については 結論「〜が重い」「〜が軽い」が書かれていれば 2k - 1 <= 3n が成り立つ。 いずれにせよ、2k - 1 <= 3n である。
もしも 2k - 1 = 3n の場合に解が存在したとしよう。 その解の結論には、 1 枚の金貨については「〜が違う」が、残りの金貨については 「〜が重い」「〜が軽い」が書かれており、 「ありえない」は書かれていない。 「〜が違う」は毎回てんびんがつりあった場合の結論であった。 補題 A により、 一度目の比較では左右の皿に同数の金貨を乗せたとしてよい。 それらの中に求める金貨が含まれている場合、 またその場合に限って、上下に進む。 上下に進んだ先の結論の数は 2 * 3n-1 だから奇数の 2 倍である。 一方、 そこには一度目に乗せた偶数枚の金貨について結論 「〜が重い」「〜が軽い」が重複なく書かれているのであるから、 それらの数は偶数の 2 倍でなければならない。 これは矛盾である。 よって、2k - 1 = 3n は成り立たない。 2k - 1 < 3n であり、 両辺は奇数であるから実は 2k + 1 <= 3n が成り立っている。 これで次が証明できた。
| 補題 C. 問題 (k, n) に解があるならば 2k + 1 <= 3n すなわち k <= (3n - 1) / 2 が成り立つ。 |
ここで等号の成り立つ場合、結論は
| 補題 D. 2k + 1 = 3n すなわち k = (3n - 1) / 2 の場合の解では、 1 枚の金貨については 「より重い」のか「より軽い」のか判明しない。 |
何回かの比較のあとでは、 「もしもこれが重さの違う金貨であるなら『より重い』」 「もしもこれが重さの違う金貨であるなら『より軽い』」 とわかることがある。 それらの金貨にはそれぞれ「重いかも」「軽いかも」の「目印」をつける。 普通の金貨であるとわかった金貨には「普通」の「目印」をつける。 上の条件を満たさないものに目印をつけてはならない。 ここで「目印」と言ったらこれらの意味に限る。 目印には重さはないものとする。
目印について正確に述べようとすれば、次のようになろう。
| 目印 | 意味 | 記号 | 略記 |
|---|---|---|---|
| なし | 重いかもしれないし軽いかもしれない | +- | ? |
| 「重いかも」 | 重いかもしれないが軽いことはない | +0 | + |
| 「軽いかも」 | 軽いかもしれないが重いことはない | 0- | - |
| 「普通」 | 重いことも軽いこともない | 00 | 0 |
これらの目印は実は 2 つの目印の組み合わせと考えるほうが便利である。 それを「記号」に書いておいた。 「略号」は考えながら三分木を書く際のメモなどに使うと便利である。
比較を行なう前には、どの金貨にも "+-" がついている。 同じ枚数の金貨をてんびんで比較し、
以下で、補題 C の不等式を満たす場合の解を構成する。
その前に、あらすじを述べておこう。 金貨を三等分する --- といっても枚数が 3 の倍数でなければ不可能だが、 あらすじなのでこうしておく。 その一つをとりのけておき、のこりの二つをてんびんで比較する。
最初：？？？？？？？？？？？？？？？？？？ あと：＋＋＋＋＋＋−−−−−−００００００「重いかも」と「軽いかも」をそれぞれ三等分する。 そして、 「重いかも」の三分の一と「軽いかも」の三分の一を一方の皿に、 「重いかも」の別の三分の一と「軽いかも」の別の三分の一をもう一方の皿に乗せる。
＋＋ −− ＋＋ −− ＼＿＿＿＿＿／ ＼＿＿＿＿＿／ ｜ ｜ ＋−−−△−−−＋
実際には枚数に半端が出るので以下のように少々複雑になる。
| 補題 X. n は 0 以上の整数とする。 何回かの比較を行なったのち、 目印のない金貨はなく、 目印「重いかも」のついた金貨の枚数と 目印「軽いかも」のついた金貨の枚数の和 k が k <= 3n を満たしていたとする。このとき、 てんびんをあと n 回だけ使って求める金貨を見つけ出すことができる。 |
証明： n = 0 のときは k = 1 であり、すでに判定が終わっている。
n >= 1 のときを考える。 k = 1 のときはすでに判定が終わっている。 k = 2 のときは、目印「重いかも」または「軽いかも」のついた金貨の 1 枚を目印「普通」のついた金貨の 1 枚と比較すればよい。
以下、k >= 3 とする。 目印「重いかも」「軽いかも」のついた金貨を“ほぼ三等分”する。すなわち、 k = 3j, 3j+1, 3j+2 （j は正の整数）のどれが成り立つかに従って
| k | 3j | 3j+1 | 3j+2 |
|---|---|---|---|
| 第一群 | j 個 | j+1 個 | j 個 |
| 第二群 | j 個 | j 個 | j+1 個 |
| 第三群 | j 個 | j 個 | j+1 個 |
第二群と第三群とをてんびんで比較する。
［証明了］
| 補題 Y. n は 0 以上の整数とする。 何回かの比較を行なったのち、 目印「普通」のついた金貨が少なくとも 1 枚あり、 目印「普通」のない金貨の枚数 k が k <= (3n + 1) / 2 を満たしていたとする。 このとき、 てんびんをあと n 回だけ使って重さの違う金貨を見つけ出すことができる。 等号が成り立たない場合には、 全ての金貨について「より重い」か「より軽い」かまで判明するやり方が存在する。 |
証明： n = 0 のときは k = 1 であり、等号が成立している。 この場合、主張は正しい。
n >= 1 とする。 3n-1以下でありかつ k 以下である奇数のうちもっとも大きなものをとる。 3n-1 も k も正の整数だからこの奇数も正である。 目印「普通」のない金貨を次のようにして三つの群に分ける。 すなわち、この奇数に等しい枚数だけを選び出し、 第二群のほうが第三群より 1 枚だけ多くなるように第二群と第三群とに分け、 残りを第一群とする。
第二群と、 第三群に目印「普通」のついた金貨を 1 枚だけ加えたものとをてんびんで比較する。
［証明了］
注意： 補題 Y の仮定の元で、 目印「普通」のない全ての金貨に対し「より重い」か「より軽い」 かまで判明する解があったとすると、 全部で 2k 通り以上の結論に至ることになる。 分岐先の総数は 3n なので、 等号が成り立つ場合にはそれは不可能である。 その場合、上のやり方では、 最後までてんびんがつりあい続けるケースが 「より重い」か「より軽い」かの判明しないケースとなる。 等号が成り立たない場合は、この補題をくり返し使っているうちに第一群が空 （くう）となり、全ての金貨について「より重い」か「より軽い」 かが判明する。
参考：
| n | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|---|---|
| (3n + 1) / 2 | 1 | 2 | 5 | 14 | 41 | 122 | 365 | 1094 |
| 定理 Z. n は 2 以上の整数とする。 3 以上の整数 k が k <= (3n - 1) / 2 を満たしていれば、 問題 (k,n) には解が存在する。 等号が成り立たない場合には、 全ての金貨について「より重い」か「より軽い」かまで判明するやり方が存在する。 |
証明： 3n-1 - 1 以下でありかつ k 以下である偶数のうちもっとも大きなものをとる。 3n-1 - 1 >= 2 かつ k >= 3 だからこの偶数は 2 以上である。 この偶数に等しい枚数の金貨を取り分け、 半分ずつに分けたものを第二群、第三群とする。 残りを第一群とする。
第二群と第三群とをてんびんで比較する。
［証明了］