問題

有金幣六袋，每袋有 24 枚金幣，不知道有幾袋真幾袋假，真的金幣重 10 克，假的重 9 克。給你一個電子秤，只能秤重一次，就知道哪幾袋是假的？

提示

不是天秤，這可以秤出重量。

解法

在上一篇我們透過二進位的方式可以辨別，但是在第六袋的時候必須要取出 32 枚金幣，超出題目限制的 24 枚金幣，所以不能使用二進位方式解，因此這裡採用另一種方式來取。

在此之前我們先將問題簡化，來說明這個方法的意涵，現在將題目改成只有兩袋金幣，然後我們先從一個袋子取出 24 枚，另一個取出 23 枚。這邊我們可以很容易知道如果比預期少 24 克表示第一袋金幣是假的、23 克則為第二袋或者 47 克則兩袋都是假的。

如果改成三袋金幣，則分別取出 24、23 和 22 枚。這時兩袋為假的情況就變得複雜，24 + 23 = 47 或 24 + 22 = 46 或 23 + 22 = 45，目前為止可以分辨。

如果改成四袋金幣，則分別取出 24、23、22 和 21 枚。這時除了之前的 24 + 23 = 47 或 24 + 22 = 46 或 23 + 22 = 45，又多出了其他可能性，然後我們會發現 24 + 21 = 45，會 和23 + 22 = 45 重複造成混淆無法分辨，故此時不取 21 枚。

基本上找出每袋要取出的金幣數目為目標，但依照上面的方式找速度很慢，以下為這個方法的精神結合數學的方式，能夠加快找到答案的速度。

由於全為真一定可以辨別，所以以下不列出考慮，這邊直接從取兩袋金幣開始：

步驟一

1
2
一袋為假 = 24, 23
兩袋為假 = 47

步驟二

1
2
一袋為假 = 24, 23, X
兩袋為假 = 47, (46 ... )

第三袋要取的金幣數假設為 X，為了避免在兩袋為假的情況下出現也是 47 的組合，所以我們希望 X 產生的組合會是 46，所以我們和最大的數字相減：

1
X = 46 - 24 = 22

接著將 22 填回去會得到

1
2
3
一袋為假 = 24, 23, 22
兩袋為假 = 47 ... 45
三袋為假 = 69

填回去同時更新資料，而我們只需要關注邊界的值即可，所以中間的部分可以忽略不管。

步驟三

1
2
3
一袋為假 = 24, 23, 22, X
兩袋為假 = 47 ... 45 (44 ... )
三袋為假 = 69 (68 ... )

到了第四袋時，除了兩袋為假還多出了三袋為假的情況要考慮，不過實際上我們可用同樣的方式去找，相減的時則是和上一層最大值相減。

1
2
X = 44 - 24 = 20
X = 68 - 47 = 21

這時候我們發現出現兩個不同值，我們取最小值 20，更新資料：

1
2
3
4
一袋為假 = 24, 23, 22, 20
兩袋為假 = 47 ... 42
三袋為假 = 69 ... 65
四袋為假 = 89

之後利用同樣的方式即可找出全部要取得數量

步驟四

1
2
3
4
5
6
7
一袋為假 = 24, 23, 22, 20, X
兩袋為假 = 47 ... 42 (41 ... )
三袋為假 = 69 ... 65 (64 ... )
四袋為假 = 89 (88 ... )
X = 41 - 24 = 17
X = 64 - 47 = 17
X = 88 - 69 = 19

更新

1
2
3
4
5
一袋為假 = 24, 23, 22, 20, 17
兩袋為假 = 47 ... 37
三袋為假 = 69 ... 59
四袋為假 = 89 ... 82
五袋為假 = 106

步驟五

1
2
3
4
5
6
7
8
9
一袋為假 = 24, 23, 22, 20, 17, X
兩袋為假 = 47 ... 37 ( 36 ... )
三袋為假 = 69 ... 59 (58 ... )
四袋為假 = 89 ... 82 (81 ... )
五袋為假 = 106 (105 ... )
X = 36 - 24 = 12
X = 58 - 47 = 11
X = 81 - 69 = 12
X = 105 - 89 = 16

所以最後答案就是取出 24, 23, 22, 20, 17, 11 去秤重即可。

那麼有沒有辦法辨別 7 袋金幣呢？我們在繼續往下找看看。

1
2
3
4
5
6
7
8
一袋為假 = 24, 23, 22, 20, 17, 11, X
兩袋為假 = 47 ... 28 (27 ... )
三袋為假 = 69 ... 48 (47 ... )
四袋為假 = 89 ... 69 (68 ... )
五袋為假 = 106 ... 93 (92 ... )
六袋為假 = 117 (116 ... )
X = 27 - 24 = 3
X = 47 - 47 = 0

我們發現出現取 0 的情況，表示沒有辦法辨別更多袋金幣，所以 24 枚金幣最多就只能辨別 6 袋。

延伸閱讀

上一篇 智力測驗 - 金幣問題 (二)