[問卦] 有二十袋金幣，其中有一袋是假幣，用秤找出假幣 - Gossiping板

看板 Gossiping
作者 fromtokyo (FromTokyo)
標題 [問卦] 有二十袋金幣，其中有一袋是假幣，用秤找出假幣
時間 2019-11-05 Tue. 21:20:50

題目: 這裡有二十袋金幣和一個超高精度秤±0.01克，秤的測量上限是3KG

已知: 每袋金幣有100枚±10枚，其中有一袋是假幣，
1枚真幣重量是10公克±0.01克，而假幣又比真幣少1公克。

請問: 最少需要使用幾次秤，才能找出哪一袋是假幣？

--
※ 編輯: fromtokyo 時間: 2019-11-05 21:39:51 (台灣)

→
ee2b00

台灣 11-05 21:37
1次
怎麼秤
→
newbit

台灣 11-05 21:51
因一次最多只能秤30枚

所以只秤一次訊息量不夠頂多是判斷出假幣落在那五袋之中！
1枚10公克±0.01克，秤299枚沒問題
→
jeffreymoto

台灣 11-05 21:53
只能秤重應該找不出來吧？你有答案嗎？
只能秤重可以找出來，關鍵在需要秤幾次
→
ee2b00

台灣 11-05 21:54
1次的原因是因為只問『最少』用幾次，所以的確有隨便抓一袋就剛好抓到的1次可能性
可以，算你過，還有別的答案嗎
→
jeffreymoto

台灣 11-05 21:56
答案該不會是每袋拿一枚出來秤，最多四次就知道哪袋都假的。
整袋秤會因為公差使真假幣重量完全一樣啊。
要詳述怎麼秤
→
cpw9711

台灣 11-05 22:14
每袋各拿一個並做記號，全部放在磅秤上；一次拿一個起來，觀察每次減少的重量，這樣應該可以判斷哪一袋是假的
可以，要詳述過程，怎麼秤，預期要秤幾次可以找出來。
→
sahuee2003

台灣 11-05 22:25
答案→秤一次即可
第一袋取1敉，第二袋取2敉，以此類推第二十袋取20敉
這樣總共會有210敉，210敉若每個10克
若都是真幣總共會有2100克
但是有一袋是假幣，就看少了多少克除以十，就知道是哪一袋了
正解出現！但是你的詳細描述有點小bug，你要說在二十袋金幣的袋子上面，依序標註編號1~20號袋，然後編號1取出1枚、編號2取出2枚‧‧‧依此類推

^^^^^^ee2b00 同學找到新狀況，在考量到誤差時，210枚誤差最大可達±2.1克，
所以正確解答可能還需要繼續拆分解題，請同學繼續往前推，最終解答快出來了
→
huzc0606

台灣 11-05 22:41
樓上是好方法~
沒錯，是正解
→
ee2b00

台灣 11-05 22:48
樓上的方法只適用真金幣全都一樣重的情況喔~~現在的情況設定有±0.01的可能了~~所以不合了喔
合的，因為±0.01公克的誤差小的可以忽略，在最差情況下的誤差影響也不及±0.2公克

^^^^^^^^^^^^^^這邊我沒注意到總數是210枚，所以最多誤差可以到±2.1克，所以可能還需要拆分解題，那麼現在我們繼續往前推，共約需要秤多少次才能取得正解呢。
→
ee2b00

台灣 11-05 22:57
不對喔~~由於有20袋~~所以在有誤差的情況會有『+2.1到-2.1』~~
也就是有4.2的可能誤差喔~~會有差到2個金幣的可能性
好像真的是，我看看，沒錯，同學抓到重點了，所以正解又要變囉，誰能推出正解呢
→
fromtokyo

台灣 11-05 23:18
···
我想到的是分成三次秤，編號1~12袋共78枚、編號13~17袋共75枚、編號18~20袋共57枚，秤三次可獲得解答，還有更好的答案嗎，但既然分三次，應該就不用取那麼多枚出來了哈XDD，應該分兩次就可以解答了
^^^^^^ 我這個解答是錯的，同學不要看XDD ^^^^^^
我下面有寫出一個最優解，但不知道有沒有兩次的解
→
fromtokyo

台灣 11-05 23:19
···
GOGO，同學，來個最優解
→
ee2b00

台灣 11-05 23:34
假設20為假

01 每袋都先編號，再都先拿1枚出來

02 分01-10一組，11-20一組

03 因每個金幣有±0.01，故10枚應為100±0.1克
所以01-10那組應為應為100±0.1克，11-20則應為99±0.1克

04 11-20再分為11-15，16-20兩組

05 5枚應為50±0.05克，故此時兩組應為50±0.05.，49±0.05

06 再分為16-17，18-19兩組，加20自己共三組

07 2枚應為20±0.02克，故此時兩組應為20±0.02.，20±0.02

抓到20為9±0.01

故應為3到4次
應該不用那麼多次，最多應該三次內可以解出來，不知道有沒有一次和兩次內的解法

你這個方法也不錯，不知道數學上這個叫什麼，互斥法?排斥法?XOR運算?
→
JosephC0227

台灣 11-05 23:48
一次
從第1袋到第19袋，依次拿 6-24 量
要細述
→
fromtokyo

台灣 11-06 02:48
···
這是我的最優解，期待有人找到兩次以下的解答
將20袋金幣分三次秤，標記編號1~9號共9包，11~19號共9包，剩餘兩包編號21、22

編號1~9袋，依序取出1-9枚，共取出45枚(最大誤差±0.45克)，第一次秤，記錄結果
假如秤出來是450±0.45克(449.55克~450.45克) 表示1~9號袋都是真幣
假如秤出來是449±0.45克(448.55克~449.45克) 表示1號袋是假幣
假如秤出來是448±0.45克(447.55克~448.45克) 表示2號袋是假幣
‧‧‧‧‧
‧‧‧‧‧
‧‧‧‧‧
依此類推

假如第一次秤，結果沒找出假幣，那就進入第二次秤

編號11~19袋，依序取出1-9枚，共取出45枚(最大誤差±0.45克)，第二次秤，記錄結果
假如秤出來是450±0.45克表示11~19號袋都是真幣
假如秤出來是449±0.45克表示11號袋是假幣
假如秤出來是448±0.45克表示12號袋是假幣
‧‧‧‧‧
‧‧‧‧‧
‧‧‧‧‧
依此類推

假如第二次秤，也沒找出假幣，那就進入第三次秤

編號21取出1枚、22取出2枚，第三次秤，記錄結果
假如秤出來是30±0.03克表示21~22號袋都是真幣
假如秤出來是29±0.03克表示21號袋是假幣
假如秤出來是28±0.03克表示22號袋是假幣

find out
→
killerblack

台灣 11-06 00:25
我覺得只要一次，但是這個方式有點偷吃步~

把20袋金幣每袋各取10枚金幣出來並做記號且分成兩邊各10袋，而假幣比真幣少1公克，加上秤最大載種為3KG而且精度到達0.01公克~

也就是說我將兩邊做好記號的金幣一直放上秤子，基本上只要其中放到假幣秤子應該就會很明顯的傾斜~
因為最大載重3KG，所以只要在每次放10枚金幣到秤子的過程中，一旦是假幣秤子應該就會馬上傾斜~就可以知道兩邊其中一邊某袋金幣是假幣~
→
ee2b00

台灣 11-06 00:27
因為有誤差~~所以題目變的很煩呀=3=
→
JosephC0227

台灣 11-06 00:31
欸，我的一次就是剛剛說的，第1袋到第19袋拿 6-24 枚金幣，總共 285 枚
總重量在2852.85-2847.15 中間，表示第20袋是假的
總重量在2846.85-2841.15 中間，表示第 1袋是假的
2845.85-2840.15 => 第二袋
2844.85-2839.15 => 第三袋
以此類推
不得不說，這題意外出得很好，而且真的是「恰到好處的神破解」，在此我對JosephC0227表達Orz的萬分敬佩，但終極解答還是有一點小小失誤，我晚點會將此解答方法轉成程式碼，並將解答序列一一列出來給大家做參考，會直接PO一篇新的文，再連結回這篇。
→
jeffreymoto

台灣 11-06 01:02
樓上破解
神破解無誤！！！
→
newbit

台灣 11-06 04:40
我題目看錯了以為一枚是100克
所以我需要秤兩次！

不過問題還可以延伸的更有趣
已知有285硬幣其中有6-24枚是重9克的假幣秤第一次可知道有幾枚
但是突然間全混在一起了
至少還要秤幾次才能把全部的假幣找出來！
沒關係，再驗證看看上面的算式，上述答案還沒有完全正確，理論已完全正確，但離正確答案只差一點點，若將完整的解答一一序列出來，會發現到中後段的排序很特別
→
haha0205

台灣 11-06 08:12
有時間數數量拿出來做記號再放回去倒不如3袋秤
這也可以應用在大量的數據分析，例如在一個資料庫裡面，有大量的資料需要採用相同的算法，若將此算法精簡化，可提升程式運作的效率。

題目是想用最少次數去秤，求最優解，其實很具思考意義，因為這樣的思考方式，可以訓練推理能力和直覺的找出解答的能力(抽象思考能力)，我印象中愛因斯坦等很多天才，都有這樣的能力，所以可以勇於大膽假設，但卻又很容易命中解答，或很接近解答，所以之後再經過推理、修正、精簡去貼近正確解答，當下可能創造出一些抽象理論(像說E=mc²)，雖然在當時礙於科學驗證能力不夠而無法證實，但在未來，科學驗證能力提升後，便能再一一回頭驗證其理論內容的正確性。

不免想偷偷回馬槍一下台灣的教育體制，台灣的教育體制非常不重視這方面的內容，它比較重視教大家用公式、用制式化的方法去快速獲得解答、獲取高分，而不教大家應用方式，只重視提升大家的「算術」能力，而不重視「邏輯推理能力、抽象思考能力、實際應用在現實層面上的能力」。

從JosephC0227的答案，可以推測出他在這次的解答方式偏重直覺能力(抽象思考能力)，所以直接出來的答案只離正確解答差一點點，而且經過這一次意外創造出的一個好題目(值得永流傳)，和JosephC0227的超神解決方案，我敢肯定他在政治評論方面的能力也會超強，絕對會是值得大家學習的對象(他絕對是深藏不露的高手)
→
huzc0606

台灣 11-06 12:15
JosephC0227的方法和sahuee2003的方法是一樣的，都會因為誤差而遇到誤判或是重疊的情況。舉例~當時如果你量到的是2845，會在這兩袋之間，第1袋:2846.85-2841.15，第二袋:2845.85-2840.15~

基本上我是用間隔6個去取幣，1,7,13,19去取金幣，這樣的幣值總重量因題目限制只能取10袋，所以要分兩次，但誤差的最大最小數值就不會重疊，(你可以寫程式或拉excel來看)，間隔5一樣會有誤差重疊，上下的spec是不能重疊的。

那當然，用JosephC0227的方法和sahuee2003的方法，一樣用兩次就可以解，第一次量出來的數值，會分布在其中相鄰的袋子，卡一下條件就可以找出是那些相鄰的袋子，在從這些袋去分就可以~ 不過第二次分，間隔就要放大到6，不然還是會有些許誤差~
有質疑很好，再去驗證推翻上次可能的解答，很正確的科學態度。

我前面是測過遞迴1+offset到19+offset，然後offset=1到5，只有剛好offset=5時可以解答，會剛好1-19袋，序列出來的所有結果(含重量誤差範圍)，剛好沒有重疊，所以我判斷這就是終極解答方案，我會再回去測試你所提出的部分並檢視我的程式是不是哪裡有問題。

你的解法是目前的最優解，算出來的答案正確，秤兩次以內得解答
→
huzc0606

台灣 11-06 09:45
現實做演算法的話基本就是列好幾種解法，在去看硬體可以突破嗎? 例如總重量如果可以很高，用間隔6一次就可以找出來，或是說我電腦速度快，我分4次都無所謂，因為可以不吃幾記憶體~
現在流行AI演算法，都用微積分推導，挖跨謀，寫成程式碼我才看的懂。
→
huzc0606

台灣 11-06 09:59
我的算法跟JosephC0227列出來上下的重量分布都是一樣~ 確實會重疊~
你的上下重量是跟JosephC0227一樣嗎?
我晚點用電腦跑跑看，昨天隨便弄一下，想說應該沒錯，沒有很仔細的確認

結果是我把程式寫錯，改寫正確後發現，取越多金幣誤差會越大，重疊的部分反而會增加，秤到11袋以上就是一定會重疊，你的解法應該就是最優解。
→
huzc0606

台灣 11-06 13:29
如果分兩次，第一次秤10袋，第一個取1、間隔3以上都可以~ 所以如果你取間隔5與我取6，都可以~
恩對，取間隔的話，就可以一次秤10袋，第一袋取1、第二袋取4、第三袋取7、第四袋取10‧‧‧依此類推
→
smallsu

台灣 11-06 21:03
昨天睡前看到這個問題，結果睡覺時整晚都在思考(暈)
我想到的方法是要用到的是類似古代的秤，用更精緻的概念去推算。
＿＿＿
ミ｜ミ←有標示公克重的彈簧
－┴－
↓　↓
物　物

傳統秤在二物中間重量一樣時會保持平衡，如果重量不同時可以調整左邊物體的距離，藉此產生力矩來平衡重量。這個更精緻的秤是裝上彈簧不用力矩去調整

分二次秤，第一次1~10袋的金幣標記1~10號。
第一包拿10枚，第二包20、第三包30、第四包40、第五包50、第六包60、第七包70、第八包80、第九包90、第十包100
第一包到第七包總和280，共重2800克±2.8克
第八包到第十包總和270，共重2700克±2.7克
如果這二邊剛好誤差100克，出問題的就是11~20包金幣，

因為一次拿10的整數，所以假幣會很明顯的產生重量誤差，差距最小的第一包的10枚會從100克變成90克，此誤差大於最大誤差的5.5克(±2.8與±2.7)。

此方式可以秤二次(1~10與11~20)就知道哪一袋是假金幣了。
看起來會秤超過兩次，假如出問題的是11~20包金幣，還要再秤一次，接著左邊較輕代表12~17包有一包出問題；右邊是18~20有問題，所以還要再找出是哪一包，可能還要再第三、第四次秤？

我有過想問題想到睡著，結果在夢裡得到解題靈感。
→
fromtokyo

台灣 11-06 16:06
···
我的兩次秤方案
1. 將20袋金幣分兩組，各10袋金幣
2. 在第一組的每袋金幣中，各取出1枚(共10枚)、在第二組中的每袋金幣中，各取出2枚金幣(共20枚)
3. 合併共30枚金幣，進行第一次秤重，目的要在這兩組當中，先找出有假幣的一組
如果秤出1枚假幣，則表示第一組中有假幣，總重就是(30*(10±0.01)-1) = 298.7 ~ 299.3
如果秤出2枚假幣，則表示第二組中有假幣，總重就是(30*(10±0.01)-2) = 297.7 ~ 298.3

4. 在假幣組的每袋上面分別編號1~10
5. 在1~9號袋中，依序取出1-9枚，共45枚(最大誤差±0.45克)，最後一次秤，
假如秤出是450±0.45克(449.55克~450.45克) 表示1~9號袋都是真幣，這樣10號就是假幣
假如秤出是449±0.45克(448.55克~449.45克) 表示1號袋是假幣
假如秤出是448±0.45克(447.55克~448.45克) 表示2號袋是假幣
‧‧‧‧‧
‧‧‧‧‧
‧‧‧‧‧
依此類推，兩次即找出解答
→
fromtokyo

台灣 11-06 19:03
···
兩次內秤出方案
1. 將20袋金幣編號1~20，分兩次秤
2. 從1~10號袋中依序取出金幣量1、4、7、10‧‧‧依此類推，共取出145枚金幣，進行第一次秤重，
如果假幣是1號袋，則秤出的重量是1447.55 ~ 1450.45
2號袋，則秤出的重量是1444.55 ~ 1447.45
3號袋，則秤出的重量是1441.55 ~ 1444.45
‧‧‧‧‧
‧‧‧‧‧
‧‧‧‧‧
依此類推，如果沒找出假幣，就要繼續

4. 從11~20號袋中依序取出金幣量1、4、7、10‧‧‧依此類推，共取出145枚金幣，最後一次秤重。
如果假幣是1號袋，則秤出的重量是1447.55 ~ 1450.45
2號袋，則秤出的重量是1444.55 ~ 1447.45
3號袋，則秤出的重量是1441.55 ~ 1444.45
‧‧‧‧‧
‧‧‧‧‧
‧‧‧‧‧
依此類推，找出解答
讚
huzc0606

台灣 11-06 19:56
Good
→
smallsu

台灣 11-06 21:06
我想的方法應該可以二次就解決。第一次秤1~10的沒出來的話，第二次秤11~20。

先對我想的秤解釋清楚點，類似傳統秤桿，二邊等距的地方都是懸吊金幣，在懸吊金幣的位置上面有一個固定秤重的彈簧，如果一邊比較重的時候會拉伸彈簧，秤桿還是維持水平狀態。

分別從
左邊是1~7共280個金幣，右邊8~10共270金幣

全都是真的金幣(10克)
左邊1~7重2800克，右邊8~10是2700克。

左邊1是假的會變成2790克，2會變成2780克
同理3變成2770，4變成2760，5變成2750，6變成2740，7變成2730

右邊8是假的會變成2620克，9會變成2610克，10會變成2600克。

所以只看彈簧秤的部分(左邊比較輕)，落差100g就是全都是真的金幣，90g是1假、80g是2假、70g是3假的、60g是4假的、50g是5假的、40g是6假的、30g是7假的、180g是8假的、190g是9假的、200g是10假的。

(PS：我原本是想10要取110個金幣來達到二邊都是280個的平衡，不過有彈簧秤的部分其實沒平衡也沒關係。)
這個秤可以直接看出左右兩個物件的重量差距多少克and精度可到1克？
→
JosephC0227

台灣 11-06 22:43
我白癡，沒有注意到重複部分，明明就很明顯，我自爆...:(
我有一個類似的想法，可能兩次就可以測出來，還是一樣的方法，等我回家確認完再上傳
但是目前最優解的靈感就來自你的解答
→
JosephC0227

台灣 11-07 01:32
嗯，剛剛沒注意看，原 PO 的方法目前也是我想到的最佳解，把誤差總和拉近到一以內，最早的方法還是可以用的，只是要分兩組各十袋，然後找出輕的那組，取九袋金幣就可以找出答案了。謝謝原 PO ，這個題目很棒
恩恩最多好像只能秤10袋，11袋誤差就一定會重疊

fromtokyo: [問卦] 有二十袋金幣，其中有一袋是假幣，用秤找出假幣 - Gossiping板