稱重 - 拼圖
By Eartha
at 2008-01-16T14:48
at 2008-01-16T14:48
Table of Contents
※ 引述《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 對調
我沒有詳細驗算,但是應該都對了。
--
這篇裡應該就有點牽涉到上次說的解題方法論...
--
: 有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 對調
我沒有詳細驗算,但是應該都對了。
--
這篇裡應該就有點牽涉到上次說的解題方法論...
--
Tags:
拼圖
All Comments
By Dora
at 2008-01-17T02:38
at 2008-01-17T02:38
By Callum
at 2008-01-18T12:23
at 2008-01-18T12:23
Related Posts
孤獨的N
By Anthony
at 2008-01-14T20:58
at 2008-01-14T20:58
小町算
By Faithe
at 2008-01-14T20:08
at 2008-01-14T20:08
小町蛀蟲算 007
By Donna
at 2008-01-14T19:22
at 2008-01-14T19:22
請問拼圖專用墊會傷害拼塊本身嗎?
By Jake
at 2008-01-14T13:22
at 2008-01-14T13:22
實體益智玩具的介紹項目
By Ida
at 2008-01-14T12:01
at 2008-01-14T12:01