31408 假幣問題及其解法
假幣問題及其解法

1. 引言

所謂「假幣問題」(又稱「12錢幣問題」), 是指有12枚錢幣, 其中有一枚是假幣, 它與真幣的形狀相同, 但重量不相同。如果容許以天平稱量3次, 但不可使用砝碼, 怎樣可判別出哪一枚才是假幣? 並確定它比真幣較重還是較輕?

這是一個經典的數學謎題, 曾在Beasley(1990)及趙文敏(1995)所著的趣味數學書中介紹過, 其本質與Bundy(1996)所討論的Odd Ball Problem屬同類問題, 但三人的解法不一樣。 本文將介紹另一種簡單的解法, 讀者只須對3進制有基本的認識便可以理解。

2. 解法及其原理

要找出那一枚是假幣, 可採用以下的步驟進行:

  1. 首先, 以整數1至12為每個錢幣編上一個互不相同的號碼。
  2. 然後, 把每個編號化成3進制, 並以 $-1$, 0 或 1表示每個位出現的數值。 如下所示: $$ \begin{array}{ll} 1 = (0, 0, 1)_3 & \hskip 1cm 7 = (1, -1, 1)_3 \\ 2 = (0, 1, -1)_3 & \hskip 1cm 8 = (1, 0, -1)_3 \\ 3 = (0, 1, 0)_3 & \hskip 1cm 9 = (1, 0, 0)_3 \\ 4 = (0, 1, 1)_3 & \hskip 1cm 10 = (1, 0, 1)_3 \\ 5 = (1, -1, -1)_3 & \hskip 1cm 11 = (1, 1, -1)_3 \\ 6 = (1, -1, 0)_3 & \hskip 1cm 12 = (1, 1, 0)_3 \end{array} $$
  3. 接著, 把這些3進制的數值, 從右至左, 看成是每次秤量時擺放在天平上的位置: 1表示放置於左邊, $-1$ 表示放置於右邊, 而0表示兩邊都不放置。 那麼, 可以初步得出錢幣的擺放位置如下:
    秤量次序 置於左邊的錢幣 置於右邊的錢幣
    第三次 5, 6, 7, 8, 9, 10, 11, 12
    第二次 2, 3, 4, 11, 12 5, 6, 7
    第一次 1, 4, 7, 10 2, 5, 8, 11
  4. 由於此時在天平的左、右所放置的錢幣數目不相同, 所以需要把某些錢幣的位置變動一下。 怎樣進行呢? 我們可以把整數1至12的3進制表示法以直列的方式記錄, 觀察每一橫行中1與 $-1$ 的數目是否相同, 然後作一些適當的變動。如下表所示:
    錢幣 1 2 3 4 5 6 7 8 9 10 11 12
    高行 0 0 0 0 1 1 1 1 1 1 1 1
    中行 0 1 1 1 -1 -1 -1 0 0 0 1 1
    低行 1 -1 0 1 -1 0 1 -1 0 1 -1 0
可以看到, 中行和高行中出現的1過多。我們可以選擇把某些直行中的數字的正、負號由正變負, 或由負變正, 使得在高、中、低行中出現的 1 與 $-1$ 的數目相等。 譬如, 如果把直行 7, 9, 11, 12 中的數字的正、負號改變, 則表中的數值會變成:
錢幣 1 2 3 4 5 6 7$^*$ 8 9$^*$ 10 11$^*$ 12$^*$
高行 0 0 0 0 1 1 -1 1 -1 1 -1 -1
中行 0 1 1 1 -1 -1 1 0 0 0 -1 -1
低行 1 -1 0 1 -1 0 -1 -1 0 1 1 0
(註: 有 $^*$ 號的數字是指曾被改動過正、負的數字。) 此時, 每一橫行中的1與 $-1$ 的數目都各有4個 1 1 若改動其他數字的話, 也可以產生相同效果。例如, 把3, 6, 8, 10, 12都改成負數的話, 則每一橫行中出現的1與 $-1$ 的數目也會相等, 讀者不妨驗證一下。 , 從而讓我們確定了每個錢幣最終的擺放位置如下:
秤量次序 置於左邊的錢幣 置於右邊的錢幣
第三次 5, 6, 8, 10 7*, 9*, 11*, 12*
第二次 2, 3, 4, 7* 5, 6, 11*, 12*
第一次 1, 4, 10, 11* 2, 5, 7*, 8

由於在每次秤量中, 天平的狀態只有三種, 分別是「左重」(L)、「右重」(R)或「平衡」(#), 而秤量的結果一定不會出現「三次皆平衡」、「三次皆左重」或「三次皆右重」 2 2 由於存在有一假幣, 故不可能出現「三次平衡」。 另外, 由於沒有任何一個錢幣在每次秤量中都置於同一邊(參看錢幣的擺放位置), 所以亦不會出現「三次左重」或「三次右重」的情況。 的情況, 所以不同秤量結果的數目是: $3\times 3\times 3-3=24$。 如果我們把L、R與 # 分別跟1, $-1$ 與 0 作「一一對應」的話, 那麼透過3進制的表示, 我們便可以知道何者是假幣, 以及知道它比真幣較輕還是較重。 為甚麼呢? 我們不妨用一個簡單的例子加以說明: 假設錢幣6是一個假幣, 而且它比真幣較重。 由於它在秤量時的罷放位置是以 $(1, -1, 0)$ 來表示, 故其稱量結果將會是(L, R, #)。 反過來說, 如果稱量的結果是(L, R, #), 它的3進制表示 $(1, -1, 0)$ 會唯一地 3 3 因為每個錢幣的擺放位置之3進制表示各不相同, 故此種對應唯一的。 確定了假幣的編號是6, 而且由於天秤下墜的方向與它在天秤出現的位置是一致的, 所以知道它比真幣較重。 另外, 如果錢幣6是一個假幣, 而它比真幣較輕。 因為它在秤量時的罷放位置是以 $(1, -1, 0)$ 來表示, 故其稱量結果將會是(R, L, #)。 反過來說, 如果稱量的結果是(R, L, #), 它的3進制表示 $(-1, 1, 0)$ 4 4 注意: $(-1, 1, 0)=-(1, -1, 0)$。 會唯一地確定了假幣的編號是6, 而且由於天秤下墜的方向與它在天秤出現的位置是相反的, 所以知道它比真幣較輕。

應用類似上述的分析, 我們可以對所有可能出現的結果作以下的結論:

天秤下墜
的方向
天秤下墜
方向的3
進制表示
天秤下墜
方向的10
進制表示
結論






1 # # L (0, 0, 1) 1 假幣是1號, 它比真幣較重。
2 # # R (0, 0, -1) -1 假幣是1號, 它比真幣較輕。
3 # L R (0, 1, -1) 2 假幣是2號, 它比真幣較重。
4 # R L (0, -1, 1) -2 假幣是2號, 它比真幣較輕。
5 # L # (0, 1, 0) 3 假幣是3號, 它比真幣較重。
6 # R # (0, -1, 0) -3 假幣是3號, 它比真幣較輕。
7 # L L (0, 1, 1) 4 假幣是4號, 它比真幣較重。
8 # R R (0, -1, -1) -4 假幣是4號, 它比真幣較輕。
9 L R R (1, -1, -1) 5 假幣是5號, 它比真幣較重。
10 R L L (-1, 1, 1) -5 假幣是5號, 它比真幣較輕。
11 L R # (1, -1, 0) 6 假幣是6號, 它比真幣較重。
12 R L # (-1, 1, 0) -6 假幣是6號, 它比真幣較輕。
13 R L R (-1, 1, -1) -7 假幣是7號, 它比真幣較重。
14 L R L (1, -1, 1) 7 假幣是7號, 它比真幣較輕。
15 L # R (1, 0, -1) 8 假幣是8號, 它比真幣較重。
16 R # L (-1, 0, 1) -8 假幣是8號, 它比真幣較輕。
17 R # # (-1, 0, 0) -9 假幣是9號, 它比真幣較重。
18 L # # (1, 0, 0) 9 假幣是9號, 它比真幣較輕。
19 L # L (1, 0, 1) 10 假幣是10號, 它比真幣較重。
20 R # R (-1, 0, -1) -10 假幣是10號, 它比真幣較輕。
21 R R L (-1, -1, 1) -11 假幣是11號, 它比真幣較重。
22 L L R (1, 1, -1) 11 假幣是11號, 它比真幣較輕。
23 R R # (-1, -1, 0) -12 假幣是12號, 它比真幣較重。
24 L L # (1, 1, 0) 12 假幣是12號, 它比真幣較輕。

由這個表可見, 如果把秤量結果的3進制表示化成10進之後, 它的絕對值便是假幣的編號。 另外, 如果所得的10進數是 1, 2, 3, 4, 5, 6, $-7$, 8, $-9$, 10, $-11$ 或 $-12$ 的話, 是代表假幣比真幣較重。 反之, 如果所得出的10進數是 $-1$, $-2$, $-3$, $-4$, $-5$, $-6$, 7, $-8$, 9, $-10$, 11 或 12 的話, 是代表假幣比真幣較輕。換言之, 秤量結果的10進制表示, 除了是 $\pm 7$, $\pm 9$, $\pm 11$ 及 $\pm 12$ 是例外, 其他所得數值的正、負號正好對應著假幣是「較重」或「較輕」的情況。 有了這種認知, 會有助於我們快速和正確地判斷出何者是假幣, 以及知道它比真幣較輕還是較重, 而不需要利用上表去查看結果。以下是一些具體的示例:

例一: 假設秤量所得的結果是: 第一次是左重、第二次是右重, 而第三次是平衡。 它對應的3進數是 $(0, -1, 1)_3=0\times 9+(-1)\times 3+1=-2$。 由此可知錢幣2是假幣, 它比真幣較輕。

例二: 假設秤量所得的結果是: 第一次是右重、第二次是平衡, 而第三次是左重。 它對應的3進數是 $(1, 0, -1)_3=1\times 9+0\times 3-1=8$。 由此可知錢幣8是假幣, 它比真幣較重。

例三: 假設秤量所得的結果是: 第一次是左重、第二次是右重, 而第三次是左重。 它對應的3進數是 $(1, -1, 1)_3=1\times 9+(-1)\times 3+1=7$。 由此可知錢幣7是假幣, 它比真幣較輕。

3. 結語及其他問題

總括而言, 本文所介紹的方法, 是運用了整數的3進制表示的唯一性。 解法簡單, 而且其思維方式可以應用到其他類似的數學問題上去。 譬如, 以下的兩個問題, 都可以運用3進制的方法求解 5 5 兩題的答案如下: 問題一: 1磅, 3磅, 9磅, 27磅。 問題二: 將1克與81克的砝碼置於右邊, 其餘的置於左邊。 , 讀者不妨動手一試:

問題一: 如果只可以用4塊不同重量的砝碼, 去秤出由1至40磅中各不同的整數重量, 問該4塊砝碼的重量應分別是多少?

問題二: 有1克, 3克, 9克, 27克, 81克和243克的砝碼各一個。 如果把一件重200克的物件放置於一個天平的右邊, 如何把上述砝碼置於天平之上, 才可以令天平的左、右平衡?

參考文獻

J. Beasley (1990), The Mathematics of Games. Oxford University Press. B. Bundy (1996), The Odd Ball Problem, Mathematical Spectrum, 26, 14-15. 趙文敏 (1995), 寓數學於遊戲, 第一輯, 九章出版社。

---本文作者現任教於香港教育學院數社科技學系---