12个球称3次找坏球的完美解答(矩阵法)

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].