[問題]偽幣問題

[問題]偽幣問題

浩浩 於 星期二 六月 07, 2005 7:58 pm


15個金幣中有一個是假的,請問用天平秤最少秤幾次能秤出?
或者是如下的鐵球問題
http://yll.loxa.edu.tw/phpBB2/viewtopic.php?p=121379&highlight=%C5K%B2y#121379

或者是如下的三個問題
1.有n個金幣,其中有1個是假的,請問最少用天平秤幾次可以秤出假的金幣?(已知假幣比真幣重)
2.有n個金幣,其中有m個是假的,請問最少用天平秤幾次可以秤出假的金幣?(已知假幣比真幣重)
3.有n個金幣,其中有m個是假的,請問最少用天平秤幾次可以秤出假的金幣?(未知假幣真幣誰比較重)


最近在作這種偽幣問題的研究,只是常常會碰到一種情況
例如有8個金幣,其中一個是假的,要找出哪個是假的
只要把原來的金幣分成 (3,3,2)去探討即可得出2次的秤法
但是,我們要如何證明2次是最少的呢?
換句話說,當我們做偽幣問題時,常常找出可能正確的答案,但要如何去證明他呢?
Fernando Tan
歡迎大家加入: http://tw.club.yahoo.com/clubs/happylearning/

只要我不放棄,夢想就在不遠處

浩浩
版 主
版 主
 
文章: 488
註冊時間: 2004-02-14
來自: 數之領域

Re: [問題]偽幣問題

bell 於 星期二 六月 07, 2005 9:37 pm


浩浩 寫到:15個金幣中有一個是假的,請問用天平秤最少秤幾次能秤出?

不知道偽幣重量是較輕或重,以下這個方式最少3次,最多4次。

一、15枚金幣分成三堆,每堆5枚,分兩次秤重:
  (以下設三堆金幣分別為abc)
  a與b秤一次,b再與c秤第二次。
  →a=b,b≠c時,偽幣在c。
  →a≠b,b=c時,偽幣在a。
  →a≠b,b≠c時,偽幣在b。
  並可得知,此有偽幣的一堆較另外兩堆輕或重。

二、將5枚金幣分成221,同為2枚的兩堆秤重。
  若兩堆不等重,則將較輕或重的一堆(2枚)再秤一次,即可找出偽幣。(總計秤4次)
  若兩堆等重,則那另1枚即為偽幣。(總計秤3次)


知道偽幣重量為較輕或重,以下的方式最少秤1次,最多秤3次。

15枚金幣分成771,同為7枚的兩堆秤重。
若兩堆等重,另一枚未秤重的金幣是偽幣。(總秤重1次)

→ 若兩堆不等重,再將秤得較輕或重的7枚分成331,同為3枚的兩堆秤重。
  若兩堆等重,另一枚未秤重的金幣是偽幣。(總秤重2次)

→→ 再若兩堆不等重,將秤得較輕或重的3枚中的2枚的秤重。
   若2枚等重,另一枚未秤重的金幣是偽幣。(總秤重3次)
   若2枚不等重,其中一枚即是偽幣。(總秤重3次)


知道偽幣重量較輕或重,以下的方式最少秤2次,最多秤3次。

一、15枚金幣分成三堆,每堆5枚,任兩堆秤一次重:
  若兩堆等重,另一堆未秤重的有偽幣。
  若不等重,其中較輕或重的一堆有偽幣。

二、將含有偽幣的一堆金幣分成221,同為2枚的兩堆秤重。
  若兩堆等重,則那未秤重的1枚即為偽幣。(總計秤2次)
  若兩堆不等重,則將較輕或重的一堆(2枚)再秤一次,即可找出偽幣。(總計秤3次)
 

 

bell
研究生
研究生
 
文章: 146
註冊時間: 2005-03-23

娜可兒 於 星期二 六月 07, 2005 9:50 pm


1.有n個金幣,其中有1個是假的,請問最少用天平秤幾次可以秤出假的金幣?(已知假幣比真幣重)

這種問題比較單純,要證明也是可以的,只是不知道如下證明夠不夠嚴謹:
物品用天平稱重會符合三一律,即大於,等於,小於
因為已經假幣較真幣重,故先把物品均分三堆,
若無法均等,也要分成兩堆等量,而第三堆和其他兩堆差一的數量
先取兩堆等量的來稱重,則會有左重,平衡,右重等三種結果
若左重,則左堆有問題
若平衡,則未取堆有問題
若右重,則右堆有問題
為了以最少次找出,必須避開矛盾現象,直接由有問題的那堆下手
重覆上述動作:均分三堆,取兩堆稱重,判別有問題堆
一直到找出有問題堆為唯一一個為止
而每稱一次會有三種結果(即左重,平衡,右重)
若重覆了T次(即稱了T次),則共有3^T個結果,即最多可判別3^T個硬幣
故若3^(T-1)<N≦3^T,則最少需稱T次才能找出假幣
*真正熱愛數學的人,是重質不重量的
 希望大家成為數學狂熱者,而不是積分狂熱者
 別做讓版管為了您的文而頭疼的小白!

*知識的價值 不在於你能擁有多少
 而是在於你要如何活用於生活之中
左鍵: 點擊縮放; 右鍵: 觀看原圖

娜可兒
版 主
版 主
 
文章: 765
註冊時間: 2005-03-19
來自: 侍魂-神仙之村    職業: 蝦夷族巫女        興趣: 蹓鷹




分類主題數學區