目次

  1. 問題
  2. 答え
    1. 平衡 3 進記数法
    2. 一般化
    3. 番号の振り方
    4. コインの乗せ方
    5. 補足
  3. シミュレーション
  4. 関連リンク

1. 問題

ここに同じ種類のコインが 12 枚あります。少なくとも 11 枚は本物ですが、1 枚だけ偽物が混ざっている可能性があります。本物と偽物は外見では見分けることができません。本物はすべて同じ重さで、偽物は本物と重さが異なります。ただし、偽物が本物よりも重いのかそれとも軽いのかはわかりません。天秤を 3 回だけ使って 12 枚のコインの中から偽物を見つけてください。

2. 答え

天秤の傾き方を 1 桁の平衡 3 進数に置き換えて、それを 3 回繰り返してできた 3 桁の平衡 3 進数が偽物のコインの番号です。おわり。(ぉぃ)

この問題は平衡 3 進数を持ち出さなくても解けますが、Mad-P さんが指摘されたように普通の 3 進数で書くよりも平衡 3 進数で書いたほうがわかりやすいと思います。

2.1. 平衡 3 進記数法

10 進数と平衡 3 進数の関係とコインの番号の振り方
10 進数平衡 3 進数11...110??...??コインの番号-
抽出符号反転平衡 3 進数10 進数
0000-0000@
1001-0011A
201-1-01-12B
3010-0103C
4011-0114D
51-1-1-1-1-15E
61-10-1-106F
71-11-1-117G
810-110-1-101-101-8H
9100100-100-100-9I
10101101-10-1-10-1-10J
1111-1-11-111K
12110110-1-10-1-10-12L
合計820410-4-10000-
3k-13k-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 より)

2.2. 一般化

問題のコインの枚数は 12 枚ですが、ここでは天秤を使う回数を N 回としてコインが 3N-32 枚ある場合について考えます。2 回で 3 枚、3 回で 12 枚、4 回で 39 枚、5 回で 120 枚、6 回で 363 枚、7 回で 1092 枚、8 回で 3279 枚、9 回で 9840 枚、10 回で 29523 枚のコインの中から偽物を見つけることができます。

2.3. 番号の振り方

  1. 3N-32 枚のコインに N 桁の平衡 3 進数で 00...001 から 11...110 の通し番号を振ります。
  2. 平衡 3 進数で 11...110??...?? の形の番号を符号反転します。平衡 3 進数の符号反転は各桁ごとに符号反転 (1 を -1 に、-1 を 1 に) するだけです。

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 とします。

このようにして振った番号には以下のような特徴があります。

特徴 1

絶対値が同じ番号のコインは 2 枚以上ありません。正の通し番号を振って一部を符号反転しただけですから当然です。

特徴 2

平衡 3 進数の番号の 1~N 桁目について、それぞれ 1 のコインと -1 のコインが同数ずつあります。すなわち、各桁ごとの合計が 0 になっています。なぜなら、右の表を観察するとわかるように、00...001 から 11...110 の通し番号は各桁ごとの合計が 3k-1 であり、その中の 11...110??...?? の形の番号は各桁ごとの合計が k-1Σi=03i = 3k-12 なので、11...110??...?? の形の番号を符号反転すると各桁ごとの合計がすべて 0 になります。

2.4. コインの乗せ方

n 回目 (n=1~N) に天秤を使うとき、平衡 3 進数の番号の n 桁目が 1 のコインをすべて天秤の左側に、-1 のコインをすべて天秤の右側に乗せます。特徴 2 より、平衡 3 進数の番号の n 桁目が 1 のコインと -1 のコインは同数ずつあるので、乗せたコインがすべて本物ならば天秤は釣り合うはずです。

12 枚の場合は右の表に従って次のようにコインを乗せます。

  1. 1 回目は E、F、G、K を左側に、H、I、J、L を右側に乗せる。
  2. 2 回目は B、C、D、K を左側に、E、F、G、L を右側に乗せる。
  3. 3 回目は A、D、G、H を左側に、B、E、J、K を右側に乗せる。

n 回目 (n=1~N) の天秤の傾き方から、偽物のコインが本物よりも重い場合と軽い場合について、偽物のコインの平衡 3 進数の番号の n 桁目がわかります。

偽物のコインが本物よりも重い場合と軽い場合について、絶対値が同じで符号だけが異なる 2 つの番号が求まります。特徴 1 より、絶対値が同じ番号のコインは 2 枚以上ないので、これで偽物のコインが特定され、同時にそれが本物よりも重いのかそれとも軽いのかということもわかります。N 回すべて釣り合ったときは 0 番のコインが偽物ということになりますが、0 番のコインは存在しないのでコインはすべて本物です。

2.5. 補足

偽物のコインが必ず 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 番が偽物だった場合はそれが本物よりも重いのかそれとも軽いのかということはわかりません。

3. シミュレーション

JavaScript を使って天秤に乗せるコインの番号を表示します。コインの枚数と天秤の傾き方を選択すると偽物のコインの番号が表示されます。符号は省略します。

4. 関連リンク


更新履歴

2015 年 9 月 7 日

日記に書いた偽物のコインの関連記事を書き直して http://stdkmd.com/fakecoin/ で公開しました。

── 続きを読む ──── 続きを隠す ──

2004 年 12 月 6 日

2004 年 12 月 6 日の日記 で解き方を自動生成するプログラムを公開しました。

2001 年 12 月 26 日

2001 年 12 月 26 日の日記 にコインの番号の振り方の補足を書きました。

2001 年 11 月 16 日

Mad-P さん のご指名を受けて 2001 年 11 月 16 日の日記 に平衡 3 進数を使った解き方を書きました。