看板 Gossiping
作者 標題 [問卦] 有二十袋金幣，其中有一袋是假幣，用秤找出假幣
時間 2019-11-05 Tue. 21:20:50
題目: 這裡有二十袋金幣和一個超高精度秤±0.01克，秤的測量上限是3KG
已知: 每袋金幣有100枚±10枚，其中有一袋是假幣，
1枚真幣重量是10公克±0.01克，而假幣又比真幣少1公克。
請問: 最少需要使用幾次秤，才能找出哪一袋是假幣？
--
※ 編輯: fromtokyo 時間: 2019-11-05 21:39:51 (台灣)
※ 看板: Gossiping 文章推薦值: 2 目前人氣: 0 累積人氣: 1867
(￣︶￣)ｂ tsukiyumi 說讚！
2樓 時間: 2019-11-05 21:51:00 (台灣)
→
+1
11-05 21:51 TW
因一次最多只能秤30枚所以只秤一次 訊息量不夠 頂多是判斷出假幣落在那五袋之中！
1枚10公克±0.01克，秤299枚沒問題
3樓 時間: 2019-11-05 21:53:01 (台灣)
→
+1
11-05 21:53 TW
只能秤重應該找不出來吧？你有答案嗎？
只能秤重可以找出來，關鍵在需要秤幾次
4樓 時間: 2019-11-05 21:54:58 (台灣)
→
+1
11-05 21:54 TW
1次的原因是因為只問『最少』用幾次，所以的確有隨便抓一袋就剛好抓到的1次可能性
可以，算你過，還有別的答案嗎
5樓 時間: 2019-11-05 21:56:58 (台灣)
→
+1
11-05 21:56 TW
答案該不會是每袋拿一枚出來秤，最多四次就知道哪袋都假的。 整袋秤會因為公差使真假幣重量完全一樣啊。
要詳述怎麼秤
6樓 時間: 2019-11-05 22:14:36 (台灣)
→
+1
11-05 22:14 TW
每袋各拿一個並做記號，全部放在磅秤上；一次拿一個起來，觀察每次減少的重量，這樣應該可以判斷哪一袋是假的
可以，要詳述過程，怎麼秤，預期要秤幾次可以找出來。
7樓 時間: 2019-11-05 22:25:06 (台灣)
→
+4
11-05 22:25 TW
答案→秤一次即可 第一袋取1敉，第二袋取2敉，以此類推第二十袋取20敉 這樣總共會有210敉，210敉若每個10克 若都是真幣總共會有2100克 但是有一袋是假幣，就看少了多少克除以十，就知道是哪一袋了
正解出現！但是你的詳細描述有點小bug，你要說在二十袋金幣的袋子上面，依序標註編號1~20號袋，然後編號1取出1枚、編號2取出2枚‧‧‧依此類推^^^^^^ee2b00 同學找到新狀況，在考量到誤差時，210枚誤差最大可達±2.1克， 所以正確解答可能還需要繼續拆分解題，請同學繼續往前推，最終解答快出來了
9樓 時間: 2019-11-05 22:48:07 (台灣)
→
+1
(編輯過) TW
樓上的方法只適用真金幣全都一樣重的情況喔~~現在的情況設定有±0.01的可能了~~所以不合了喔
合的，因為±0.01公克的誤差小的可以忽略，在最差情況下的誤差影響也不及±0.2公克^^^^^^^^^^^^^^這邊我沒注意到總數是210枚，所以最多誤差可以到±2.1克，所以可能還需要拆分解題，那麼現在我們繼續往前推，共約需要秤多少次才能取得正解呢。
10樓 時間: 2019-11-05 22:57:27 (台灣)
→
+1
11-05 22:57 TW
不對喔~~由於有20袋~~所以在有誤差的情況會有『+2.1到-2.1』~~ 也就是有4.2的可能誤差喔~~會有差到2個金幣的可能性
好像真的是，我看看，沒錯，同學抓到重點了，所以正解又要變囉，誰能推出正解呢
11-05 23:12 TW
╳
fromtokyo:[自己刪除]
12樓 時間: 2019-11-05 23:18:33 (台灣)
→
(編輯過) TW
···
^^^^^^ 我這個解答是錯的，同學不要看XDD ^^^^^^ 我下面有寫出一個最優解，但不知道有沒有兩次的解
14樓 時間: 2019-11-05 23:34:23 (台灣)
→
+1
(編輯過) TW
假設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.0506 再分為16-17，18-19兩組，加20自己共三組07 2枚應為20±0.02克，故此時兩組應為20±0.02.，20±0.02抓到20為9±0.01故應為3到4次
應該不用那麼多次，最多應該三次內可以解出來，不知道有沒有一次和兩次內的解法你這個方法也不錯，不知道數學上這個叫什麼，互斥法?排斥法?XOR運算?
17樓 時間: 2019-11-06 00:25:12 (台灣)
→
+1
11-06 00:25 TW
我覺得只要一次，但是這個方式有點偷吃步~把20袋金幣每袋各取10枚金幣出來並做記號且分成兩邊各10袋，而假幣比真幣少1公克，加上秤最大載種為3KG而且精度到達0.01公克~也就是說我將兩邊做好記號的金幣一直放上秤子，基本上只要其中放到假幣秤子應該就會很明顯的傾斜~ 因為最大載重3KG，所以只要在每次放10枚金幣到秤子的過程中，一旦是假幣秤子應該就會馬上傾斜~就可以知道兩邊其中一邊某袋金幣是假幣~
19樓 時間: 2019-11-06 00:31:54 (台灣)
→
+2
11-06 00:31 TW
欸，我的一次就是剛剛說的，第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一篇新的文，再連結回這篇。
21樓 時間: 2019-11-06 04:40:44 (台灣)
→
+1
11-06 04:40 TW
我題目看錯了 以為一枚是100克 所以我需要秤兩次！不過問題還可以延伸的更有趣 已知有285硬幣 其中有6-24枚是重9克的假幣 秤第一次可知道有幾枚 但是突然間全混在一起了 至少還要秤幾次 才能把全部的假幣找出來！
沒關係，再驗證看看上面的算式，上述答案還沒有完全正確，理論已完全正確，但離正確答案只差一點點，若將完整的解答一一序列出來，會發現到中後段的排序很特別
22樓 時間: 2019-11-06 08:12:33 (台灣)
→
+1
(編輯過) TW
有時間數數量拿出來做記號再放回去 倒不如3袋秤
這也可以應用在大量的數據分析，例如在一個資料庫裡面，有大量的資料需要採用相同的算法，若將此算法精簡化，可提升程式運作的效率。題目是想用最少次數去秤，求最優解，其實很具思考意義，因為這樣的思考方式，可以訓練推理能力和直覺的找出解答的能力(抽象思考能力)，我印象中愛因斯坦等很多天才，都有這樣的能力，所以可以勇於大膽假設，但卻又很容易命中解答，或很接近解答，所以之後再經過推理、修正、精簡去貼近正確解答，當下可能創造出一些抽象理論(像說E=mc²)，雖然在當時礙於科學驗證能力不夠而無法證實，但在未來，科學驗證能力提升後，便能再一一回頭驗證其理論內容的正確性。不免想偷偷回馬槍一下台灣的教育體制，台灣的教育體制非常不重視這方面的內容，它比較重視教大家用公式、用制式化的方法去快速獲得解答、獲取高分，而不教大家應用方式，只重視提升大家的「算術」能力，而不重視「邏輯推理能力、抽象思考能力、實際應用在現實層面上的能力」。從JosephC0227的答案，可以推測出他在這次的解答方式偏重直覺能力(抽象思考能力)，所以直接出來的答案只離正確解答差一點點，而且經過這一次意外創造出的一個好題目(值得永流傳)，和JosephC0227的超神解決方案，我敢肯定他在政治評論方面的能力也會超強，絕對會是值得大家學習的對象(他絕對是深藏不露的高手)
23樓 時間: 2019-11-06 12:15:30 (台灣)
→
+1
(編輯過) TW
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袋，序列出來的所有結果(含重量誤差範圍)，剛好沒有重疊，所以我判斷這就是終極解答方案，我會再回去測試你所提出的部分並檢視我的程式是不是哪裡有問題。你的解法是目前的最優解，算出來的答案正確，秤兩次以內得解答
24樓 時間: 2019-11-06 09:45:59 (台灣)
→
+1
11-06 09:45 TW
現實做演算法的話基本就是列好幾種解法，在去看硬體可以突破嗎? 例如總重量如果可以很高，用間隔6一次就可以找出來，或是說我電腦速度快，我分4次都無所謂，因為可以不吃幾記憶體~
現在流行AI演算法，都用微積分推導，挖跨謀，寫成程式碼我才看的懂。
25樓 時間: 2019-11-06 09:59:17 (台灣)
→
+1
11-06 09:59 TW
我的算法跟JosephC0227列出來上下的重量分布都是一樣~ 確實會重疊~ 你的上下重量是跟JosephC0227一樣嗎?
我晚點用電腦跑跑看，昨天隨便弄一下，想說應該沒錯，沒有很仔細的確認結果是我把程式寫錯，改寫正確後發現，取越多金幣誤差會越大，重疊的部分反而會增加，秤到11袋以上就是一定會重疊，你的解法應該就是最優解。
26樓 時間: 2019-11-06 13:29:42 (台灣)
→
+1
11-06 13:29 TW
如果分兩次，第一次秤10袋，第一個取1、間隔3以上都可以~ 所以如果你取間隔5與我取6，都可以~
恩對，取間隔的話，就可以一次秤10袋，第一袋取1、第二袋取4、第三袋取7、第四袋取10‧‧‧依此類推
11-06 14:45 TW
╳
smallsu:[自己刪除]
28樓 時間: 2019-11-06 21:03:44 (台灣)
→
+1
(編輯過) TW
昨天睡前看到這個問題，結果睡覺時整晚都在思考(暈) 我想到的方法是要用到的是類似古代的秤，用更精緻的概念去推算。 ＿＿＿ ミ｜ミ←有標示公克重的彈簧 －┴－ ↓ ↓ 物 物傳統秤在二物中間重量一樣時會保持平衡，如果重量不同時可以調整左邊物體的距離，藉此產生力矩來平衡重量。這個更精緻的秤是裝上彈簧不用力矩去調整分二次秤，第一次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有問題，所以還要再找出是哪一包，可能還要再第三、第四次秤？我有過想問題想到睡著，結果在夢裡得到解題靈感。
32樓 時間: 2019-11-06 21:06:27 (台灣)
→
+1
(編輯過) TW
我想的方法應該可以二次就解決。第一次秤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克？
33樓 時間: 2019-11-06 22:43:00 (台灣)
→
+1
11-06 22:43 TW
我白癡，沒有注意到重複部分，明明就很明顯，我自爆...:( 我有一個類似的想法，可能兩次就可以測出來，還是一樣的方法，等我回家確認完再上傳
但是目前最優解的靈感就來自你的解答
34樓 時間: 2019-11-07 01:32:59 (台灣)
→
+1
11-07 01:32 TW
嗯，剛剛沒注意看，原 PO 的方法目前也是我想到的最佳解，把誤差總和拉近到一以內，最早的方法還是可以用的，只是要分兩組各十袋，然後找出輕的那組，取九袋金幣就可以找出答案了。謝謝原 PO ，這個題目很棒
恩恩最多好像只能秤10袋，11袋誤差就一定會重疊
回列表(←)
分享