在32枚金幣中找假幣 by weiweililin - 拼圖

原題：有32枚金幣，其中有一枚是假幣，但不知較輕或較重。

要如何在五次之內，用天平把假幣找出來，並得知它較輕或較重？


只能說我功課做太少了，明明之前就已經有人說過通式解：

若有n個金幣，則k次可以把其中一枚假幣找出，且知較輕較重，則n與k必符合下列關係：

2 < n <= (3^k-3)/2

若符此關係則肯定有解。

反過來說，若秤四次，那麼最多可以從39枚金幣當中找出一枚假幣。
也就是說，原題是可以改為四次的！



題目：有32（或39）枚金幣，其中有一枚是假幣，但不知較輕或較重。

要如何在四次之內，用天平把假幣找出來，並得知它較輕或較重？


◆39枚金幣的方法

先探討39枚，了解了之後，32枚的方式也是大同小異。

◎第一秤（A與B）：

將39枚分成 A13、B13、C13 三堆。

將AB兩組放上去秤。

若A=B，則假幣在C組。AB兩組皆為真幣。

＊拿 A9 與 C9 相秤（第二秤），若不平衡，則知假幣之輕重：

C9較輕，則假幣較輕。
C9較重，則假幣較重。

已知輕重，又只剩下9枚，那麼此題就變成一道很經典的題目。

可以分成3-3-3的3組。
秤一次找到有問題的一組（第三秤），再秤一次（第四秤）找到假幣。＃（結束）
─────────────────────────────
＊若 A9與 C9 相秤（第二秤）且平衡，那麼假幣必在剩下的C4之中：

拿 A3 與 C3 相秤（第三秤），若平衡則剩下的 C1 必為假幣。
再秤一次（第四秤）可知假幣之輕重。＃

若 A3 與 C3 不平衡（第三秤），則可知假幣之輕重。
此時拿 C3 之中兩幣，各放一枚於兩端（第四秤），必可找出假幣。＃
=========================================================================

◎第二秤（A5B4 與 A5'B4'）（「'」僅代表天平右端。例如B4'＝在B組中拿四枚於右方）

若AB不平衡，且假設 A>B ==> 可知假幣若重則在A組；若輕則在B組：

取 A5B4 及 A5'B4' 相秤──

＊若兩邊平衡，則假幣在剩下的 A3B5

取當中的 A1B2 與 A1'B2' 相秤（第三秤）
若平衡則AB組各剩下一枚，此時從C組（皆為真幣）取一枚
與AB組其中一枚相秤（第四秤），則找出假幣且知輕重。＃
（即使平衡，若假幣在A組必較重；在B組必較輕。）
────────────────────────────
＊若不平衡，假設 A1B2 > A1'B2'（第三秤）
則假幣必在A1B2'

這時取B2'相秤（第四秤）可找出假幣（較輕者，若平衡則為A1）。
且可知輕重。＃
=========================================================================

◎第三秤（A1B2 與 A1'B2'）

若 A5B4 及 A5'B4' 不平衡，且假設 A5B4 > A5'B4'，
則可知假幣必在 A5B4' 之中。

取當中的 A1B2 與 A1'B2' 相秤（第三秤）

＊若平衡，則只剩下A組的3枚。
此時任取兩枚相秤（第四秤）則可找出假幣且知較重。＃
=========================================================================

◎第四秤（B1' 與 B1'）

若 A1B2 與 A1'B2' 不平衡，且假設 A1B2 > A1'B2'
則可知假幣必在 A1B2' 之中。

這時取B2'相秤（第四秤）則可找出假幣，且知輕重。＃


◆32枚金幣的方法

看完了上述恐怖且冗長的過程。接下來32枚會簡單一點。

將32枚分成 A10 B10 C12 三組。

若A=B，則剩下C組12枚。這已是流傳已久的題目，故不詳述。

若A>B，則取 A5B4 與 A5'B4' 相秤。若平衡，則B組剩下的兩枚可輕易找出。

若不平衡且假設 A5B4 > A5'B4' 則表示假幣在 A5B4' 裡面。
此時取當中的 A1B2 與 A1'B2' 相秤，若平衡則剩下的A3可秤一次找出假幣。
若不平衡且假設 A1B2 > A1'B2' 則表示假幣在 A1B2' 裡面。
此時取 B2' 相秤可找出假幣且知輕重。


--