網頁

▼

2010年2月3日 星期三

12枚金幣有一不知或輕或重偽幣之解


[兩個50元硬幣，一真一偽，你會分辨嗎？圖取自http://www.libertytimes.com.tw/2009/new/oct/19/today-center2.htm]

>[沒帳號也可匿名推]
分享

12枚金幣有一不知或輕或重偽幣之解


部落格上政論文寫多了，除了政治、經濟、歷史、推背圖外，筆者對科學的東西也是興趣濃厚，像是算算詐胡線出包相關機率，有時也想把生活中的點滴分享給網友。話說在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.

筆者所提供詳解：

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
延展閱讀


Honor一下提供答案的網友！

Spieler fragt[再噗]有個數學問題，本人將在週一公佈答案於本人部落格，謝謝！有十二枚金幣, 其中一枚是偽幣, 重量與真幣不同, 但不知偽幣比較重或比較輕, 現有天平一座, 可以使用三次找出偽幣是哪一枚? 並比真幣輕或重嗎? (thinking)
Jan 30, 2010 - 02:01PM
20 responses to this plurk. (reply to this plurk)
  • Jan 30, 2010 - 14:01
    轉噗機 按我轉噗分享
  • Jan 30, 2010 - 14:01
    小籤籤 想 2010-01-30的天秤座：綜合運勢：★★★★愛情運勢：★★★★工作狀況：★★★★理財投資：★★★ 健康指數：82%商談指數：85%幸運色：橘色幸運數：3　速配星座：天蠍座
  • Jan 30, 2010 - 14:01
    小籤籤 想 外出玩樂不如將時間用在提昇自我方面會更充實。學習性強，讀書、學習技藝都能很快上手。今天可稍微延長沐浴 時間，多讓身體接觸水分，身心都感覺更清爽。待在家裡的
  • Jan 30, 2010 - 14:01
    小籤籤 想 時間不妨整理周遭環境中不需要的物品，淘汰一些舊衣、舊鞋、枯萎的盆栽等等，都有讓心情渙然一新的效果喔。
  • Jan 30, 2010 - 14:01
    冰友美眉1 說 晚安 正妹分機請播 號 點這看足跡找同好 等你很久了
  • Jan 30, 2010 - 14:03
    覺醒的台灣人~薇媽 sagt
  • Jan 30, 2010 - 14:03
    donnayuying sagt 太難了。 (thinking)
  • Jan 30, 2010 - 14:27
    herrian 說 廣告公 司真厲害,連登廣告都免費,真希望哪天廣告公司送錢給我花~...
  • Jan 30, 2010 - 14:50
    站長|Snosrap sagt 6 3 1
  • Jan 30, 2010 - 14:53
    Spieler sagt Snosrap: 不解！
  • Jan 30, 2010 - 16:54
    僵屍蛇amin 分3堆(4.4.4),偽幣在重量不同的那堆,這時候就知道偽幣是比較輕還是重;再把重量不同的4個裡拿 3個來秤兩次就行了
  • Jan 30, 2010 - 16:55
    僵屍蛇amin 我的解是秤4次,不曉得對不對
  • Jan 30, 2010 - 17:56
    野芭樂x堅持xsspiggy sagt 分4,4,4沒錯，不過要假設一下各種狀況：如果第一、二堆等重(#1)，則偽幣在第三堆。任取第三堆中的 兩個秤(#2)，若等重則留下一個並由剩下的兩個中再任取一個秤(#3)，如果又等重，則沒秤到那顆是偽幣；若(#3)不等重，則最後挑到這顆是偽幣。
  • Jan 30, 2010 - 18:14
    野芭樂x堅持xsspiggy sagt 前述狀況：若第一二堆不等重(#1)，則第三堆均為真幣免秤。從不等重的兩堆中各取走一顆，再將各堆剩下的 任兩顆交換到另一盤(#2)，若天枰平衡，表示皆為真幣，則留下一顆，並將(#2)中取走的任一顆和留下的真幣比(#3)。(結果同上一狀況之#3)
  • Jan 30, 2010 - 18:25
    野芭樂x堅持xsspiggy sagt 承上(#2)，交換秤後若不平衡且重盤依然較重，輕盤依然較輕，則交換之四顆皆為真幣且偽幣較輕，將未交換 之兩科任取一顆與真幣秤(#3)，即可找出較輕之偽幣 (說明略)
  • Jan 30, 2010 - 18:28
    野芭樂x堅持xsspiggy sagt 承上(#2)，交換秤後若不平衡且輕重盤互換，則偽幣必在重的那堆中且較真幣重，任取重堆中之任兩顆置於天 枰(#3)，若等重則偽幣為未取的那顆，若不平衡，重的那顆是偽幣。
  • Jan 30, 2010 - 18:40
    野芭樂x堅持xsspiggy sagt 補充上上上上樓：(#2)若不等重，則其中一個為偽幣，任留一顆與真幣秤(#3)，即可找出偽幣 (goodluck)
  • Jan 31, 2010 - 13:04
    僵屍蛇amin sspiggy: 詳解有詳細喔(applause)
  • Jan 31, 2010 - 13:06
    僵屍蛇amin 所以可以3次找出偽幣(dance)
  • Feb 01, 2010 - 06:14
    donnayuying sagt (woot)
http://www.plurk.com/p/3lurhb
  • Feb 02, 2010 - 04:36
    ㄧ中同學s sagt 這有點複雜 分三堆 分別是A1A2A3A4 B1B2B3B4 C1C2C3C4 拿Ａ堆跟Ｂ堆秤第ㄧ次，情況有 平衡 不平衡 先說平衡的情況（這狀況比較簡單），若平衡，則ＡＢ共８個全部都是真的，假的在Ｃ堆 抓Ｃ１Ｃ２來秤第二次，平衡則假的在Ｃ３跟Ｃ４
  • Feb 02, 2010 - 04:37
    ㄧ中同學s sagt 此時，任意拿ㄧ個真的 （Ａ１Ａ２Ａ３Ａ４～Ｃ２） Ａ１跟Ｃ3比較 平衡 則假的是Ｃ４ 尚未完工的部份有第ㄧ次的不平衡 跟第二次的不平衡，還有七種狀況，讓給大家接龍
Facebook上解答！

Hubert Yu
情況一：步驟1同重
硬幣分成三堆，標明為a, b, c，真的設定為x, 假的設定為y，可解答下列情況。

步 驟1，比較a堆4x與b堆4x，因為同重，表示c堆為假。
步 驟2，比較a堆2x與c堆2x，因為同重，表示c堆x+y為 假。⋯⋯ 繼續閱讀
步 驟3，比較a堆x與c堆x，因為同重，表示c堆y為假。

步 驟2，比較a堆2x與c堆x+y，因為不同重，表示x+y為 假。
步驟3，比較a堆x與c堆y，因為不同重，表示y為假。

這是步驟1同重時的方式，運用到二分法和交換法。但步驟1若不同重時，則運用此法至少需4步驟，多出確認假幣的輕重。

情況二：步驟1不同重
硬幣分成三堆，標明為a, b, c，硬幣標為1-12，假幣為12。（以下是假幣輕）

步驟1，比較a堆1-4與c堆9-12，若a重，表示一組為假，b堆（5-8）為真。
步驟2，比較1-3+9（+9到+11結果 同）與5-7+4，因為同重，表示10-12為假。
步 驟3，比較10與11，若同重，表示12為假，假幣輕。

步 驟2，比較1-3+12與5-7+4，前者輕，表示4或12 為假。
步驟3，比較5與4，因為同重，則12為假，假幣輕。

若是假幣重，則方法也如情況二。
昨天 9:55
Hubert Yu
Hubert Yu
有獎賞嗎 XD
我現在只想找出時間好好經營修伯特‧魚看世界啦！
昨天 9:57 ·


[感謝一中同學s大大提供此免費遊戲的連結]
請複製上方的貼紙語法，貼到您的部落格來串連『我要看電影"Formosa Betrayed"』個活動!
於

4 則留言:

  1. joe2010年2月4日 凌晨3:26

    我提供另一種解法，可能更容易：

    一、將硬幣等分二批，拿其中一批再等分上天平，即二側各有三個，如此便可從有無維持水平，得知假幣是在上天平中的那一批，或是沒上天平中那一批。

    二、拿三個真幣上天平一側，再將含有假幣的那一組(6個)等分，一批上天平，另一批不上天平；如此便可知二件事：(1)假幣是較真幣輕或重、(2)假幣是在上天平中的那一批，或是沒上天平中的那一批。

    三、含有假幣的那一批剩3個，二個各上天平二端，一個不上；若維持水平，即沒上天平者是假的，若沒維持水平，因已知假幣是較重或較輕，也可一眼視破。

    回覆刪除
  2. drspieler2010年2月4日 下午4:21

    繼續於此噗討論!

    回覆刪除
  3. 匿名2011年3月4日 晚上11:48

    if step 1 and step 2 result are both equal, but step 3 are unequal, then we cannot concluded since no information to shown the fake coin is heavier or lighter.

    回覆刪除
  4. 匿名2011年3月5日 凌晨12:05

    I check in details but see each method has bug. The solution needs to know the fake coin is heavier or lighter. But I see all above methods can figure out if it is heavier or lighter for some case.

    回覆刪除

歡迎留言！

HTML 編輯器