Note This article tries to give a general and strict solution for the issue of the problem. Because it is necessary to do general and strict, it is necessary to consider many of the special circumstances that are not encountered, so the narrative is more cumbersome. If the reader is not interested in strict proven, you can only read the first, second quarter of the report, and the second quarter of the report, and the 27 balls at the end of the third quarter, and the fifth section of 13 balls and 40 ball solutions . In fact, all skills have been manifested in these examples. I. The classic form of the problem is like this: "There is twelve of the same ball, which has a bad ball, its weight and other eleven have slight (but can measure). Now There is a very sensitive balance without weight, asking how to say three times, guarantee that the bad ball is to find out, and know it is better than the standard ball, "this may be the most intelligence question of the number of times online. It is as follows: Twelve ball numbers are 1-12. For the first time, put the 1-4 号 on the left and put on the right. 1. If the right is heavy, the bad ball is from 1-8. The second time I took 2-4, moved from the right from the right to the left and put the 9-11 to the right. That is, put 1, 6, 7, 8 on the left, 5, 9, 10, 11 to the right. 1. If the right is heavy, the bad ball is not touched 1, 5. If it is No. 1, it is light than the standard sphere; if it is 5, it is more than the standard ball. The third time I put the No. 1 on the left and put on the right. 1. If the right weight is a bad ball and is light than the standard sphere; 2. If the balance is 5 is a bad ball and is more than the standard ball; 3. This time it is impossible to turn left. 2. If balance, the bad ball is 2-4, and is light than the standard sphere. The third time I put the No. 2 on the left and put it on the right. 1. If the right weight is 2, it is a bad ball and is light than the standard sphere; 2. If the balance is 4th is a bad ball and is more light than the standard sphere; 3. If the left, the No. 3 is a bad ball and is light than the standard. 3. If the left, the bad ball is got to the left 6-8, and it is more than the standard ball. The third time I put the No. 6 on the left and put it on the right. 1. If the right weight is the number 7 is a bad ball and is more than the standard ball; 2. If the balance is 8, it is a bad ball and the standard ball weight; 3. If the left, the 6th is a bad ball and is more than the standard ball. 2. If the balance is balanced, the bad ball is from 9-12. The second time will be placed on the left side, and the 9-11 is placed on the right. 1. If the right is heavy, the bad ball is 9-11 and the bad ball is heavier. The third time I put the 9th on the left and put on the right. 1. If the right weight is 10, it is a bad ball and is more than the standard ball; 2. If the balance is 11th is a bad ball and is more than the standard ball; 3. If the left, the left is 9 is a bad ball and is more than the standard ball. 2. If balance, the bad ball is 12. The third place was placed on the left and on the right side. 1. If the right weight is 12th is a bad ball and is more than the standard ball; 2. This is impossible to balance; 3. If the left is 12, the 12th is a bad ball and is light than the standard sphere. 3. If the left is heavy, the bad ball is 9-11 and the bad ball is lighter. The third time I put the 9th on the left and put on the right. 1. If the right weight is 9th is a bad ball and is better than the standard sphere; 2. If the balance is 11th is a bad ball and is better than the standard sphere; 3. If the left, the 10th is a bad ball and is light than the standard sphere. 3. If the left is heavy, the bad ball is from 1-8. The second time I took 2-4, moved from the right from the right to the left, put the 9-11 number on the right.
That is, put 1, 6, 7, 8 on the left, 5, 9, 10, 11 to the right. 1. If the right is heavy, the bad ball is got to the left of the 6-8, and is more light than the standard sphere. The third time I put the No. 6 on the left and put it on the right. 1. If the right weight is 6th is a bad ball and is better than the standard sphere; 2. If the balance is 8th is a bad ball and is better than the standard sphere; 2. If balance, the bad ball is from the 2-4 mark that is taken, and is more than the standard ball. The third time I put the No. 2 on the left and put it on the right. 1. If the right weight is 3, it is a bad ball and is more than the standard ball; 2. If the balance is 4, it is a bad ball and is more than the standard ball; 3. If the left, the left is the bad ball and the standard ball is heavy. 3. If the left is heavy, the bad ball is not touched 1, 5. If it is No. 1, it is more than the standard ball; if it is 5, it is light than the standard ball. The third time I put the No. 1 on the left and put on the right. 1. This time it is impossible to right. 2. If the balance is 5, it is a bad ball and is light than the standard sphere; 3. If the left is left, No. 1 is a bad ball and is more than the standard ball; it is troublesome. In fact, there are many situations that are symmetrical. For example, the right weight and right light at the first time, only one can be considered, and the other can be implemented. I wrote the whole process and just want to scare everyone. Try a little, you can know that only two times is impossible to ensure that the bad ball is found. If the thirteen balls are given, the above solution is basically effective, but there is a small change, just in this case, when the first second is balanced, it is possible to balance the third time. (It is the top 2.2.2 above), then we can definitely bad balls are 13th, but we can't know that it is better than the standard ball, or is more than standard. If it is 14 balls, we will find that it is impossible to just call three times, to ensure that the bad ball is found. A natural problem is: For a given natural number n, how can we solve N-ball name? In the following discussion, give a natural number N, we must solve the following questions: (1) identify the minimum number of N-ball weighing problems, and prove that the minimum number given above; (2) gives the smallest The specific method of the number; (3) If only the bad ball is required to find bad balls without requiring the light weight of the bad ball, the above two problems have been solved by the N-ball title; there is another is not so interested, but The problem is: ⑷ If the N ball given, the other will be given to a standard ball, solve the above three problems. Second, marks should be busy with the above problems first. First give a few definitions, especially, to give relatively simple symbols and notes. Everyone sees that the solution given above is troubles - imagine if we want to use this method to describe the problem of 40 or 1000 balls! Still considering the case of twelve balls and the solution above. I haven't begun the first time, and the information known to this twelve balls is one or more of the ball, so the following 24 cases are possible: 1. No. 1 is Ball, and heavier; 2. No. 2 is a bad ball, and heavier; ... 12. No. 12 is a bad ball, heavier; 13. No. 1 is a bad ball, and lighter; 14. No. 2 is Bad ball, and lighter; ... 24. No. 12 is a bad ball, and lighter.
Without other possibilities, such as "1, 2 is a bad ball, and it is heavy". When we solve the top 1-4 in the left, No. 5-8 is placed on the left, 5-8, "We have called the first time, the result is right weight, slightly analyzed, you will know the above 24 cases Now there is only 8 kinds of possible, that is, the No. 1 is a bad ball, and it is lighter; 2. No. 2 is a bad ball, and lighter; 3. No. 3 is a bad ball, and lighter; 4. 4 It is a bad ball, and it is lighter; 5. No. 5 is a bad ball, heavier; 6. No. 6 is a bad ball, and heavier; 7. No. 7 is a bad ball, heavier; 8. No. 8 is bad Ball, and heavier. We put, such as "No. 1 is a bad ball, and heavier, the other balls are normal" and "No. 2 is a bad ball, and it is light, and the other ball is normal." Is called a "layout", In order to: (1 heavy) and (2 light) We put "putting 1-4 to the left, 5-8 on the right", called a "weigh". We have called (1, 2, 3, 4; 5, 6, 7, 8) or (1-4; 5-8), which is the number of participating weighing balls in parentheses. And put on the left and placed on the right side with a semicolon. At the moment, we have 24 possible layouts, while after one weighing (1-4; 5-8), if the result is right, we have the above eight possible layouts. Our purpose is to use as little weighing, and get the only possible layout - so that we know which ball is a bad ball, it is relatively light. Here we notice that there is no need to consider the weighing weighing. Because the difference between the bad ball and the standard ball weight is small, less than the standard ball weight, so the number of balls in the day is different, and the balance is more than the ball. So before making such a weigh, its results can be expected, it can't bring us any new information. In fact, it is easy to understand after reading this article, even if the difference between the bad ball and the standard ball weight is large, it will not affect this paper. Because this situation will make problems, we can't bring interesting results, we will omit this consideration. Now we see that the solution about the twelve ball issues is actually a series of weighing - can not be combined with cascading, but in such a form: weigh 1 if right, Then weigh 3 ... If balanced, weigh 2 ... If left, weigh 4 ... The number of omitted numbers is almost a matter of "if the right weight, then ..." and so on. So this prompts us to use the tree form to indicate the above solution: the root of the tree is the first weigh, it has three branches (ie three sub-trees, there are three sub-nodes), respectively correspond to this weighing The right weight, balance, and left three cases.
On the three child nodes of the root, there is a corresponding weighing, and three branches of them ... if specifically written, it is | - Right-(1 light) | - Right - (1; 2) | - Flat - (5) | | - Left - () | | | - Right - (2 Light) | - Right - (1,6-8; | - (2; 3) | - 平 - (4 light) | 5, 9-11) | | - left - (3 light) | | | | | - Right - (7 heavy) | | - Left - (6; 7) | - Flat - (8) | | - Left - (6) | | | - Right - (10) | | - Right - - (9; 10) | - Flat - (11) | | | - Left - (9) | | | | | - Right - (12) (1-4; 5-8 ) | - 平 - (1-3; | - 平 - (1; 12) | - 平 - (13 light, 13 heavy) * | 9-11) | | - left - ( 12 light) | | | | | - Right-(9 light) | | - Left - (9; 10) | - Flat - (11 light) | | - Left - (10 Light) | | | - Right - (6 Light) | | - Right - (6; 7) | - Flat - (8 Light) | | | - (7 light) | | | | | - right - (3 weight) | - Left - (1,6-8; | - 平 - (2; 3) | (4 heavy) 5,9-11) | | - left - (2 heavy) | | | - right - () | - left - (1; 2) | - 平 - (5 Light) | - Left - (1 Weight) (*: There should be a thirteenth ball. Here, "Right", "flat" and "left" respectively indicate the result of "right weight", "balance", and "left".
The leaves of the tree (that is, the result of "can reach" these nodes, which is the result of "being able to reach" these nodes, that is to say, the result given by this layout And "right", "flat" and "left" as marked on the road to the corresponding leaves are in line with. From this figure, we can also see that the left branch and right branch under the roots are symmetrical: only need to change all "right" to "left", "left" to "right", "light" change "Heavy", "heavy" is changed to "light"; the left branch and right branch under the node (1-3; 9-11) also have this feature. (If you have friends interested in tree theory, you can refer to where you are discrete or discrete mathematics book. Here we use the most basic knowledge in the tree theory, the nouns and conclusions used are quite intuitive. So If you don't know the theory of tree, you can also understand the argument here.) So give a three-point tree (that is, there are three child nodes outside the leaves), in each of each A weighing is given on the node of the leaves, and the three branches (subtroes) under this node corresponding to the right weight, balance, and left, and we have got a way that is called the ball. We call such a three-point tree as a "strategy" or a "strategy tree". You can give an ordinary strategy. For example, no matter what happens, the number 1 and 2 will always be called (there we have not written on the leaves, replacing it with @ @ 来): | - Right - @ A | - Right - (1; 2) | - Flat - @ | | - Left - @ | | | - Right - @ (1; 2) | - 平 - (1; 2) | - 平 - @ | | - left - @ | | | - Right - @ b | | - Right - (1; 2) | - @ | | | - - @ | | | | - - @ | - Left - (1; 2) | - Flat - (1; 2) | - @ | | - Left - @ | | | - - @ | - left - (1; 2) | - 平 - @ | - left - @ of course this strategy is not used It can only let us know the lighter relationship between the 1st ball and 2. In addition, we see that each branch is not necessarily as long as the strategy tree roots is relatively long. The height of a tree is the maximum value of the node number between the leaves to the roots. For example, in this figure, the leaves A and the roots have 1 node, while the leaves B and the roots have two nodes, no leaves with the number of nodes between the roots. So it's height is 2 1 = 3. The height of the twelfth ball solution strategy tree is also 3. A tree without any branch, only root node, we define its height of 0. Obviously, the height of the strategic tree is the number of weighs required to implement this strategy.
Our purpose is to find a "good" strategy tree so that it is the low height. What is "good" strategy? Let's go back to see the twelve ball solution strategy tree. We have said that the layouts on the leaves are beginning to leave from the root. For example, the layout (7 heavy) is the reason why the leaves are "right" results in that the leaf, the result of the three weighing is "right"; for example, the layout (11 heavy), it is on the leaf Because the result of the three weighing is "Ping right" as the result of this strategy. If the two layouts lead to the same leaf, then, according to this strategy, the result of the three weigh is exactly the same, so we can't pass this strategy to distinguish these two layouts. For example, in the case of thirteen balls, (13 light) and (13 heavy) are all about the leaves corresponding to "Pingping", these two layouts 13, the ball or light or heavy, so we know 13 The ball must be a bad ball, but we can't know if it is light or heavy. Therefore, for the "good" strategy for standard title (find bad balls and knowing its compared to standard ball weight or light), it is the strategy that can make different layouts to different leaves. Third, each ball is known to introduce a mark first in the case: for any real number a, we use {A} to indicate the minimum integer equal to A, such as {2.5} = 3, {4 } = 4; We use [A] to indicate the maximum integer equal to A, for example [2.5] = 2, [4] = 4. We first consider such a collection of layouts. Assume that M, N is two non-negative solids, and it is 0. In the number from 1 to M N, we know that the 1 to M number is either a standard ball or a standard ball, while M 1 to M N is either standard ball, or Light than standard scorpion; we also know one of them is a bad ball (but I don't know much). In other words, we know that the true situation is one of the following m n layouts: 1. No. 1 is a bad ball, and heavier; 2. No. 2 is a bad ball, and heavier; ... m. M is Bad ball, heavy; M 1. M 1 is a bad ball, and lighter; m 2. M 2 is a bad ball, and lighter; ... m n. M N is Bad ball, and lighter. There is a special case that M = 0 or n = 0, that is, the bad ball is light or heavy, often used to be used as a intellectual question. Conclusion 1: 1) In the case of establishing the above conditions, it is necessary to ensure that the bad ball is found in M N ball and knows that it is precise, at least {LOG3 (M N)} times. 2) If M and N are different, then {LOG3 (M N)} is sufficient. If m = n = 1, and another standard ball is called {log3 (m n)} = {log3 (1 1)} = 1 time is also enough. Here, log3 represents the logarithm of 3 as the bottom. Need to describe 2). If m = n = 1, there is no standard ball, then it will never be a bad ball. Putting two balls on the balance, inevitably the 1st weight 2 light. But because there is no standard ball, we can't know that the bad ball is more serious, so the No. 1 is bad, or the bad ball is relatively light, so the 2 is bad. If there is a standard ball, just compare the 1st ball and the standard ball.
If the balance is unbalanced, then the ball is a bad ball, and it is more important; if the balance is balanced, then the 2nd ball is a bad ball, and it is relatively light. The strategy tree is as follows: (use s Representab to the standard ball) | - Right-() | | (1; s) | - 平 - (2 light) | | | - left - (1 heavy) Certification 1). As we see above, possible layout is M N type (1 weight, 2 heavy, ..., M heavy, M 1 light, m 2 light, ..., M N light). Suppose we have a strategy to ensure that the bad balls are found in this M N ball and know that it is precise, then each layout must lead to different leaves on the strategy tree, this strategy tree requires at least M N Film leaves. However, a height of h-shaped trees can only have 3 ^ h square sheet leaves. So this strategic tree must meet the conditions 3 ≥ m N is H ≥ log3 (m n) considering that h is an integer, we prove that H ≥ {log3 (m n)} Now we have to find it specifically A strategy tree with {log3 (m n)} such that the M N layout leads to its different leaves. We use mathematical induction methods for k = m n. First k = 1. So, don't call it, because there must be a bad ball, then the bad ball is the only 1st. If it is m = 1, n = 0, then the ball is heavy; if it is m = 0, n = 1, then the 1st is relatively light. The number of weighing is {log3 (1)} = 0. For K = 2. M = 1, n = 1 has been discussed. Consider m = 2, n = 0. At this time, we know that the bad ball is relatively heavy. As long as the 1st ball and the 2nd ball are placed on both sides of the balance, which is a bad ball. The strategy tree is as follows: | - Right - (2) | | (1; 2) | - Flat - () | | | - Left - (1 Weight) M = 0, n = 2 It is totally similar. It is assumed that we can use {log3 (k)} to say bad balls for M N For example, assuming that M is even, there are two possibilities. If m / 2 ≥ {k / 3}, then {K / 3} balls from the first group of balls as the first and second piles (only the first group in the first second pile) Ball); if m / 2 <{k / 3}, then divide the first set of balls into two piles of the same m / 2 balls, then use {k / 3} -m / 2 second group, respectively. The ball is replenished into two piles of {k / 3} balls (at this time there is only the second group of balls). It is clear that such deposits meet the above requirements. If m and n are odd, things are a bit complicated. First, if (m-1) / 2 ≥ {k / 3}, then it is easy to divide the ball into three piles as required by the above method. But if we (m-1) / 2 <{k / 3}, we must first take out (M-1) / 2 balls from the first group, put them in the first and second piles, then from the second Each of the groups {k / 3} - (m-1) / 2 balls added them to each of the {k / 3} balls. This requires a total of 2 ({k / 3} - (m-1) / 2) ball from the second group. So there must be 2 ({k / 3} - (m-1) / 2) ≤ n ie 2 {k / 3} ≤ (m-1) N 2 {K / 3} ≤ K-1 This inequality in K = 3 or K> 4 is always established, but it is not established for K = 4. So we have to have a special treatment for K = 4 and M, N is odd. We only need to consider M = 3, n = 1. Put the 1st ball and 2nd ball in both ends of the balance, if it is unbalanced, then the heavier is the bad ball; if balanced, put the 1st ball and 3 ball on both ends of the balance, Balance 4 For the bad ball and lighter, the imbalance is the ball is a bad ball and heavier. The strategy tree is as follows: | - Right - (2) | | | - Right - (3) (1; 2) | - Flat - (1; 3) | - Flat - (4 Light) | | - Left - () | | - Left - (1 Weighing) M = 1, the case of n = 3 is completely similar. So now we can assume that there is no obstacle to M N = K, and the first pile and the second pile have {k / 3} balls, and these two biles The number of balls belonging to the first group (which is also the same as the number of balls belonging to the second group), and there is K-2 {k / 3} ball in the third heap (which is the remaining ball). We put the first bullets and the second pile in the left and right ends of the balance. If balanced, then the bad ball is in the third pile, so we will break the problem into a k-2 {k / 3} problem; if the right side is more important, then we get the conclusion: either bad ball comparison Light, and it is the second group of balls in the first pile, that is, the balls that may be lighter, or the bad ball is relatively heavy, and it is in the first set of balls in the second pile, which may be heavier In those of the balls, below it is attributed to a {k / 3} ball problem; if it is more heavy, then we have completely similarly to a problem with the problem into a {k / 3}. The strategic tree begins is as follows: (the number of the ball is appropriately changed: assuming 1, 2, ..., s is the first group of balls in the first pile, 1 ', 2' ..., s' is the second pile The first group of balls, (S 1), ...... For the second set of balls in the first pile, (S 1) 'is attributed to a pool in the second pile | - Right-(1 ', 2', ..., S ', S 1, ...) | ({k / 3} ball) | | (1, 2, ..., s, S 1, ...; | 1 ', 2', ..., s ', (s 1)', ...) | - Flat - Clears up the problem of bad ball in the third pile | (K -2 {k / 3} Balls) | | Cashed with bad balls in | - Left - (1, 2, ..., s, (s 1) ', ...) ({K / 3} Balls) Take into account K-2 {k / 3} ≤ {k / 3}, and we can at least get a standard ball after weighing (if unbalanced, the ball in the third pile is a standard ball) Otherwise, the ball in the first second pile is a standard ball). According to the summary assumption, the problem after "left", "flat", "right", can be solved with {log3 {k / 3}} = h-1 times. So, add this first weigh, K ball only needs to find a bad ball with {log3 (k)}. At the end of this section, we give a specific example: if there is 27 balls, there is a bad ball, and it is known that the first pile of 1-14 is if one is a bad ball, then it is more than the standard ball, The second pile of 15-27, if one is a bad ball, then it is better than the standard sphere. According to the result 1, we know that as long as [log3 (27)] = 3 times can find a bad ball. According to the above, 27 balls are divided into three piles, the number of first second piles is {27/3} = 9 balls, and the number of balls belonging to the first and second groups the same. So we can take: first pile: 1-7, 15-16 Second Heap: 8-14, 17-18 Third Heap: 19-27 Now put the first and second piles on both ends of Balance, if balance We have come to the problem of there is a lighter-bad ball in 9 balls from 19-27; if we turn on the right, we will return to the problem of bad balls in 8-14, 15-16; if the left is heavy, We will return to the problem of bad balls in 1-7, 17-18. These three situations are 9 ball problems. | - Right - the problem of bad ball in 8-14, 15-16 | | (1-7, 15-16; | 8-14, 17-18 | - flat - The problems in 19-27 | | | | - Left - to the problem of bad balls in the three cases of the problem in 1-7, 17-18, we only do one: Bad ball at 1-7, 17 The problem in -18. Similarly, we divide them into three piles of the first pile: 1-3 Second Heap: 4-6 Third Heap: 7, 17-18 Photo Similarly We have strategic trees | Problems in 4-6 | | (1-3; 4-6) | - Flat-Clan to the problem of bad balls in 7, 17-18 | | | | The problem in 1-3 then turned into three ball problems, and the solution was obvious. We wrote the above strategy tree: | - Right - (5) | - Right - (4) ; 5) | - Flat - (6) | | - Left - (4) | | | - Right - (17 Light) (1-3; 4-6) | - (17; 18) | - 平 - (7 heavy) | | - left - (18 light) | | | - right - (2 heavy) | - left - (1; 2) | - Flat - (3) | - Left - (1 Weight) Similarly We wrote the strategic trees of the problem of bad balls in 8-14, 15-16: | - Right - (12 " Heavy) | - Right - (11; 12) | - Flat - (13) | | - Left - (11) | | | - Right - (15 Light) (8-10 11-13) | - Flat - (15; 16) | - Flat - (14) | | - Left - (16 Light) | | | - Right - (9) | - Left - (8; 9) | - Flat - (10) | - Left - (8) and Bad Balls in 19-27 Problem Tree: | - Right - (19 light) | - Right - (19; 20) | Flat - (21 Light) | | - Left - (20 Light) | | | - Right - (25 Light) (19-21; 22-24) | - Flat - (25; 26) | - Flat - (27 Light) | | - Left - (26 Light) | | | - Right - (22 Light) | - Left - (22; 23) | (24 Light) | - Left - (23 Light) The three strategic trees will finally take the final solution: | - Right - (12) | - Right - (11; 12) | - 平 - (13 heavy) | | - left - (11 heavy) | | | - Right - (15 light) | - Right - (8-10; | (15; 16) | - Flat - (14th) | 11-13) | | - Left - (16 Light) | | | | | - Right - (9 Weight) | | - Left - ( 8; 9) | - Flat - (10) | | - Left - (8) | | | - Right - (19 Light) | | - Right - (19; 20) | - Flat - (21 Light) | | | - Left - (20 Light) | | | | | - Right - (25 Light) (1-7, 15-16; | (19-21; | - 平 - (25; 26) | - 平 - (27 light) 8-14, 17-18) | 22-24) | | - Left - (26 light) | | | | | - Right - (22 Light) | | - Left - (22; 23) | - Flat - (24 Light) | | - Left - (23 Light) | | | - Right-(5) | | - Right - (4; 5) | - Flat - (6) | | | - Left - (4) | | | | | - Right - (17 Light) | - Left - (1-3; | - Flat - (17; 18) | - Flat - (7 Heavy) 4-6) | | - Left - (18 light) | | | - Right - (2) | - Left - (1; 2) | - Flat - (3) | - Left - (1) The correctness of a strategic tree is relatively easy (although it is more annoying). First check if all layouts are on a piece of leaves; secondly, it is to test whether each layout is correct. Realistic. Fourth, the question's answer is now we can answer the question in the first section. Conclusion 2: The existing N small balls, which have a bad ball that is not known than the standard ball. We make h = {log3 (2n)}. 1) To ensure that the bad ball is found in N, it is necessary to say hiencies. Suppose n 2, we have 2) if n <(3 ^ h-1) / 2, then hierarily is sufficient; 3) If n = (3 ^ h-1) / 2, then H times enough Guaranteed to find a bad ball, but not enough to ensure that the bad ball is not heavy than the standard ball; 4) If n = (3 ^ h-1) / 2, and there is another standard ball, then H times is enough to ensure that it is bad Ball and know, knowing bad balls are light than the standard sphere. Suppose n = 2, we have 5) If there is another standard ball, it is called H = {log3 (2 * 2)} = 2 times enough to ensure that the bad ball and know that the bad ball is light than the standard sphere. 5) It is a bit strange, but this is actually apparent. If there are more than two balls, we know that the bad ball is one of the "unique", always find it; but if there is only two balls, a good ball is a bad ball, it is "unique", if there is no standard ball If we can't know which one is good. First, assume that the conclusion is established, let's take a look at several specific examples. If it is 12 balls, then h = {log3 (2 * 12)} = 3, and 12 <(27-1) / 2 = 13. So according to 2) We know that you can find a bad ball for 3 times and know it. If it is 13 balls, then h = {log3 (2 * 13)} = 3, and (27-1) / 2 = 13. According to 3) We know that you can find bad balls 3 times but don't necessarily know the weight. But if there is another standard ball, you can find a bad ball and know the light weight. Generally, the bad ball can be found by H times and know that the maximum number of small balls is (3 ^ H-1) / 2-1 = (3 ^ h-3) / 2; can be called by H Ignore the bad ball but don't need to know the maximum number of small balls (3 ^ H-1) / 2; there is a standard ball, can find bad balls from H times, and know the largest pneaky ball Also (3 ^ H-1) / 2. For example, in order to find a bad ball and know that it is light weight, 3 times can be called 12, 4 times is 39, 5 times to 120, 6 times to 363, etc.; in order to find bad balls I know that it is a lightweight, then 3 times can be called 13, 4 times is 40, 5 times, 664, etc. - but if there is another standard ball, then you can use the same number to know bad The ball is light. First we prove at least {log3 (2n)} times. This is almost the same as the proof of similar problems with the previous section. We see that N small balls may have 2N types (1 weight, 2 heavy, ..., N, 1 light, 2 light, ..., N light). Therefore, the corresponding strategic tree requires at least 2 N leaf. However, a height of H is a three-point tree that can only have a 3H leaf. Then this strategic tree must meet the conditions H ≥ {LOG3 (2N)}. Now let's prove 3), the second half: if n = (3H-1) / 2, then h then hide is still insufficient to ensure that the bad ball is light than the standard sphere. We know that the first step must be that each of the steps of each of the two ends of the balance, and then look at the balance. There are three cases at this time.) If the balance is balanced, the bad ball is in the remaining N-2N ball. At this time, according to 1), we also need {log3 (2 (n-2n))} to find bad balls and know that it is light; 2) If it is the left side, or the bad ball is relatively light, and the bad ball is on the right N balls, either bad balls, and bad balls in N balls on the left. According to conclusions 1, we also want to find bad balls and know that it is lightweight; 3) If it is right, then the above conclusion, we have {log3 (2n)) } Time to find a bad ball and know the weight. If we can refer to H times, we can refer to a bad ball and know it, then we must have {log3 (2 (N-2N))} ≤ H-1 and {log3 (2N))} ≤ h-1 but before One formula indicates that 2 (N-2N) ≤ 3 ^ H-1 is 2 ((3H-1) / 2-2n) ≤ 3 ^ H-1, 3 ^ H-1 ≤ 2n 1/2 Too considered 3H-1 is an integer, therefore 3 ^ H-1 ≤ 2n but 3H-1 is odd, and 2N is an even number, so 3 ^ h-1 <2n. (*) And the subsequent bonus show that 2N ≤ 3 ^ H-1 also take into account the parity 2N <3 ^ H-1. (**) We see (*) and (**) formulas are contradictory. So the case of n = (3 ^ h-1) / 2, only H step is not able to refer to bad balls and know that it is precise. It is because, although theoretically n = (3 ^ h-1) / 2, then possible layout is (3 ^ h-1), and a H layer strategy tree has 3 ^ H leaf, see It is enough to get up. However, since the first step is impossible to allocate this 3 ^ H-1 layout, there is always a branch that has more than 3 ^ (h- 1), so the bad ball is not known in this branch, and it is known that the bad ball is known to know it. Next, we also prove 2), 4) and 5 in the conclusions 2). In other words, we have to specifically find a strategy, if n <(3h-1) / 2, then do not use the standard ball to find bad balls in h, know that it is precise; if n = (3H-1) / 2 or n = 2, allowing a standard ball to achieve the same purpose. Learning mathematics induction method is still used. First, N = 1, {log3 (2n)} = 1 and n = (31-1) / 2, allowing the use of standard balls. Because there is only one ball, the topic is there a bad ball, so this is the only one is a bad ball. Now I just need to know that it is still light than the standard ball. This is ok, which can be compared to the standard ball and this ball in the balance, the strategy tree is as follows (we use S to represent the standard ball): | - Right - (1 light) (1; s) | - () | - Left - (1 weight) to n = 2 and n = 3, {log3 (2n)} = 2. We give the following strategy tree, which is easy to verify its correctness. N = 2, allowing the standard ball to be used: | - Right - (1 Light) | | - Right - (2 Light) (1; S) | - Flat - (2; S) | - () | | - Left - (2 Weight) | - Left - (1 Weighing) N = 3: | - Right - (1 Light) | - Right - (1; 3) | - Flat - (2) | | - Left - () | | | - Right - (3 Light) (1; 2) | - Flat - (1; 3) | Flat - () | | - Left - (3) | | | - Right - () | - Left - (1; 3) | - Flat - (2 Light) | Left - (1) Now, it is now assumed that the situation of less than N is found. Consider N (now assumed n> 3) a small ball. Still h = {log3 (2n)}. First, if n <(3 ^ h-1) / 2, we divide N ball into three piles: the first pile and the second pile have {n / 3} balls, third piles for the rest of the ball There are N-2 {n / 3}. We put the first and second piles on the left and right ends of the balance. Three cases: If the balance is balanced, then the bad ball is in the n-2 {n / 3} of the third pile, the problem is attributed to N-2 {n / 3} small ball, called H-1 time, and this When we can take a ball from the first or second pile to make a standard ball. But N-2 {n / 3} ≤ 3 {n / 3} -2 {n / 3} = {n / 3}, but by n <(3 ^ H-1) / 2 has n ≤ (3 ^ H- 1) / 2-1 = (3 ^ H-3) / 2 So N / 3 ≤ (3 ^ (H-1) -1) / 2 must be an integer, so we finally get N-2 {N / 3} ≤ {n / 3} ≤ (3H-1-1) / 2. According to the summary assumption, the problem of N-2 {n / 3} balls can be solved by the H-1 weighing. If the left side is heavy, or the bad ball is relatively light, and the bad ball is in the right side {n / 3} balls; or the bad ball is relatively heavy, and the bad ball is on the left {n / 3} ball. At this time, according to the conclusion 1, we have to find a bad ball and know its light weight. As the above calculation is exactly the same, N / 3 ≤ (3H-1-1) / 2 thereof 2 {n / 3} ≤ 3 ^ (H-1) -1 {log3 (2 {n / 3}))} ≤ H-1 is still available to solve the problem with the remaining H-1. If the right side is heavy, it is completely similar to the left weight. Now consider N = (3 ^ H-1) / 2, it is allowed to use a standard ball. We can divide the ball into three piles. The first pile is (3 ^ (h-1) 1) / 2, the second pile is (3 ^ (h-1) -1) / 2 plus standard ball, so the second pile is also ( 3H-1 1) / 2 balls, the third pile is the remaining (3H-1) / 2- (3H-1 1) / 2- (3H-1-1) / 2 = (3H-1 -1) / 2 balls. We put the first and second piles on the left and right ends of the balance. Three cases: If the balance is balanced, then the bad ball is in the third pile of (3H-1-1) / 2. According to the summary assumption, this can be solved by the H-1 title in the case of a standard ball. If the left side is heavy, or the bad ball is relatively light, and the bad ball is on the right side (3 ^ (h-1) 1) / 2 balls; or the bad ball is relatively heavy, and the bad ball is on the left except for additional standards Outside the ball (3 ^ (h-1) -1) / 2 balls. According to conclusions 1, we have to find bad balls to find {log3 (3 ^ (h-1) 1) / 2 (3 ^ (h-1) -1) / 2)} = h-1 time Know it. Therefore, this can also solve the problem with the remaining H-1 ". If the right side is heavy, it is completely similar to the left weight. This fully proves 2), 4) and 5 in 2), 4) and 5). The remaining is 3), the first half of: If n = (3H-1) / 2, then h then H times enough to ensure that the bad ball is found (but may not know the weight). This is very simple. If we take a ball, then according to 2), you can find bad balls with H times and know the light - the only exception is that if the one taken is just a bad ball - then At this time, the results of all weigh are balanced in balance. If this happens, all the proposal results are balance in balance. We can conclude that the bad ball is the ball that is taken. Of course, this ball has never been able to go through the balance. We must know it is Better than the standard ball, or is more light than the standard sphere. // The following proof is simple, hehe. Be good at thinking (reproduced) theorem: Up to the sky is called M times, you can only have only one bad ball (different) N (N = (3 ^ m-1) / 2) I find this bad ball in a small ball (you don't need to know the light), and the N is the best, you can't be big. Proof: * _ ~. First, let's talk about basic ideas, let's map once A long vector, this N long vector consists of elements {0, 1, -1} (the vector elements mentioned later in this article are taken from 0, 1, -1). The mapping relationship is as follows. 1: Put N Number, 1, 2, .... N2: The elements of the n (k] .a [k] of the kth k] are determined in the following ways. In this weigh: if i (i = 1, 2 ... n) a small ball in the left, let A [K] (i) = 1; if i (1 = 1, 2 ... n) a small ball in the right disk Let A [k] (i) = - 1; if the first (i = 1, 2 ... n) a small ball does not participate in the weigh, let A [k] (i) = 0. Here A [ K] (i) representing the IEE element of the vector a [k]. Below we construct a set of vector groups a satisfying two conditions, preparing for the following work: for any I, JA [i]! = -A [j] (! = indicates unequal) 2.sum (a) = 0, i.e., a is the zero vector and all vectors .____________________________________________________________________ | | | Step: we first prove that the vector length m satisfying such conditions does not exceed the number n = (3 ^ m-1) / 2 || ___________________________________________________________________ | vector we first note the total number of all the elements from {-1, 0} is removed nonzero vector 3 ^ m. The remaining 3 ^ m-1 vector is paired in opposite vectors (remembering the corresponding elements), with (3 ^ m-1) / 2 pairs. Obviously according to the conditions 1, each pair is taken up to one element In this way, n <= (3 ^ m-1) / 2 1 (calculated about 0 vectors). It is otherwise impossible to remove a vector in every pair of all (3 ^ m-1) / 2 pairs. . Use the anti-skilled manner, otherwise, we first consider how many of the non-zero vectors in all vectors, apparently 2 * 3 ^ (m-1), because such vectors must be two two mutual opposite So all (3 ^ m-1) / 2 pairs of 2 * 3 ^ (m-1) / 2 = 3 ^ (m-1) pair of {1, -1} for the first bit. This is if we are in each pair In the words of all vectors, we consider all of the main elements, and its value should be the sum of the first non-zero vector first elements mentioned earlier. And -1 3 ^ (m-1) is odd, so it is not possible to be even zero. Those of the above constraints are known for all the vector and zero. Contradiction. So we know the two constraints to satisfy the above , n <= (3 ^ m-1) / 2 ___________________________________________________ | || Step: next we prove that n = (3 ^ m-1) / 2 is achieved || _________________________________________________ | _ by induction .m = 1, n = (3 ^ 1-1) / 2 = 1, take (0) m = 2, n = (3 ^ 2-1) / 2 = 4, take (0, 0), (0, 1) (- 1, 0), (1, -1) set M = k, which is to find (3 ^ k-1) / 2 K long vector of the condition. So m = k 1, us Adding elements -1, 0, 1, adding elements -1, 0, 1 before the K long non zero vector, so that it is 3 [(3 ^ k-1) / 2-1] = (3 ^ (k 1) -1) / 2-4. Yixin These vectors also meet the above-mentioned constraints. Also known as the previous certificate, M =
