問題

有金幣六袋,每袋有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枚。

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

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

步驟一

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

步驟二

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

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

X = 46 - 24 = 22

接著將22填回去會得到

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

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

步驟三

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

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

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

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

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

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

步驟四

一袋為假 = 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

更新

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

步驟五

一袋為假 = 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袋金幣呢?我們在繼續往下找看看。

一袋為假 = 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袋。

延伸閱讀

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

文章標籤
創作者介紹

小殘的程式光廊

emn178 發表在 痞客邦 PIXNET 留言(0) 人氣()