稱重 - 拼圖

※ 引述《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 對調

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

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

--