|
假幣問題及其解法
假幣問題 整數的3進制 砝碼組合
1. 引言所謂「假幣問題」(又稱「12錢幣問題」), 是指有12枚錢幣, 其中有一枚是假幣, 它與真幣的形狀相同, 但重量不相同。如果容許以天平稱量3次, 但不可使用砝碼, 怎樣可判別出哪一枚才是假幣? 並確定它比真幣較重還是較輕? 這是一個經典的數學謎題, 曾在Beasley(1990)及趙文敏(1995)所著的趣味數學書中介紹過, 其本質與Bundy(1996)所討論的Odd Ball Problem屬同類問題, 但三人的解法不一樣。 本文將介紹另一種簡單的解法, 讀者只須對3進制有基本的認識便可以理解。 2. 解法及其原理要找出那一枚是假幣, 可採用以下的步驟進行: - 首先, 以整數1至12為每個錢幣編上一個互不相同的號碼。
- 然後, 把每個編號化成3進制, 並以 −1−1, 0 或 1表示每個位出現的數值。 如下所示:
1=(0,0,1)3 7=(1,−1,1)3 2=(0,1,−1)3 8=(1,0,−1)3 3=(0,1,0)3 9=(1,0,0)3 4=(0,1,1)3 10=(1,0,1)3 5=(1,−1,−1)3 11=(1,1,−1)3 6=(1,−1,0)3 12=(1,1,0)3"
接著, 把這些3進制的數值, 從右至左, 看成是每次秤量時擺放在天平上的位置: 1表示放置於左邊, −1−1 表示放置於右邊, 而0表示兩邊都不放置。 那麼, 可以初步得出錢幣的擺放位置如下:[td]| 秤量次序 | 置於左邊的錢幣 | 置於右邊的錢幣 | | 第三次 | 5, 6, 7, 8, 9, 10, 11, 12 | | | 第二次 | 2, 3, 4, 11, 12 | 5, 6, 7 | | 第一次 | 1, 4, 7, 10 | 2, 5, 8, 11 |
- 由於此時在天平的左、右所放置的錢幣數目不相同, 所以需要把某些錢幣的位置變動一下。 怎樣進行呢? 我們可以把整數1至12的3進制表示法以直列的方式記錄, 觀察每一橫行中1與 −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−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−1 的數目都各有4個 1 , 從而讓我們確定了每個錢幣最終的擺放位置如下:[td]| 秤量次序 | 置於左邊的錢幣 | 置於右邊的錢幣 | | 第三次 | 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 的情況, 所以不同秤量結果的數目是: −1−1 與 0 作「一一對應」的話, 那麼透過3進制的表示, 我們便可以知道何者是假幣, 以及知道它比真幣較輕還是較重。 為甚麼呢? 我們不妨用一個簡單的例子加以說明: 假設錢幣6是一個假幣, 而且它比真幣較重。 由於它在秤量時的罷放位置是以 (1,−1,0)(1,−1,0) 來表示, 故其稱量結果將會是(L, R, #)。 反過來說, 如果稱量的結果是(L, R, #), 它的3進制表示(1,−1,0)(1,−1,0) 會唯一地 3 確定了假幣的編號是6, 而且由於天秤下墜的方向與它在天秤出現的位置是一致的, 所以知道它比真幣較重。 另外, 如果錢幣6是一個假幣, 而它比真幣較輕。 因為它在秤量時的罷放位置是以(1,−1,0)(1,−1,0) 來表示, 故其稱量結果將會是(R, L, #)。 反過來說, 如果稱量的結果是(R, L, #), 它的3進制表示 (−1,1,0)(−1,1,0) 4 會唯一地確定了假幣的編號是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,±12±12 是例外, 其他所得數值的正、負號正好對應著假幣是「較重」或「較輕」的情況。 有了這種認知, 會有助於我們快速和正確地判斷出何者是假幣, 以及知道它比真幣較輕還是較重, 而不需要利用上表去查看結果。以下是一些具體的示例: 例一: 假設秤量所得的結果是: 第一次是左重、第二次是右重, 而第三次是平衡。 它對應的3進數是 (0,−1,1)3=0×9+(−1)×3+1=−2(0,−1,1)3=0×9+(−1)×3+1=−2。 由此可知錢幣2是假幣, 它比真幣較輕。 例二: 假設秤量所得的結果是: 第一次是右重、第二次是平衡, 而第三次是左重。 它對應的3進數是(1,0,−1)3=1×9+0×3−1=8(1,0,−1)3=1×9+0×3−1=8。 由此可知錢幣8是假幣, 它比真幣較重。 例三: 假設秤量所得的結果是: 第一次是左重、第二次是右重, 而第三次是左重。 它對應的3進數是 (1,−1,1)3=1×9+(−1)×3+1=7(1,−1,1)3=1×9+(−1)×3+1=7。 由此可知錢幣7是假幣, 它比真幣較輕。 3. 結語及其他問題總括而言, 本文所介紹的方法, 是運用了整數的3進制表示的唯一性。 解法簡單, 而且其思維方式可以應用到其他類似的數學問題上去。 譬如, 以下的兩個問題, 都可以運用3進制的方法求解 5 , 讀者不妨動手一試:
問題一: 如果只可以用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), 寓數學於遊戲, 第一輯, 九章出版社。
---本文作者現任教於香港教育學院數社科技學系---
|
樓主
