作者isnoneval (流动的语言)
看板puzzle
标题Re: [问题] 称重
时间Wed Jan 16 14:48:36 2008
※ 引述《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)
1F：推 puzzlez:所以结论是，5次就可以确保找出？ 01/16 14:52
2F：→ isnoneval:是的, 我来写清楚一点 01/16 14:56
※ 编辑: isnoneval 来自: 71.37.32.84 (01/16 14:56)