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

[puzzlez (帕索)]

原題：有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
推 CHOIP:推
推 circleli:推,但第一秤中「拿C3之中兩幣....」那是第四秤,非第三秤
→ circleli:若又平衡,再秤一次.....則為第5秤喔~~這裡寫錯了@@
※ 編輯: puzzlez         來自: 123.194.127.118      (03/02 07:15)
→ puzzlez:嗯，其實我有看到...只是懶得改...:-P
推 perseus0724:看都看一陣子了，想答案要想多久啊＠＠
→ youga:其實從一秤 兩秤 三秤往上推會簡單很多 因為模式完全相同
推 youga:了解少秤的道理 就可以推公式 多秤其實就只是套進去而已
→ puzzlez:=  =是哦..我想好久...我比較笨>"<