12个球称3次找坏球的数学解答(原作者-方).docx

序篇（4-4-4分组整体称法）古老的智力题详述:有12个球特征相同,其中只有一个重量异常,要求用一部没有砝码的天平称三次,将那个重量异常的球找出来。以下会给4个解答，一个比一个牛，一个比一个震撼！第一篇先给个被号称网上最牛的解答，一种新的完全的数学解法（线代+信息论），该文解法创于2005年，一次与友人聊天建议发表到QQ346546618的个人空间（2006年7月），后被网友转载到各大网站并被收入到百度文库。第二篇会给个EXCEL进阶解法，网友们可以用此法加上分块矩阵的方法继续找出9球称4次找2异常球的具体解法或更复杂的称球问题。第三篇会给出2个很漂亮完美的非常特别的解，其称量结果的三进制和异常球序号及和轻重状态具有简洁的一一对应关系。 先给个444分组的具体称量方案：把12个球编成1，2.12号，则可设计下面的称法： 左盘 * 右盘 第一次 1，5，6，12 * 2，3，7，11 第二次 2，4，6，10 * 1，3，8，12 第三次 3，4，5，11 * 1，2，9，10 每次都可能有平、左重、右重三种结果，搭配起来共有27种结果，但平、平、平的结果不会出现，因为总有一个球是不相等的。同样左、左、左，右、右、右的结果也不回出现，因为根据设计的称法，没有一个球是三次都在左边或右边的。剩下的24种结果就可以判断出哪种情况是哪一个球了。例如：如果结果是平、平、左或是平、平、右，就可判断出是9号球，因为第一次与第二次都没有9号球，唯独第三次有9号球，而第一次与第二次都是平的，只有第三次是失衡的，说明9号球的重量与其它的球不同。可依据此原理判断出其它的各种情况分别是哪个球。 有12个球，而坏球又可能比好球轻也可能比好球重，所以总共有12x2=24种可能，24可能结果如下表： * * * * * 可 能 * * 结 果 * * 可 能 * 结 果 * * * * 1号球，且重 左、右、右 1号球，且轻 右、左、左 2号球，且重 右、左、右 2号球，且轻 左、右、左 3号球，且重 右、右、左 3号球，且轻 左、左、右 4号球，且重 平、左、左 4号球，且轻 平、右、右 5号球，且重 左、平、左 5号球，且轻 右、平、右 6号球，且重 左、左、平 6号球，且轻 右、右、平 7号球，且重 右、平、平 7号球，且轻 左、平、平 8号球，且重 平、右、平 8号球，且轻 平、左、平 9号球，且重 平、平、右 9号球，且轻 平、平、左 10号球，且重平、左、右 10号球，且轻平、右、左 11号球，且重右、平、左 11号球，且轻左、平、右 12号球，且重左、右、平 12号球，且轻右、左、平 上面的24种结果里面没有一个重复的，也可以把上面的结果反过来当成可能，也可唯一的推出那个球为坏球，证明此方法可行。第一篇（完美的数学建模）原文：网上的最多的方法是逻辑法,还有少数画成图的所谓策略树和基于此的程序算法.这里我提出一种新的完全的数学解法:一首先提出称量的数学模型: 把一次称量看成一个一次代数式,同样问题就可以描述成简单的矩阵方程求解问题.怎么把一次称量表示成一个代数式呢? 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便构成了312的称量矩阵J；对于某一可能情况i,对应的3次称量结果组成的3维列向量b,得 J*i=b 二称球问题的数学建模 问题的等价： 设J为312的矩阵，满足每行各项之和为0。i为12维列向量,i的某一项为1或1，其他项都是0，即i是1224的分块矩阵M=(E,-E)的任一列。而327的矩阵C为由27个互不相同的3维列向量构成，它的元素只能是1,0,-1. 由问题的意义可知b=J*i必定是C的某一列向量。而对于任意的i,有由J*i=b确定的b互不相同. 即 J*M=J*(E,-E)=(B,-B)=X -（设X为324的矩阵） 因为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，(3N-3)/2个球称N次找出异球且确定轻重的通解： 第一步，先给出3个球称2次的一个称量矩阵J2 0, 1,-1; -1, 0, 1. 第二步，设Kn=(3N-3)/2个球称N次的称量矩阵为N行Kn列的矩阵Jn,把(3N/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类，有(3n-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. 第二篇（EXCEL构造大法）此法可以便捷直观地验证所构造的称量方法是否是正确的！解决了对答案进行正确性验证的难题。并且可以通过构造分块矩阵最终解决N球称M次找2异常球的更高级称球问题！贴不了EXCEL原档，只能先截个图了，此法要先温习前一篇的解法才风味更佳：步骤详解：第一步,做分块矩阵M=-E12,E12。第二步，构造称量矩阵，每一列互不相同，为了满足完备性，可以调整各列。第三步，两矩阵求积，函数MMULT(，)第四步，对结果矩阵求各列的对应3进制并算出具体K值。k值函数示例(-1)B24*SIGN(B24)第五步，做三位（-1,0,1）的3进制的全排列和对应序列码第六步，对于各序列码M，做出在N中与之相等的元素个数Tt函数示例COUNTIF($B24:$Y24,B31)第七步，求MAX(T),若为1，则保证了称量结果矩阵M的每列都是互不相同的（各列唯一性），既题得证，所构造的称量方案矩阵J是正确的次球状态：M轻：负单位矩阵-E12重：单位矩阵E121-10000000000010000000000020-10000000000010000000000300-10000000000010000000004000-10000000000010000000050000-10000000000010000000600000-10000000000010000007000000-10000000000010000080000000-10000000000010000900000000-100000000000100010000000000-100000000000100110000000000-100000000000101200000000000-1000000000001称量方案：J12345678910111213求和：称量完备性要求行和须为零第一次0000-111-11-11-10第二次01-111-1000-11-10第三次-1-10110-10110-10称量结果：X=J*M（矩阵求内积函数MMULT(B16:M18,B2:Y13)）a00001-1-11-11-110000-111-11-11-1b0-11-1-110001-1101-111-1000-11-1c110-1-1010-1-101-1-10110-10110-1三进制编码：n1-23-45-6-89-1011-1213-12-34-568-910-1112-13绝对值|n|1234568910111213k=(-1)n*n/|n|-1-1-1-1-1-1-1-1-1-1-1-1111111111111令：k=-1为球轻,k=1为球重;n=9a+3b+c元素-1,0,1组成的所有排列P:-1-1-1-1-1-1-1-1-1000000000111111111-1-1-1000111-1-1-1000111-1-1-1000111-101-101-101-101-101-101-101-101-101序列码m：-13-12-11-10-9-8-7-6-5-4-3-2-1012345678910111213求n=m的元素个数t：函数COUNTIF()111111011111101111110111111最大值！MAX(t)1MAX(t)=1保证M的每列都是互不相同的，既题得解重排：把12个球分两组(1号到6号,8号到13号)编好序号坏球n对应称量结果：球序号|n|1234568910111213第一次a0000-111-11-11-10a第二次b01-111-1000-11-10b第三次c-1-10110-10110-10cn=9a+3b+c-12-34-568-910-1112-13k=(-1)n*n/|n|111111111111注：求和目的是检查称量完备性，记k=(-1)n*n/|n|abc只能是左边12列中的一列或取反，既(a,b,c)T=(a,b,c)T或(-a,-b,-c)T对应的：|n|为坏球序号，且k=-1为球轻，k=1为球重第三篇（简洁特解，有趣的就这么两个）方案一（最漂亮的一个解的文字说明）：首先12个球编号16,813，跳过7称量方案如下，可以三次称完再整体分析，具体如下：对称量结果：右边较重记1，平衡记0，