天秤找假幣（二）

最近忙了一點，今次先說說三題的「最佳」答案，下次才說怎樣證明為「最佳」。

說起「最佳」，我的原意是「最少用多少次天秤就能確定能找出假幣？」。網友Pop在上一篇文章留言用了另一個方法看「最佳」，就是「平均用多少次天秤就能確定能找出假幣？」。大家可以到上一篇文章的「意見」看一看。

1) a)

Pop在上一篇文章說了方法，最壞情況需要三次。

1) b)

先在天秤兩邊每邊任意放四個金幣。

若然兩邊重量一樣，則可確定不在天秤上的四個幣其中一個是假的。只需要多用兩次天秤，便能從這四個幣中判出哪個是假（這個不難，自己想一想吧）。

若然兩邊重量不一樣，定義在較輕那邊的四個幣為L1, L2, L3, L4；在較重那邊的四個幣為H1,H2,H3,H4。

把L1,L2,H1放在一邊，L3,L4,H2放在另一邊。若然兩邊重量一樣，則H3是假幣或H4是假幣。那麼只要將H3和H4秤一次，哪個較重就是假的。若然兩邊重量不一樣，不失一般性，設L1,L2,H1那邊較輕。那麼只可能出現以下情況：

i) L1是假幣，比真幣輕
ii) L2是假幣，比真幣輕
iii) H2是假幣，比真幣重

只需將L1和L2秤一次，若兩邊重量一樣，是情況iii)；若L1比L2輕，是情況i)；若L1比L2重，是情況ii)。

故最壞情況也是三次。

2)

設已確定為真的幣為N，而其餘五個幣的編號為1,2,3,4,5。

先將N和1放在一邊，2和3放在另一邊。若兩邊重量一樣，則4為假幣或5為假幣。之後將N和4一起秤，若重量一樣則5為假幣；若重量不同則4為假幣。

若 N和1 比 2和3 輕，則只會出現以下三種情況：
i) 1 是假幣，比真幣輕
ii) 2是假幣，比真幣重
iii) 3是假幣，比真幣重

若 N和1 比 2和3 重，則只會出現以下三種情況：
i) 1是假幣，比真幣重
ii) 2是假幣，比真幣輕
iii) 3是假幣，比真幣輕

兩組的「三種情況」均可以用一次天秤就能判別哪個是假幣，而且方法非常簡單（跟 1) b) 最後一部分類似），故略。


看了解答後，我相信部分人會有一點疑惑：1) a)只有五個幣，1) b)有十二個幣，怎麼「最佳」的解法都是三次？這不敢令人對1) a)的「最佳」解法質疑。所以，數學人必須證明它是「最佳」！

下次我便說說證明「最佳」的方法，並簡介一下這個方法解決了一個Computer Science基本但非常重要的問題。