Re: [問題] 稱重

看板puzzle (益智遊戲 - 數獨,拼圖,推理,西洋棋)作者isnoneval (流動的語言)時間18年前 (2008/01/16 14:48)推噓1(1推 0噓 1→)

留言2則, 2人參與討論串2/2 (看更多)

※ 引述《flamerecca (werewolf)》之銘言： : 有12個金幣其中有兩個偽造 : 一個較重一個較輕 : 但是兩個重量加起來恰好等於兩個正常的錢幣重量 : (也就是說 10個重量a 一個a+b 一個a-b) : 請問用等臂天平要稱幾次才能 : 1.找出所有偽幣 : 2.找出偽幣並且分出哪個重哪個輕我先說以下的東西我有用程式輔助，而且答案並非巧解，想保留樂趣的人可以先跳過不看。 :3 首先我們來估個下限：第一小題有 C(12,2) = 66 種需要區分的【狀態】，每個狀態中有兩種【組合】，我們稱這兩種組合互為共軛。第二小題有 12*11 = 132 種【組合】。因為 3^3 < 66 < 3^4 < 132 < 3^5，所以兩者分別有 4 與 5 的下限。但是！在第一小題中，扣掉對稱，考慮第一次可能秤法只有：兩邊各擺一個、各擺兩個、... 各擺六個這六種；而不管哪一種秤法，如果某種組合秤出來是不平衡的，則它的共軛組合秤出來的結果必然和它相反。如果某種組合秤出來是平衡的，則它的共軛組合秤出來必然也平衡。什麼意思呢？例如現在有個組合是 1 過重 12 過輕，我們第一次秤 1 2 3 vs 4 5 6，結果是右邊翹起來，那它的共軛組合 (1輕12重) 秤出來一定是左邊翹起來。那這會造成什麼問題呢？就是原本在理想的情況下，共軛的兩組應該是不需要去區分的，如果秤法區分太多的共軛組，最後會超過 81 組，就不可能用 4 次解決了。而事實上因為第一小題的這種性質，假設第一次秤完之後，66 種狀態依結果納入三種，分別是平衡 p 組、左傾 q 組、右傾 r 組，則一定會有： p + q = 66, q = r 這樣無論如何都不可能把三種的組數都壓在 27 以下，所以 4 次解決不用想了，下限提高到 5 次，和第二小題一樣了。現在如果我們可以找到第二小題的 5 次解，那麼這兩題就同時解決了。5 次可能嗎？構造起來好像很難，但理論上有的可能性很大。為什麼？因為秤 5 次足以分出 243 種狀態，拿來拆 132，空隙還滿大的。所以現在我們要嘗試的是： 1.第一次秤出來分成的三區 (平衡左傾右傾) ，每區都要小於 81 組，愈平均愈好。 2.上一步分出的每一區中，第二次秤出來的再三區，每區都要小於 27 組，愈平均愈好。 ... 依此類推如果上面每一步都做得到，5 次解就到手了。 :3 這個用工人智慧是可以硬算的 (就不斷找秤法來用排列組合試算結果) ，大概要花三到五個晚上可以成功。不過我懶得算了，所以驗算組數我是用程式算的。 XD 以下是 5 次解詳細秤法：第一次： 1 2 3 vs 4 5 6 第二次： 1 2 3 = 4 5 6 (42組) → 1 7 vs 4 8 1 2 3 < 4 5 6 (45組) → 1 4 vs 2 5 1 2 3 > 4 5 6 (45組) → 同上第三次： 1 2 3 = 4 5 6, 1 7 = 4 8 (16組) → 9 vs 10 1 7 < 4 8 (13組) → 9 10 vs 11 12 1 7 > 4 8 (13組) → 同上 1 2 3 < 4 5 6, 1 4 = 2 5 (15組) → 1 7 8 vs 4 9 10 1 4 < 2 5 (15組) → 3 7 8 vs 6 9 10 1 4 > 2 5 (15組) → 同上 1 2 3 > 4 5 6, 同上三組, 但 1 4 對調, 2 5 對調, 3 6 對調第四、五次： 1 2 3 = 4 5 6, 1 7 = 4 8, 9 = 10 (6組) → 2 5 11 vs 3 6 12, 2 vs 5 9 < 10 (5組) → 1 2 3 vs 10 11 12, 11 vs 12 9 > 10 (5組) → 同上 1 7 < 4 8, 9 10 = 11 12 (5組) → 1 2 3 vs 5 6 7, 2 5 vs 3 6 9 10 < 11 12 (5組) → 1 2 vs 7 8, 9 11 vs 10 12 9 10 > 11 12 (5組) → 同上 1 7 < 4 8, 同上三組, 但 1 4 對調, 7 8 對調 1 2 3 < 4 5 6, 1 4 = 2 5, 1 7 8 = 4 9 10 (6組) → 9 10 vs 11 12, 3 11 vs 5 12 1 7 8 < 4 9 10 (5組) → 7 vs 8, 9 vs 10 1 7 8 > 4 9 10 (4組) → 恰好同上 1 4 < 2 5, 3 7 8 = 6 9 10 (5組) → 1 vs 5, 11 vs 12 3 7 8 < 6 9 10 (6組) → 1 vs 5, 7 9 vs 8 10 3 7 8 > 6 9 10 (4組) → 7 vs 8, 9 vs 10 1 4 > 2 5, 同上三組, 但 1 2 對調, 4 5 對調我沒有詳細驗算，但是應該都對了。 -- 這篇裡應該就有點牽涉到上次說的解題方法論... -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 71.37.32.84 ※ 編輯: isnoneval 來自: 71.37.32.84 (01/16 14:51)