稱重 - 拼圖

Eartha avatar
By Eartha
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 對調

我沒有詳細驗算,但是應該都對了。

--
這篇裡應該就有點牽涉到上次說的解題方法論...

--
Tags: 拼圖

All Comments

Dora avatar
By Dora
at 2008-01-17T02:38
所以結論是,5次就可以確保找出?
Callum avatar
By Callum
at 2008-01-18T12:23
是的, 我來寫清楚一點

孤獨的N

Anthony avatar
By Anthony
at 2008-01-14T20:58
從Wiki和網路上找到的(孤獨的7在1925由Odlin發表) 孤獨的4 孤獨的6 孤獨的7 □□□ □□□ □7□□□ ————— ...

小町算

Faithe avatar
By Faithe
at 2008-01-14T20:08
:在歐美,類似的謎題稱為「century puzzle」,不過算式的形式很自由。重點僅在於使用 :1~9的數字而不重覆。例如: :96+(1428/357)=100 共有11個答案 3+69258/714 81+5643/297 81+7524/396 ...

小町蛀蟲算 007

Donna avatar
By Donna
at 2008-01-14T19:22
四連號特輯...XD 請完成下列等式 每個空心符號(■以外)都代表1~9其中一個數字 1. ○□△ x ○□△ x ○□△ = ■■■■■△△△△ 2. ○□△ x ○□△ x ( ○ + ○□△ ) = ■■▽▽▽▽■ 3. ( ○ + ○□ ) x ( □ + ○□ ) x ○□ = △△△△ ...

請問拼圖專用墊會傷害拼塊本身嗎?

Jake avatar
By Jake
at 2008-01-14T13:22
嗯,沒想到有潛水版友也覬覦這項產品XD 基本上我想本版版友大多數是學生 就算不是學生,一次要花個幾千塊還是會猶豫一下 所以在此團成行之前 還是只有存錢、存錢、再存錢 (每天投個10元在你的小豬裡吧~) 而且這項產品算滿貴的,國外運費也很恐怖 所以我想不會有人禁得起「退貨」或「反悔」的打擊 此外,要怎麼交錢 ...

實體益智玩具的介紹項目

Ida avatar
By Ida
at 2008-01-14T12:01
請問各位 在介紹一個「實體益智玩具」的時候 應該要具備哪些「項目」呢? 實體益智玩具,當然是指可以拿在手上把玩的那種囉! 茲貼之前所介紹的方式: 類型:拼板類 品名:The Ultimate Puzzle──終極四角拼圖 製造年份: 作者: 製造廠商:thepuzzle.biz 網址:http://ww ...