劉應興的部落格

有若干硬幣，其中一枚是偽幣。偽幣與真幣只差在質量不同。今欲用天平，不含法碼，用最少次量測來找出偽幣，問：怎麼做？

數學問題就是這麼不現實！現實上除非剛從鑄幣廠出來，如果經過輾轉使用，會有不同程度的磨損；即使同是新鑄幣，也有製造公差，因此很難說兩枚硬幣完全無差別。再者，為什麼要限制只能用天平還沒有法碼呢？咱用砰不行嗎？又何必執著於最少次量測？

話說回來，如果只能測質量或重量，而且真幣之間的差異現有工具無法查覺，倒是真偽幣之間的質量差距能輕易用天平測出，那麼，採用其他方法或許真不可能更快（更少次數量測）找出偽幣。

硬幣中找偽幣只是這問題的一個形式，也可以換成若干球中找「異類」或其他形似物中找異物。數學問題就是這樣， 1 + 1 = 2, m + n = p 可以描述很多現實問題，因此解決一個數學問題也就是解決了許多形形色色的現實問題。

回到問題本身，一個典型的例子是從 13 枚硬幣中，經 3 次天砰測量找出其中唯一的偽幣，並且可能知道它比真幣輕或重。同時，這還有一個附加結論： n 枚硬幣之中有一枚偽幣，則所需使用天平次數至少是 ２n 以 3 為底的對數。

以 13 枚硬幣的例子來說，假設它們被標上號票 1~13，則可能的惰形有 26 種

　　　　{1L, 1H, 2L, 2H,……13L,13H}

其中 1L　表示偽幣是 1 號，並且偏輕； 1H 表示偽幣是 1 號，並且偏重；以此類推。

天平的測量結果有三：兩邊平衛、左重右輕、或左輕右重。例如，左 1 右 2 （天平左邊放 1 號幣右邊放 2 號幣，可能情形是： 1 號 2 號同質量、１ 號重於 2 號、或 2 號重於 1 號，如果這是 13 枚硬幣中的 2 枚，則

　　平：表示原來 26 種可能情形變成 22　種 {3L, 3H,......13L, 13H};

　　左重: 則可能 1H 或 2L; 

　　右重：可能 {1L, 2H}.

為了最快查出偽幣，必須在任何量測結果之後都讓可能結果數縉減為原來 1/3 左右。例如第一次，左1,2,3,4　右5,6,7,8, 則

　　平：則可能結果 {9L, 9H,......,13L,13H} 有 10 種可能，因此再兩次量測不一定可知偽幣輕重。

　　左輕：則結果 {1L, 2L, 3L, 4L, 5H, 6H, 7H, 8H}

　　左重：則結果 {1H, 2H, 3H, 4H, 5L, 6L, 7L, 8L}

如果第一次兩邊平，接下來的問題似乎是 9~13 號 5 枚硬幣中要經過兩次天平量測找出偽幣。這本是做不到的，但現在有 8 枚真幣在就不一樣了。第２次量測用：左9,10 右11,1,

　　平：則偽幣在 12, 13 中，可能結果 {12L, 12H, 13L, 13H}

　　左輕：則可能結果是 {9L,10L,11H}

　　左重：則可能結果是 {9H, 10H, 11L}

對第一種結果，最後一次量測採：左12 右1, 若

　　平：則偽幣是 13 號，不知偏軾或偏重。

　　左輕，偽幣 12, 偏軾。

　　左重，偽幣 12, 偏重。

第二次量測，左9,10 輕於右11,1, 可能結果是 {9L,10L,11H}，因此只要將 9, 10 分別放天‵平兩邊，即可知究竟是 9L? 10L? 或 11H? 第二次量測得可能結果 {9H, 10H, 11L} 也一樣，將 9, 10 分放天‵平兩邊，即可知最終答案。

第一次量測　得可能結果是  {1L, 2L, 3L, 4L, 5H, 6H, 7H, 8H} 或  {1H, 2H, 3H, 4H, 5L, 6L, 7L, 8L} 則 1~4 與 5~8 一組取 3 枚，另一組取２ 枚與正常的 9~13 五枚比較，例如原本是 1~4 較 5~8 輕，而第二次是：左 1,2,3,5,6 右9~13，則：

　　平，則可能結果是 {4L, 7H, 8H}

　　左輕，則得 {1L, 2L, 3L}

      左重，意謂 5H 或 6H。

不管哪種結果，再一次量測都能確認偽幣並且知其偏輕或偏重。

以上量測方式有可能雖然 3 次可找出偽幣，卻不知偽幣偏輕或偏重，因為在 4 + 4 + 5 的分組中，若偽幣在最後一組中，即使有已知的真幣在手，也不可能在兩次量測完全區分 10 種可能性。於是我們也知道：若是原先是 12 枚而非 13 枚硬幣，分成 4 + 4 + 4 三組，若第一次量測結果發現偽幣在 9~12 之中時，再兩次量測即能找出偽幣並知其偏輕或偏重。

另一方面，如果不只 13 枚呢？例如 15 枚，分成 5 + 5 + 5。第一次：左1~5 右6~10, 若天平持平，接下來用 4 + 4 + 5 時第一次 4 對 4 平之後的方法，兩次可找出偽幣，知或不知偏軾或偏重。但若一輕一重，接下來想兩次量測從 10 枚硬幣中找出有問題的一枚似不可能，因為如果找出偽幣同時也能知其偏輕或偏重，這等於兩次天平量測可完全區辨出 10 種可能性，但實際上一次量測可區分 ３ 種，兩次量測充其量是區辨 ９ 種。15 枚既然不可能三次量測解決，更多枚硬幣更不可能。那麼 14 枚呢？顯然 5 + 5 + 4 的分法遇到止述同樣問題，4 + 4 + 6 呢? 這可能面臨從 6　枚硬幣用兩次天平找出偽幣的問題，雖然有真幣在手，這是否可能? 將 6 枚硬幣分成 3 + 3 並將一組與真幣比，可能最後一次機會面臨從 ３ 校硬幣只用天平一次要找出偽幣的問題，可惜這做不到，畢竟有６種可能，即使有真幣在手也做不到。因而三次使用天平從 13 枚硬幣找出偽幣已是上限，而要完全解決偽幣問題（找出並知其較輕較重）則只能是 12 枚。