用编码规则巧解天平称球问题

gxqcn

12个球和一个天平，现知道只有一个和其它的重量不同(轻或重)，问怎样称才能用三次就找到那个球？ 这个问题相信很多人做过，大多是采用分类讨论的模式。 下面介绍一个非常巧妙的解答（估计知道的人不多）： 将12个球编号：1～6，8～13

次数	左盘	右盘	记录
1	1, 2, 8, 13	4, 5, 10, 11	a
2	3, 6, 11, 13	2, 4, 5, 12	b
3	5, 9, 11, 13	6, 8, 10, 12	c

称量过程中，若左边重则记录1，右边重则记录(-1)，相等则记录0 假设记录结果为 a,b,c，令 n=a+3b+9c ， 则 |n| 号球的质量与其它的不同；若 (-1)ⁿ⁺¹ * n > 0 则该球重了，否则该球轻了。 注：上述解法是在老的 数学研发论坛（2001.03.12建；现已废弃）上一网友在 2001/12/27 给出的巧妙解答。 该网友同时抛出了如下问题：

推广（已经解决）： 　　1、三分球的推广：给3^n个球编号1-3^n，其中有且仅有1个球质量与其它的球不同，若此球号码≤m，则该球重了，否则轻了。 问：如何通过n次将此球称出？其中，n≥1，1≤m≤3^n 　　2、12球问题的推广：给 (3^n-3)/2个球 (n>1)，其中有且仅有1个球质量与其它的球不同，问：如何通过n次将此球称出？ 问题（尚未解决）： 　　1、有n个球，其中有2个（或多个）球质量与其它的不同，问：需要多少次能够称出这些球？ 　　2、有n个球，及此n个球的质量，但球与质量对不上号，问：如何以最少的称量次数使球与质量一一对应？

gxqcn

请大家探索一下，上面的编码规则是什么？ 可以推广吗？如何推广？

g99

为什么？

无心人

1, 0, -1的三进制吧

gxqcn

该编码规则很容易获得，确实与 { -1，0，1 } 三进制有关。 略作推广，我用得到了如下问题的解决方案： ——39小球通过4次称量，找出唯一质量不同于其它的那个小球，并判断它是属于偏轻或是偏重？ 1、首先对这39个小球编号：用前40个正整数，但跳空“20”号； 2、按如下编号组合称量：

1. 1L: 1, 2, 7, 8, 13, 14, 19, 25, 26, 31, 32, 37, 38
2. 1R: 4, 5, 10, 11, 16, 17, 22, 23, 28, 29, 34, 35, 40
4. 2L: 3, 6, 11, 13, 14, 16, 21, 24, 29, 31, 32, 34, 39
5. 2R: 2, 4, 5, 7, 12, 15, 22, 23, 25, 30, 33, 38, 40
7. 3L: 5, 7, 9, 11, 13, 14, 16, 18, 22, 33, 35, 37, 39
8. 3R: 6, 8, 10, 12, 15, 17, 19, 21, 32, 34, 36, 38, 40
10. 4L: 15, 17, 19, 21, 23, 25, 27, 29, 31, 33, 35, 37, 39
11. 4R: 14, 16, 18, 22, 24, 26, 28, 30, 32, 34, 36, 38, 40

复制代码

称量过程中，若左边重则记录1，右边重则记录(-1)，相等则记录0 假设记录结果依次为 a,b,c,d，得到 n=a+3*b+9*c+27*d 3、判定结果：|n| 号球的质量与其它的不同；若 (-1)ⁿ * n < 0 则该球重了，否则该球轻了。 上述方案的最大特色是无须讨论； 且各次称量无前后依赖关系，可部分并行处理， 比如说在称量的同时，可将占总数1/3的余下小球预先分类以备下次称量。

gxqcn

1L: 1, 2, 7, 8, 13, 14, 19, 20, 25, 26, 31, 32, 37, 38, 43, 44, 49, 50, 55, 56, 62, 67, 68, 73, 74, 79, 80, 85, 86, 91, 92, 97, 98, 103, 104, 109, 110, 115, 116, 121 1R: 4, 5, 10, 11, 16, 17, 22, 23, 28, 29, 34, 35, 40, 41, 46, 47, 52, 53, 58, 59, 64, 65, 70, 71, 76, 77, 82, 83, 88, 89, 94, 95, 100, 101, 106, 107, 112, 113, 118, 119 2L: 3, 6, 11, 13, 14, 16, 21, 24, 29, 31, 32, 34, 39, 42, 47, 49, 50, 52, 57, 60, 65, 67, 68, 70, 75, 78, 83, 85, 86, 88, 93, 96, 101, 103, 104, 106, 111, 114, 119, 121 2R: 2, 4, 5, 7, 12, 15, 20, 22, 23, 25, 30, 33, 38, 40, 41, 43, 48, 51, 56, 58, 59, 66, 69, 74, 76, 77, 79, 84, 87, 92, 94, 95, 97, 102, 105, 110, 112, 113, 115, 120 3L: 5, 7, 9, 11, 13, 14, 16, 18, 20, 22, 33, 35, 37, 39, 42, 44, 46, 48, 59, 63, 65, 67, 68, 70, 72, 74, 76, 87, 89, 91, 93, 96, 98, 100, 102, 113, 115, 117, 119, 121 3R: 6, 8, 10, 12, 15, 17, 19, 21, 32, 34, 36, 38, 40, 41, 43, 45, 47, 49, 60, 62, 64, 66, 69, 71, 73, 75, 86, 88, 90, 92, 94, 95, 97, 99, 101, 103, 114, 116, 118, 120 4L: 15, 17, 19, 21, 23, 25, 27, 29, 31, 33, 35, 37, 39, 42, 44, 46, 48, 50, 52, 54, 56, 58, 60, 62, 64, 66, 95, 97, 99, 101, 103, 105, 107, 109, 111, 113, 115, 117, 119, 121 4R: 14, 16, 18, 20, 22, 24, 26, 28, 30, 32, 34, 36, 38, 40, 41, 43, 45, 47, 49, 51, 53, 55, 57, 59, 63, 65, 67, 96, 98, 100, 102, 104, 106, 108, 110, 112, 114, 116, 118, 120 5L: 41, 43, 45, 47, 49, 51, 53, 55, 57, 59, 63, 65, 67, 69, 71, 73, 75, 77, 79, 81, 83, 85, 87, 89, 91, 93, 95, 97, 99, 101, 103, 105, 107, 109, 111, 113, 115, 117, 119, 121 5R: 42, 44, 46, 48, 50, 52, 54, 56, 58, 60, 62, 64, 66, 68, 70, 72, 74, 76, 78, 80, 82, 84, 86, 88, 90, 92, 94, 96, 98, 100, 102, 104, 106, 108, 110, 112, 114, 116, 118, 120

编号跳空第61号。附件是对应的excel表，另外还用到了 PowCalc 进行智能提取数据。

shshsh_0510

这个还是有点复杂，但网上有不少，比如 http://blog.csdn.net/bsbgong/archive/2009/02/11/3876171.aspx 转贴如下： 今天方博士给我们出了一个12小球的问题，并提供了一个3进制的解决方案，确实不错。。。赞一个！博士！ 后来我想把这种处理方式记录下来，说不定以后有其他的问题可以参考这种方式来解决呢。。。再去网上查了一下，找到了一个号称最牛的解答，转过来记录之。。。 另：先给出一个最牛的次数判定的方法，信息论的完美应用！赞！ 从信息论来看，12个球一个重量异常，出现概率1/12；该球质量可能轻也可能重，那么出现概率为1/2。 那么要得到结果所需信息量为log2+log12。 称一次可能有轻、重、相等三种结果，信息量为log3。log24/log3<3，三次应该能称出来。 这样的话，可以直接给出N个小球问题的称量次数了。。。 天平称重，有两个托盘比较轻重，加上托盘外面，也就是每次称重有3个结果，就是ln3/ln2比特信息。n个球要知道其中一个不同的球，如果知道那个不同重量的球是轻还是重，找出来的话那就是n个结果中的一种，就是有ln(n)/ln2比特信息，如果不知道轻重，找出来就是2n（n个球中的一个，轻或者重，所以是2n）个结果中的一种，那就是ln(2n)/ln2比特信息。 假设我们要称k次，根据信息理论，那显然两种情况就分别有： （1） k*ln3/ln2>=ln(n)/ln2, 解得k>=ln(n)/ln3 （2） k*ln3/ln2>=ln(2n)/ln2 (k>1) 解得k>=ln(2n)/ln3 12个球称3次找坏球的完美解答 古老的智力题详述: 有12个球特征相同,其中只有一个重量异常,要求用一部没有砝码的天平称三次,将那个重量异常的球找出来。 网上的最多的方法是逻辑法,还有少数画成图的所谓策略树和基于此的程序算法.这道题有13种不同的答案.这里我提出一种新的完全的数学解法: 一·首先提出称量的数学模型: 把一次称量看成一个一次代数式,同样问题就可以描述成简单的矩阵方程求解问题.怎么把一次称量表示成一个代数式呢? 1),简化描述小球的重量(状态)----正常球重量设为0,设异常球比正常球重为1或轻为-1,异常球未知轻重时用x代表(只取1或-1).用列向量j表示所有球的重量状态. 2),简化描述称量的左右(放法)-----把某号球放左边设为1,右边设为-1,不放上去设为0.用行向量i表示某次称量所有球的左右状态. 3),描述称量结果: 由1),2)已经可以确定一个称量式 ∑各球的重量*放法=天平称量结果.--------(1)式 如果我们用向量j,i分别表示球的重量状态和球的左右放法情况(j为行向量,i为列向量),对于(1)式,可以改写为 j*i=a(常数a为单次称量结果) -------------(2)式 例如有1-6号共6个小球,其中4号为较重球,拿3号5号放左边,1号4号放右边进行称量,式子为: (-1)*0+0*0+1*0+(-1)*1+1*0+0*0=-1, 从-1的意义可以知道它表示结果的左边较轻; 同样可以得到0表示平衡,1表示左边较重. 4),方程用来描述称量过程,还需附加一个重要的条件:代表放左边的1和右边的-1个数相等,也就是 ∑各球的放法=0-------------------------(3)式 这样就解决了称量的数学表达问题. 对于12个小球的3次称量,分别用12维行向量j1,j2,j3表示,由j1j2j3便构成了3×12的称量矩阵J；对于某一可能情况i,对应的3次称量结果组成的3维列向量b,得 J*i=b 二·称球问题的数学建模 问题的等价： 设J为3×12的矩阵，满足每行各项之和为0。i为12维列向量,i的某一项为1或－1，其他项都是0，即i是12×24的分块矩阵M=(E,-E)的任一列。而3×27的矩阵C为由27个互不相同的3维列向量构成，它的元素只能是1,0,-1. 由问题的意义可知b=J*i必定是C的某一列向量。而对于任意的i,有由J*i=b确定的b互不相同. 即 J*M=J*(E,-E)=(B,-B)=X -----（设X为3×24的矩阵） 因为X为24列共12对互偶的列向量，而C为27列，可知从C除去的3列为(0,0,0)和1对任意的互偶的列向量，这里取除(1,1,1)和(-1,-1,-1). 由上式得J*E=B推出J=B,X=(J,-J)。因此把从27个3维列向量中去除(0,0,0),(1,1,1),(-1,-1,-1)然后分为互偶的两组(对应取反) [ 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1]; [ 0, 1, 1, 1, 0, 0, 0, 1, 1,-1,-1,-1]; [ 1, 0, 1,-1, 0, 1,-1, 0,-1, 0, 1,-1]. [ 0, 0, 0, 0,-1,-1,-1,-1,-1,-1,-1,-1]; [ 0,-1,-1,-1, 0, 0, 0,-1,-1, 1, 1, 1]; [-1, 0,-1, 1, 0,-1, 1, 0, 1, 0,-1, 1]. 现在通过上下对调2列令各行的各项和为0！！即可得到J.我的方法是从右到左间隔着进行上下对调，然后再把2排和3排进行上下对调，刚好所有行的和为0。得 称量矩阵J= [0, 0, 0, 0, 1,-1, 1,-1, 1,-1, 1,-1]; [0, 1,-1,-1, 0, 0, 0,-1, 1, 1,-1, 1]; [1, 0,-1, 1, 0,-1,-1, 0,-1, 0, 1, 1]. 相应三次称量两边的放法： 左边5，7，9，11 ：右边6，8，10，12； 左边2，9，10，12：右边3，4，8，11； 左边1，4，11，12：右边3，6，7，9 。 *********** ********** ************ ********** 1号球，且重 －平、平、左 1号球，且轻 －平、平、右 2号球，且重 －平、左、平 2号球，且轻 －平、右、平 3号球，且重 －平、右、右 3号球，且轻 －平、左、左 4号球，且重 －平、右、左 4号球，且轻 －平、左、右 5号球，且重 －左、平、平 5号球，且轻 －右、平、平 6号球，且重 －右、平、右 6号球，且轻 －左、平、左 7号球，且重 －左、平、右 7号球，且轻 －右、平、左 8号球，且重 －右、右、平 8号球，且轻 －左、左、平 9号球，且重 －左、左、右 9号球，且轻 －右、右、左 10号球，且重－右、左、平 10号球，且轻－左、右、平 11号球，且重－左、右、左 11号球，且轻－右、左、平 12号球，且重－右、左、左 12号球，且轻－左、右、右 三·问题延伸 1，13个球称3次的问题： 从上面的解答中被除去的3个向量为(0,0,0)(1,1,1)(-1,-1,-1).而要能判断第13个球，必须加入1对对偶向量，如果加入的是(1,1,1)(-1,-1,-1),则 [ 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1，1]; [ 0, 1, 1, 1, 0, 0, 0, 1, 1,-1,-1,-1，1]; [ 1, 0, 1,-1, 0, 1,-1, 0,-1, 0, 1,-1，1]. [ 0, 0, 0, 0,-1,-1,-1,-1,-1,-1,-1,-1,-1]; [ 0,-1,-1,-1, 0, 0, 0,-1,-1, 1, 1, 1,-1]; [-1, 0,-1, 1, 0,-1, 1, 0, 1, 0,-1, 1,-1]. 第一行的非0个数为奇数，不论怎么调也无法使行和为0。故加入的行只能为自对偶列向量(0,0,0),结果是异球可判断是否是第13球时却无法检查轻重。也可见，13球称3次的问题和12球称3次的问题只是稍有不同，就如12个球问题把球分3组4个称，而13个球问题把球分4组(4,4,4,1),第13个球单独1组。 2，(3^N-3)/2个球称N次找出异球且确定轻重的通解： 第一步，先给出3个球称2次的一个称量矩阵J2 [ 0, 1,-1]; [-1, 0, 1]. 第二步，设Kn=(3^N-3)/2个球称N次的称量矩阵为N行×Kn列的矩阵Jn,把(3^N/3-3)/2个球称N-1次的称量矩阵J简写为J.再设N 维列向量Xn,Yn,Zn分别为(0,1,1,...,1),(1,0,0,...,0),(1,-1,-1,...,-1). 第三步之1，在N-1行的矩阵J上面添加1行各项为0，成新的矩阵J'. 第三步之2，在N-1行的矩阵J上面,添加行向量t=(1,1,...,1,-1,-1,...,-1),成新的矩阵J".t的维(长)和J的列数一致，t 的前面各项都是1，后面各项都是－1；t的长为偶数时，1个数和－1个数相等；t的长为奇数时，1个数比－1个数少1个； 第三步之3，在N-1行的矩阵-J上面,添加行向量t=(1,1,...,1,-1,-1,...,-1),成新的矩阵J"'. 第四步，当J的列数即t的长为奇数时，用分块矩阵表示矩阵Jn＝(J',J",J"',Xn,Yn,Zn);当J的列数即t的长为偶数时，用分块矩阵表示矩阵Jn＝(J',J",J"',Xn,-Yn,Zn); 此法可以速求出一个J3为 [ 0, 0, 0, 1,-1,-1, 1,-1,-1, 0, 1, 1]; [ 0, 1,-1, 0, 1,-1, 0,-1, 1, 1, 0,-1]; [-1, 0, 1, -1, 0, 1, 1, 0,-1, 1, 0,-1]. 同样可以继续代入求出J4,J5的称量矩阵。 3，2类主要的推广： 第1类，有(3^n-3)/2个球，其中有一个异球，用天平称n次，出该球并确定是较轻还是较重。 第2类， 有n个球，其中混入了m个另一种规格的球，但是不知道异球比标球重还是轻，称k次把他们分开并确定轻重？ 显然，上面的推广将球分为了两种，再推广为将球分为n种时求称法。 对于第一类推广，上面已经给出了梯推的通解式。而对于第二类推广，仅对于m=2时的几个简单情况有了初步的了解，如5个球称3次找出2个相同的异球，9个球称4次找出2个相同的异球，已经获得了推理逻辑方法上的解决，但是在矩阵方法上仍未理出头绪，16个球称5次找出2个相同的异球问题上普通的逻辑方法变得非常烦琐以至未知是否有解，希望有高手能继续用矩阵方法找出答案，最好能获得m=2时的递推式。 上面的通解法得到的J4= [ 0,0, 0, 0, 0, 0,0, 0, 0,0,0, 0, 1,1, 1, 1, 1, 1,-1,-1,-1,-1,-1,-1,1, 1, 1, 1, 1, 1,-1,-1,-1,-1,-1,-1,0,-1, 1]; [ 0,0, 0, 1,-1,-1,1,-1,-1,0,1, 1, 0,0, 0, 1,-1,-1, 1,-1,-1, 0, 1, 1,0, 0, 0,-1, 1, 1,-1, 1, 1, 0,-1,-1,1, 0,-1]; [ 0,1,-1, 0, 1,-1,0,-1, 1,1,0,-1, 0,1,-1, 0, 1,-1, 0,-1, 1, 1, 0,-1,0,-1, 1, 0,-1, 1, 0, 1,-1,-1, 0, 1,1, 0,-1]; [-1,0, 1,-1, 0, 1,1, 0,-1,1,0,-1,-1,0, 1,-1, 0, 1, 1, 0,-1, 1, 0,-1,1, 0,-1, 1, 0,-1,-1, 0, 1,-1, 0, 1,1, 0,-1].

gxqcn

我用编码法与上面的矩阵法理论依据基本是一致的， 但编码法很容易程序化设计，无须人工调整。 （在6#我特意将execl表上传，以便大家了解流程） 我最欣赏编码法的是结果无须查表， 经过简单的计算就可以直接确定出是哪个球异常，并判断出是偏轻还是偏重。

mathe

复旦BBS数学版很早以前就讨论过并且有很好的结论的: http://bbs.fudan.edu.cn/cgi-bin/ ... ems/prob/weightball

dobear

确实很巧妙，有空好好看看