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

12个球称3次找坏球的解答 There are 12 balls, one of which is different from the weight of the other balls (of course, light or heavy). Question: give you a balance, let you say at most three times (three times is enough, in fact, less than three times simply can not be called), find that weight is different from the other ball. And find out is heavy is light. It has been suggested that n can be from (3^n-1) said a bad ball /2 balls (people who are interested in using mathematical induction to prove it to me), that is to say the most with 13 ball 3 times the size of the title 12 is probably in order to avoid the 13 foreigners don't think too lucky number. The following is the solution of the reprint: ///////////////////// A //////////////////////////////////////////////////////////////////////////////// Number twelve balls to No. 1-12. * * the number 1-4 in the balance on the left, on the right side of No. 5 to 8. There are three kinds of results: I. balance. That question is "no.. * * the 1 on the left, on the right side of 9-11. There are three kinds of results: 1. balance. There is a problem with number 12. * put the number 1 on the left, and number 12 on the right. Left weight is 12 lighter, right heavy is No. 12 heavy. Impossible balance. 2. left heavy. That there is a ball in the light of the 9-11. * put the number 9 on the left, and number 10 on the right. Left weight is 10 light, right weight is 9 light, balance is 11 light. 3. right heavy. There is a ball that 9-11 heavy. * put the number 9 on the left, and number 10 on the right. The left weight is 9, the heavy weight is 10, and the balance is 11. Two. Left weight. That question is No. 1-8. * * 1, 5-7 on the left, on the right 811. There are three kinds of results: 1. balance. There is a ball that 2 heavy. * put the number 2 on the left, and number 3 on the right. The left weight is 2, the heavy weight is 3, and the balance is 4. 2. left heavy. It means No. 1 is heavy, or No. 8 is light. * number 1 on the left, number 2 on the right. The left weight is 1, the balance is No. 8 is light. It can't be right. 3. right heavy. That 5-7 No. there is a ball of light. * put the number 5 on the left, and number 6 on the right. Left weight is 6 light, right weight is 5 light, balance is 7 light. Three. Right weight. That question is No. 1-8. * * 1, 5-7 on the left, on the right 811. There are three kinds of results: 1. balance. That there is a ball in the light of the 2. * put the number 2 on the left, and number 3 on the right. Left weight is 3 light, right weight is 1 light, balance is 4 light. 2. right heavy. Note that No. 1 is light, or No. 8 is heavy. * number 1 on the left, number 2 on the right. The left weight is 1 lighter, and the balance is 8 heavier. It can't be right. 3. left heavy. That is a heavy ball, 5-7. * put the number 5 on the left, and number 6 on the right. The left weight is 5, the heavy weight is 6, and the balance is 7. If it's 13 balls, you can call it three times. For the first time, the eight ball balance said, "if the balance is unknown, the ball is in the eight balls, according to the above 2. continue to call it.". If it is called a balance for the first time, the abnormal ball will take three of the 5 balls in the following 2 balls, plus a balance on the normal ball. If balance is made, the third ball will be found in the remaining two balls, and can be weighed at one time. If unbalanced, the abnormal ball in the balance of the three balls, from the three balls to take one, shift one, third do not move, with normal ball to complete the number of balls on both sides, called third times. You can find the ball at one stroke. ///////////////////// B //////////////////////////////////////////////////////////////////////////////// A new and complete mathematical solution: First, the mathematical model of weighing was proposed: To treat a weighing as an algebraic expression, the same problem can be described as a simple matrix equation problem. How can one weigh it into an algebraic expression? 1), simplified description of ball weight (state) - normal ball weight is set to 0, with exception than the normal weight of 1 ball ball or light -1, abnormal ball with X on behalf of unknown severity (only 1 or -1). With the column vector J represents all the weight of the ball. 2) to simplify the weighing of the left and right (put the law) - put a ball to the left is set to 1, the right is set to -1, do not put it up to 0., with a row vector I that means weighing all of the ball's left and right state 3) describe weighing results: By 1) 2) a weighing system has been established The ball weight * Sigma method = balance weighing results.-------- (1) type If we use vector J and I to represent the weight state of the ball and the left and right set of the ball (J is the row vector, and I is the column vector), for (1), we can rewrite it as J*i=a (constant a for single weighing results) - (2) - For example 1-6, a total of 6 balls, including 4 for the heavier ball, take the No. 3 No. 5 No. 1 No. 4 on the left and right are put into weighing,: (-1) *0+0*0+1*0+ (-1) *1+1*0+0*0=-1, From the meaning of -1, you can know that it indicates the left side of the result is lighter; You can also get 0 for balance, and 1 for heavier left 4) equations are used to describe the weighing process, and additional important conditions are required: the 1 on the left and the -1 on the right equal, that is The putting of each ball, =0------------------------- (3) This solves the problem of mathematical expression of weighing For the 3 time weighing 12 balls, respectively with 12 dimensional vector J1, J2, J3, j1j2j3 constitute by weighing matrix J 3 * 12; for a possible I, corresponding to the 3 weighing results of 3 vectors consisting of B, too J*i=b Mathematical modeling of two ball problem Equivalence of problems: Let J be a matrix of 3 * 12, satisfying the sum of 0 of each row. I is the 12 vectors, I a 1 - or 1, other items are 0, namely I is a block matrix M= 12 * 24 (E, -E) of any column. The matrix C 3 * 27 by 27 different 3 vectors, only elements of which is 1,0, -1. From the point of view of the problem, b=J*i must be a column vector of C. For any I, the B determined by J*i=b is different from each other That is J*M=J* (E, -E) = (B, -B) =X = (let X be a matrix of 3 * 24) Since X is the column vector of 12 pairs of mutual pairs in 24 columns, and C is the 27 column, we can see that the 3 columns removed from C are the column vectors of (0,0,0) and 1 pairs of arbitrary mutual pairs, where 1,1,1 (and -1, -1, -1) are removed From the previous formula, J*E=B launches J=B, X= (J, -J). So the removal from the 27 vectors in 3 (0,0,0), (1,1,1), (-1, -1, -1) and then divided into two groups of mutually coupled (corresponding to invert) [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]. Now, by switching up and down 2 lines, the order of each line is 0!! You can get J., my method is from right to left, up and down, and then the 2 row and the 3 row up and down, just all the rows and 0. have to Weighing matrix 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]. The corresponding three weighing, both sides of the discharge method: Left, 5, 7, 9, 11: right, 6, 8, 10, 12; Left, 2, 9, 10, 12: right, 3, 4, 8, 11; Left, 1, 4, 11, 12: right, 3, 6, 7, 9. *********** ********** government ********** Ball No. 1, and it is flat, flat, left, 1 ball, and light, flat, flat and right Ball No. 2, and the weight - flat, left and flat 2 ball, and light - flat, right, flat Ball No. 3, heavy, flat, right and right, No. 3 ball, and light, flat, left and left Ball No. 4, and the weight - flat, right and left, No. 4 ball, and light - flat, left, right Ball No. 5, and weight - left, flat, flat, 5 ball, and light - right, flat, flat Ball No. 6, and weight - right, flat, right, No. 6 ball, and light left, flat, left Ball No. 7, and weight - left, flat, right, No. 7 ball, and light - right, flat, left Ball No. 8, and weight - right, right, flat, ball No. 8, and light left, left, flat Ball No. 9, and weight - left, left and right, No. 9 ball, and light - right, right, left Ball No. 10, and weight - right, left, flat, ball No. 10, and light left, right, flat Ball No. 11, and weight - left, right and left, No. 11 ball, and light - right, left, flat Ball No. 12, and weight - right, left and left, ball No. 12, and light left, right and right Three. Problem extension 1, 13 balls called 3 times: The 3 vectors removed from the above solution are (0,0,0) (1,1,1) (-1, -1, -1). To be able to determine the thirteenth ball, 1 pairs of dual vectors must be added. If the (1,1,1) (-1, -1, -1) is added, then the [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]; [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列的矩阵约，把(3 ^ N / 3-3)/ 2个球称N-1次的称量矩阵J < N-1 >简写为J.再设N维列向量Xn，Yn，锌分别为(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的长为奇数时，用分块矩阵表示矩阵约,(J，J，J，Xn，Yn，Zn);当J的列数即T的长为偶数时，用分块矩阵表示矩阵约,(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,0 1, 1 ]; 【0,0，0, 1，1，1，1，-1,0,1，1，0,0，0, 1，1，1, 1，1，1, 0, 1，0，0, 0，1, 1, 1，1, 1, 1，0，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 ]; [ 0，1，1, 0，1,1，0，- 1,1,0，- 1、- 0，1，1, 0, 1，1, 0，1, 1, 0，1，0，1, 1, 0，1，1, 0, 1，1, 0，1,1，0，1 ]。