About finding different questions in 13 balls
Problem: There are 13 sizes, the same shape, one of which is different from the other 12, please use the balance, use up to three times, find that the weight of the ball is different.
Foreword: This is an unusual problem. Half a month ago, I was fascinated by this problem. I thought about it all day. After I watched countless answers, I still didn't think about it. The correct result, I gave up (I started to doubt the correctness of the topic), until yesterday, September 16, 2001, I came up with an answer. (If this is really Huawei's interview question, I am definitely eliminated)
Solution Idea: 12 standard balls, 1 non-standard ball. When finding non-standard ball, every ball is likely, calling it is suspect. Here I am going to discuss several situations that can be found with one weigh:
1. There are two suspects, and when you have a number of standard battles, you can find it once. The specific approach is to take a suspect that the same standard ball is compared. If the weight is different, you can determine that the suspect on the balance is non-standard ball, otherwise, the remaining is non-standard ball.
2. There are three suspects, and there is a comparison result in these three suspects, and in this comparison, three suspects are not on the same side. The comparative method is to take one of the suspects on both sides. If the same two standard balls are compared, if the same, it can be sure, the suspect without participating is non-standard ball, if the two suspects are heavy, then the last time In the comparison result, the suspect on the heavy side is a non-standard ball, otherwise the suspect on the light side is a non-standard ball.
3. There is only one suspect.
Solution method:
First, 13 ball numbers and groups:
1, 2, 3, 4 A1 group
5, 6, 7, 8 b1 group
9, 10, 11, 12 c1 group
13
Weigh a and b, record results R1 (here more than 0) is used to represent A> B, other types of push)
Then secondary group
13, 2, 7, 8 A2 group
1, 6, 11, 12 B2 group
5, 10, 3, 4 C2 group
9
Weighing A2 and B2, record results R2
Start analysis results:
If r1 = r2 = 0, it proves that non-standard balls have not been above the balance, so that suspects have 2: 9th, 10th. Compliance with the solutions proposed in front. You can solve this problem. The results will be produced in 9, 10.
If r1 = 0, R2> 0 (or R2 <0), when the second measurement is demonstrated, it is non-standard ball on the balance, so that the suspects have three: 13, 11, 12. This is in line with the second case mentioned earlier or resolved. The results will be generated in 13, 11, 12.
If R1> 0, R2 = 0 is very simple, this proves that non-standard balls leave the balance when the non-standard ball is measured, and the suspect is three: 5, 3, 4. We can use the first comparison results to find non-standard balls with the second solution. The results will be produced in 5, 3, 4.
If R1> 0, R2> 0, the second measurement is proved that the non-standard ball has been flattened, but the suspect seems to have four: 1, 2, 6, 7, 8, is not the case, From the test results, non-standard balls have not left their own position. In this case, only 2 and 6 are suspects. The results will be produced in 2, 6. R1> 0, R2 <0, the same reason, non-standard balls move their position, so that the suspect should be: 1, 7, 8. Obviously this is in line with the second condition. The results will be produced in 1, 7, 8.
Obviously there is no need to discuss R1 <0, which is actually the same as R1> 0.
Although the answer is completed, I always want to say something, I am just an undergraduate, I have not exposed to a high-profile logic, but this topic is really reflecting a mathematical phenomenon, I understand, but I can't say it. I hope that one day I can truly master this science.
Beyond_ml (Malei@bisp.com)
