Re: [請問] 在32枚金幣中找假幣 by weiweililin

看板puzzle (益智遊戲 - 數獨,拼圖,推理,西洋棋)作者puzzlez (帕索)時間16年前 (2010/03/01 10:58)推噓4(4推 0噓 4→)

留言8則, 5人參與討論串2/4 (看更多)

原題：有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' 相秤可找出假幣且知輕重。 -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 123.194.127.118 ※ puzzlez:轉錄至看板 ask 03/01 11:03