2014年9月24日 星期三

訓練數學感 35 ─ 尋找偽幣

https://4rdp.blogspot.com/2014/09/35.html

有60個外型一樣的硬幣及一個沒有砝碼的天平,現在知道只有一個偽幣和其它的重量不同,問怎樣稱才能最少次數內就找到那個重量不同的偽硬。(注意此題並未說明那個硬幣的重量是輕是重,所以需要仔細考慮)

難度
如果知道偽幣比較輕時,你又會怎麼稱?

24 則留言:

  1. 知道偽弊輕重,秤7次可找到
    不知道輕重,運氣好也可能7次找到

    回覆刪除
  2. 知道偽弊輕重,秤6次可找到
    不知道輕重,運氣好也可能7次找到

    回覆刪除
  3. 不知道輕重,應該五次就能夠找到。

    回覆刪除
  4. 知道輕重,4次
    不知道輕重,5次

    回覆刪除
    回覆
    1. 您好,
      雖然寫出答案了,可否再補充說明。
      訓練數學感這一系列考題,除了讓大家動動腦想一想,也透過討論學習如何思考,有助於學業、工作、生活多方收穫,謝謝。

      刪除
    2. 知道輕重的話, 我想大概是這樣的?

      第一次, 5 vs 5
      第二次, 3 vs 3
      第三次, 2 vs 2
      第四次, 1 vs 1

      刪除
    3. Rex,我無法理解你的說明,如果可以請再詳細說明。

      謝謝

      刪除
  5. 分成三堆20:20:20(秤兩次,取出較輕的那堆)
    在分成三堆7:7:6(只秤7:7,若相同偽幣在6,若不同取輕的7)
    在分成三堆3:3 or 3:3:1(只秤3:3,若相同取得偽幣,若不同取輕的3)
    第五次 1:1:1

    回覆刪除
    回覆
    1. Bon 謝謝你的說明,關鍵已經點到了。

      刪除
  6. 分三堆秤重,不管結果如何,一定可以找到標準重量的硬幣。例如天平左右相等,則天平上這40枚硬幣為真幣。若天平不等重則剩下的20枚硬幣為真幣。正個題目的做法就是盡可能分成三堆,然後透過上面的原則,不斷排除真幣,即可得到答案。

    回覆刪除
    回覆
    1. 沒錯,精髓已經點出來,在不知道輕重的狀況,可能會多一次秤重來鑑別真偽。

      加分題,知輕重情形時,秤五次最多可以從幾個硬幣中找出偽幣?
      進階題,60個硬幣中有兩個偽幣,知道輕重與不知輕重,分別需要最少幾次秤重找出偽幣?

      刪除
    2. 知輕重情形時,秤1次可以從3個硬幣中找出偽幣;
      秤2次可以從9個硬幣中找出偽幣……
      大膽推測一下,二者應該是冪的關係。
      秤五次則是3^5 = 243

      刪除
    3. 已知僞幣輕重時,
      假設共有n枚硬幣,所需最大磅重次數為:
      =roundup(log(n,3),0)

      刪除
    4. Linke 好久不見,香港佔中活動有影響你嗎?

      加分題正解,進階題繼續努力。

      刪除
    5. 是啊,前段網絡壞掉,剛修好。
      我在香港西北面的屯門區工作,距離很遠,沒太大影響。
      (聽説股市跌了,我準備找個低位買一點,試圖接受下它的“影響”……(笑)
      ————————————————————————————
      進階題有兩個僞幣,我第一個想法就是分5組。
      因爲一個僞幣時大家分了1*2+1=3組,那兩個僞幣時
      又不知道輕重的話,分2*2+1=5組也不為過。
      (3個僞幣時就先分7組……這個公式x*2+1貌似是通解喲)
      回歸正題,分5組每組12個後,隨便拿一組與其他四組秤重(共4次),
      按照其大於小於或等於的情況,列舉如下:
      等小小小
      等大大等
      小小小小
      等等大等
      ———分隔———
      大大大大
      等等等小
      等大大大
      等等小小
      *(説明:分隔之上是2個輕僞幣的情況,之下是2個重僞幣的情況,
      1輕1重的情況有點複雜,之後再討論)*
      秤了4次之後,就知道輕重,也知道僞幣的分佈,共兩種情況:
      甲、1組共12個中,有2個僞幣;
      乙、2組共24個中,各有1個僞幣。
      情況甲因爲其中總硬幣個數小於情況乙,所以前者所需步驟應該亦少於或等於後者。
      故僅需討論短板情況乙。
      承原題,從12個硬幣中找出1個僞幣,需要3次秤重才能找出僞幣。
      那麽兩組就是6次,加上之前的4次,
      結論:
      一共要秤10次才能在60個硬幣中找出2個不知皆輕或皆重的相同僞幣。

      刪除
    6. 嗯,兩個等重或等輕的偽幣分五組是正確的,這樣找一定找的到,而且你還提出多枚偽幣的通解,真厲害。

      不過我對這個問題,仍有疑惑,有沒有比較單純的作法,可能會多一兩次(通解但不是最佳解),不管找幾個偽幣,都可找出來。

      另外,不知道能不能12顆找兩個偽幣五次內找到?

      刪除
    7. 先說最後的問題。
      上次說到短板情況乙,需要再做6次才能分辨出2個僞幣,
      那麽情況甲一定會在5次内找到啊~
      步驟如下:
      因爲已知僞幣等重或等輕了,那麽就不用分5組,分4組就夠了,
      秤3次便可以知道僞幣分佈。
      一種情況是3個硬幣中有2個僞幣,另一種情況是2組3個硬幣中各有1個。
      第一種情況,秤1次就可以知道結果;第二種情況,需要各秤1次,共2次。
      又是只需要考慮短板情況乙,2次加上之前的3次,就是5次。

      刪除
    8. 「已知僞幣等重或等輕了,那麽就不用分5組,分4組就夠了,秤3次便可以知道僞幣分佈」,
      這個說明有問題,假設 A3 = B3,A3 # C3 ,A3 # D3,你能明確指出是 A3 與 B3 各有一枚偽幣,還是 C3 與 D3 有?

      刪除
    9. 還是要按照其大於小於或等於的情況,列舉如下:
      等小小
      等大大
      小小小
      等大等
      ———分隔———
      大大大
      等小等
      等大大
      等小小
      *(分隔上是已知兩僞幣皆輕的情況,之下是已知兩僞幣皆重的情況)*

      刪除
    10. 啊,抱歉,我忘記在60枚分五堆測量時,把偽幣是輕是重,以及分佈在哪裡,已經判別出來。
      所以你的推導過程相當正確,唉,老了,常常忘東忘西 ^_^!!!

      刪除
    11. 最近搜了一下其他人做的找僞幣研究,我發現我這種找2個僞幣方法……
      居然比大多數人的先進?!
      我看到台大兩位研究生做的是2*roundup(log(n,3))+2,
      我的方法換成這種形式表述約合2*roundup(log(n,3))+1.071,
      而理論最小值是2roundup(log(n,3))+0。
      (突然想找香港教院的期刊發表一下我的發現XD)
      ——————但,事實是殘酷的————————
      我在驗證時,發現2*n+1這個多枚僞幣分組秤量方法存在問題,
      其實在n=3的時候,已經不能根據6次秤量的結果準確判別輕重和分佈了。
      ……真的不能嗎……我下週再做做看吧……

      刪除
    12. 能否提供台大研究生的連結,以便參考比較?
      另外,你的表述式 2*roundup(log(n,3))+1.071 中 1.071 怎麼來的?

      最近在閱讀一本 改變世界的九大演算法,其中一章談論到公鑰加密,現今科技以極大的質數運算保護,未來不排除有人能提出快速破解這個古老的數學問題,或許這個看似簡單的尋找偽幣,n 個錢幣中尋找 m 個假幣問題,會成為另一個難解的加密方法。 \^_^/

      刪除
    13. http://ir.lib.ntnu.edu.tw/ir/retrieve/21319/metadata_0306002_01_010.pdf
      應該更正為“台師大”的研究才對。
      我的表達式原來是 2*roundup(log(n/5,3))+4 ,
      變成上述鏈接中的表述形式就約合1.071。

      刪除
    14. 了解,這篇文章不知為何無法下載,明天再試看看。

      刪除