12个球称3次找坏球的解答

12个球称3次找坏球的解答 有12个球，其中有一个球与其他球的重量不一样(当然，是轻还是重就不知道 了)。问:给你一个天平，让你最多称三次(三次就够少的了，其实低于三次根本 就称不出来)，就找出那个重量与其他球不一样的球。并求出是重是轻。 有人提出:n次最多可以从(3^n-1)/2个球中称出一个劣质球(有兴趣的人用数学 归纳法证明一下发给我)，也就是说3次最多可处理13个球的规模，题目取12大 概是为了回避13这个老外认为不太吉利的数字吧。 下面是转载的解法: ///////////////////// A //////////////////////////////////////////////////////////////////////////////// 将十二个球编号为1,12号。 ,,将1,4号放在天平左边，5,8号放在右边。 有三种结果: 一.平衡。说明有问题的是9,12号。 ,,把1,3放在左边，9,11放在右边。 有三种结果: 1.平衡。说明12号有问题。 ,,把1号放在左边，12号放右边。 左重则12号轻了，右重则12号重了。不可能平衡。 2.左重。说明9,11中有一个球轻了。 ,,把9号放在左边，10号放在右边。 左重则10号轻了，右重则9号轻了，平衡则11号轻了。 3.右重。说明9,11中有一个球重了。 ,,把9号放在左边，10号放在右边。 左重则9号重了，右重则10号重了，平衡则11号重了。 二。左重。说明有问题的是1,8号。 ,,把1，5,7放在左边，8,11放在右边。 有三种结果: 1.平衡。说明2,4中有一个球重了。 ,,把2号放在左边，3号放在右边。 左重则2号重了，右重则3号重了，平衡则4号重了。 2.左重。说明1号重了，或者8号轻了。 ,,1号放在左边，2号放在右边。 左重则1号重了，平衡则8号轻了。不可能右重。 3.右重。说明5,7号有一个球轻了。 ,,把5号放在左边，6号放在右边。 左重则6号轻了，右重则5号轻了，平衡则7号轻了。 三。右重。说明有问题的是1,8号。 ,,把1，5,7放在左边，8,11放在右边。 有三种结果: 1.平衡。说明2,4中有一个球轻了。 ,,把2号放在左边，3号放在右边。 左重则3号轻了，右重则1号轻了，平衡则4号轻了。 2.右重。说明1号轻了，或者8号重了。 ,,1号放在左边，2号放在右边。 左重则1号轻了，平衡则8号重了。不可能右重。 3.左重。说明5,7号有一球重了。 ,,把5号放在左边，6号放在右边。 左重则5号重了，右重则6号重了，平衡则7号重了。 如果是13个球呢?也可以三次称出来。 第一次取八个球上天平称，若不平衡，则未知球就在这八个球中，按上述的2.继续称就是。 若第一次称为平衡，异常球在下面的5个球中，取其中三个球加一个正常球上天平称，若平衡，第三次就在剩下的2个球中找，一次就可称出。若不平衡，异常球在天平上的三个球中，从这三个球中取下一个，移位一个，第三个不动，用正常球补齐两边球数，称第三次。就可一举找到异常球。 ///////////////////// B //////////////////////////////////////////////////////////////////////////////// 一种新的完全的数学解法: ?首先提出称量的数学模型: 一 把一次称量看成一个一次代数式,同样问题就可以描述成简单的矩阵方程求解问题.怎么把一次称量表示成一个代数式呢? 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, 0, 0, 1, 1,-1,-1,-1，1]; [ 0, 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 次找出2个相同的异球，9个球时的几个简单情况有了初步的了解，如5个球称3 称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].