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克的物件放置於一個天平的右邊, 如何把上述砝碼置於天平之上, 才可以令天平的左、右平衡?

參考文獻

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