ここに同じ種類のコインが 12 枚あります。少なくとも 11 枚は本物ですが、1 枚だけ偽物が混ざっている可能性があります。本物と偽物は外見では見分けることができません。本物はすべて同じ重さで、偽物は本物と重さが異なります。ただし、偽物が本物よりも重いのかそれとも軽いのかはわかりません。天秤を 3 回だけ使って 12 枚のコインの中から偽物を見つけてください。
天秤の傾き方を 1 桁の平衡 3 進数に置き換えて、それを 3 回繰り返してできた 3 桁の平衡 3 進数が偽物のコインの番号です。おわり。(ぉぃ)
この問題は平衡 3 進数を持ち出さなくても解けますが、Mad-P さんが指摘されたように普通の 3 進数で書くよりも平衡 3 進数で書いたほうがわかりやすいと思います。
| 10 進数 | 平衡 3 進数 | 11...110??...?? | コインの番号 | - | |||||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 抽出 | 符号反転 | 平衡 3 進数 | 10 進数 | ||||||||||||||||||
| 0 | 0 | 0 | 0 | - | 0 | 0 | 0 | 0 | @ | ||||||||||||
| 1 | 0 | 0 | 1 | - | 0 | 0 | 1 | 1 | A | ||||||||||||
| 2 | 0 | 1 | -1 | - | 0 | 1 | -1 | 2 | B | ||||||||||||
| 3 | 0 | 1 | 0 | - | 0 | 1 | 0 | 3 | C | ||||||||||||
| 4 | 0 | 1 | 1 | - | 0 | 1 | 1 | 4 | D | ||||||||||||
| 5 | 1 | -1 | -1 | - | 1 | -1 | -1 | 5 | E | ||||||||||||
| 6 | 1 | -1 | 0 | - | 1 | -1 | 0 | 6 | F | ||||||||||||
| 7 | 1 | -1 | 1 | - | 1 | -1 | 1 | 7 | G | ||||||||||||
| 8 | 1 | 0 | -1 | 1 | 0 | -1 | -1 | 0 | 1 | -1 | 0 | 1 | -8 | H | |||||||
| 9 | 1 | 0 | 0 | 1 | 0 | 0 | -1 | 0 | 0 | -1 | 0 | 0 | -9 | I | |||||||
| 10 | 1 | 0 | 1 | 1 | 0 | 1 | -1 | 0 | -1 | -1 | 0 | -1 | -10 | J | |||||||
| 11 | 1 | 1 | -1 | - | 1 | 1 | -1 | 11 | K | ||||||||||||
| 12 | 1 | 1 | 0 | 1 | 1 | 0 | -1 | -1 | 0 | -1 | -1 | 0 | -12 | L | |||||||
| 合計 | 8 | 2 | 0 | 4 | 1 | 0 | -4 | -1 | 0 | 0 | 0 | 0 | - | ||||||||
| 3k-1 | 3k-12 | -3k-12 | すべて 0 | ||||||||||||||||||
平衡 3 進記数法は 3 進記数法と同じ基数 3 の記数法です。違うところは、3 進記数法が 0、1、2 という 3 つの数字を使って数を表すのに対して、平衡 3 進記数法は -1、0、1 の 3 つを使います。右の表で 10 進数と平衡 3 進数の対応を確認してみてください。
Knuth 先生いわく、「おそらく、すべての記数法の中で最も美しいのは平衡 3 進表示である」
(Donald E. Knuth 著、中川圭介訳、『KNUTH THE ART OF COMPUTER PROGRAMMING 第 4 分冊 準数値算法／算術演算』p14 より)
問題のコインの枚数は 12 枚ですが、ここでは天秤を使う回数を N 回としてコインが 3N-32 枚ある場合について考えます。2 回で 3 枚、3 回で 12 枚、4 回で 39 枚、5 回で 120 枚、6 回で 363 枚、7 回で 1092 枚、8 回で 3279 枚、9 回で 9840 枚、10 回で 29523 枚のコインの中から偽物を見つけることができます。
12 枚の場合は右の表のように 8、9、10、12 を符号反転して A=1、B=2、C=3、D=4、E=5、F=6、G=7、H=-8、I=-9、J=-10、K=11、L=-12 とします。
このようにして振った番号には以下のような特徴があります。
絶対値が同じ番号のコインは 2 枚以上ありません。正の通し番号を振って一部を符号反転しただけですから当然です。
平衡 3 進数の番号の 1～N 桁目について、それぞれ 1 のコインと -1 のコインが同数ずつあります。すなわち、各桁ごとの合計が 0 になっています。なぜなら、右の表を観察するとわかるように、00...001 から 11...110 の通し番号は各桁ごとの合計が 3k-1 であり、その中の 11...110??...?? の形の番号は各桁ごとの合計が k-1Σi=03i = 3k-12 なので、11...110??...?? の形の番号を符号反転すると各桁ごとの合計がすべて 0 になります。
n 回目 (n=1～N) に天秤を使うとき、平衡 3 進数の番号の n 桁目が 1 のコインをすべて天秤の左側に、-1 のコインをすべて天秤の右側に乗せます。特徴 2 より、平衡 3 進数の番号の n 桁目が 1 のコインと -1 のコインは同数ずつあるので、乗せたコインがすべて本物ならば天秤は釣り合うはずです。
12 枚の場合は右の表に従って次のようにコインを乗せます。
n 回目 (n=1～N) の天秤の傾き方から、偽物のコインが本物よりも重い場合と軽い場合について、偽物のコインの平衡 3 進数の番号の n 桁目がわかります。
偽物のコインが本物よりも重い場合と軽い場合について、絶対値が同じで符号だけが異なる 2 つの番号が求まります。特徴 1 より、絶対値が同じ番号のコインは 2 枚以上ないので、これで偽物のコインが特定され、同時にそれが本物よりも重いのかそれとも軽いのかということもわかります。N 回すべて釣り合ったときは 0 番のコインが偽物ということになりますが、0 番のコインは存在しないのでコインはすべて本物です。
偽物のコインが必ず 1 枚あるとわかっている場合は、0 番を使うことで 3N-12 枚 (2 回で 4 枚、3 回で 13 枚、4 回で 40 枚、5 回で 121 枚、6 回で 364 枚、7 回で 1093 枚、8 回で 3280 枚、9 回で 9841 枚、10 回で 29524 枚) のコインの中から偽物のコインを見つけることができます。N 回すべて釣り合ったときは 0 番のコインが偽物です。0 番のコインは 1 度も天秤に乗せていないので 0 番が偽物だった場合はそれが本物よりも重いのかそれとも軽いのかということはわかりません。
JavaScript を使って天秤に乗せるコインの番号を表示します。コインの枚数と天秤の傾き方を選択すると偽物のコインの番号が表示されます。符号は省略します。
https://stdkmd.net/fakecoin/ に引っ越しました。
── 続きを読む ──── 続きを隠す ──
日記に書いた偽物のコインの関連記事を書き直して http://stdkmd.com/fakecoin/ で公開しました。
2004 年 12 月 6 日の日記 で解き方を自動生成するプログラムを公開しました。
2001 年 12 月 26 日の日記 にコインの番号の振り方の補足を書きました。
Mad-P さん のご指名を受けて 2001 年 11 月 16 日の日記 に平衡 3 進数を使った解き方を書きました。