02/08/2010 00:36

12枚金幣有一不知或輕或重偽幣之解 (知識科技)

[感謝南方大大iitaiwan提供圖片！相關文字請按] 12枚金幣有一不知或輕或重偽幣之解 本文funP網址請推 部落格上政論文寫多了，除了政治、經濟、歷史、推背圖外，筆者對科學的東西也是興趣濃厚，像是算算詐胡線出包相關機率，有時也想把生活中的點滴分享給網友。話說在1月30日當天，有人熊熊問筆者一個問題：『有十二枚金幣, 其中一枚是偽幣, 重量與真幣不同, 但不知偽幣比較重或比較輕, 現有天平一座, 可以使用三次找出偽幣是哪一枚? 並比真幣輕或重嗎? 』，筆者想了好一陣子解出了。本來這個問題，網路是有詳解的，如果想偷懶用Google一下，應該是可以得到答案的。不過自己去想，得到答案的，那種喜悅，還是比較有意思的。 筆者把這個問題分別PO在Plurk、 Facebook上，有網友野芭樂x堅持xsspiggy、ㄧ中同學s和Hubert Yu po出解，在此必須對此3位網友表示敬意，文中並列出解答，以示Honor之意！ 其實筆者解答這個問題的過程，是企圖找出更為一般的情況，看能不能把一般的情況reduce到幾種簡易的case，甚至發展出個Algorithm。像是「12枚金幣有一不知或輕或重偽幣」的問題就可能衍生「n枚金幣有一不知或輕或重偽幣」、「n枚金幣有一已知或輕或重偽幣」以及「n枚金幣有一或輕或重偽幣，再加上若干可用的已知真幣」等等。主要的工具是天平，量一次可能有三種結果：『重於、輕於、等於』，在不知偽幣輕重下，應該是要用「三分法」，如果已知偽幣是較輕或較重，當然可用「二分法」，筆者把原始問題 「12枚金幣有一不知或輕或重偽幣」以符號 P(12, 偽幣輕重不知) 表之。 當金幣數多時，每測量一次，就會得到一堆等式或不等式，再想辦法解出。然而其中幾個簡易 case應該馬上可解： P(3,偽幣輕重不知) 僅需量2次 解：令三金幣重量分為X,Y,Z。量X, Y: 1. 如果X=Y則Z為偽幣。 2. 如果X重於Y，量X, Z 2.1. 如果X重於Z，X是偽幣。 2.2. 如果X=Z，Y是偽幣。 P(4,偽幣輕重不知) 僅需量2次 解：令4金幣重量分為X1,X2,A,B。量 X1, X2: 1. 如果 X1=X2 則偽幣為A或B 1.1. 量X1, A IF X1=A THEN 偽幣=B 1.2. ELSE 偽幣= A 2. 如果 X1重於X2 量X1, A 2.1. IF X1=A THEN 偽幣=X2 2.2. ELSE 偽幣=A 3. 如果 X1輕於X2 類似case 2. 筆者所提供詳解： Code: 1.把12金幣分成3堆A,B, C，重量分別為A1,A2,A3,A4, 　　B1,B2,B3,B4, C1,C2,C3,C4。 2.量A, B 3.IF 重量(A)=重量(B) THEN 4. 偽幣在C中，較輕較重未知 5. P(4,偽幣輕重不知) 6. 得解 7.ELSE IF A重於 B (較重堆為A ，較輕堆為B) THEN 8. 偽幣 在A,B中，C中全為真幣，每顆重量均為x 9. 量 A1+A2+B1+B2, A3+B3+C1+C2 10. IF A1+A2+B1+B2=A3+B3+C1+C2 THEN 11. A3=B1=B2=B3=A1=A2=x為真幣, 偽幣為A4或B4 12 量A4, C1 13 IF A4=C1 THEN 偽幣=B4 ELSE 偽幣=A4 14. ELSE IF A1+A2+B1+B2重於A3+B3+C1+C2 THEN 15. A3=A4=B1=B2=B4=x為真幣，偽幣於A1,A2,B3中 16. 量A1, A2 17. CASE A1=A2: 偽幣=B3 18. CASE A1重於A2: 偽幣=A1 19. CASE A1輕於A2: 偽幣=A2 20. ELSE 即 A1+A2+B1+B2輕於A3+B3+C1+C2 21. A1=A2=B3=A4=B4=x為真幣，偽幣於A3,B1,B2中 22. 量B1, B2 23. CASE B1=B2: 偽幣=A3 24. CASE B1重於B2: 偽幣=B2 25. CASE B1輕於B2: 偽幣=B1 http://drspieler.blogspot.com/2010/02/12.html »» 回應這篇文章