You have eight marbles and a two-pan balance. All the marbles weigh the same, except for one, which is heavier than all the others. The marbles are otherwise indistinguishable. You may make no assumptions about how much heavier the heavy marble is. What is the minimum number of weighings needed to be certain of identifying the heavy marble? |
The first step in solving this problem is to realize that you can put more than one marble in each pan of the balance. If you have equal numbers of marbles in each pan, then the heavy marble must be in the group on the heavy side of the balance. This saves you from having to weigh each marble individually, and it enables you to eliminate many marbles in a single weighing.
Once you realize this, you are likely to devise a binary search-based strategy for finding the heavy marble. In this method, you begin by putting half of the marbles on each side of the balance. Then you eliminate the marbles from the light side of the balance and divide the marbles from the heavy side of the balance between the two pans. As shown in Figure 1, you continue this process until each pan holds only one marble, at which point the heavy marble is the only marble on the heavy side of the balance. Using this process you can always identify the heavy marble in three weighings.
This may seem to be the correct answer. The solution wasn’t completely obvious, and it’s an improvement over weighing the marbles one by one. If you’re telling yourself that this seemed too easy, you’re right. The method described so far is a good start, but it’s not the best you can do.
How can you find the heavy marble in fewer than three weighings? Obviously, you’ll have to eliminate more than half the marbles at each weighing, but how can you do that?
Try looking at this problem from an information flow perspective. Information about the marbles comes from the balance, and you use this information to identify the heavy marble. The more information you derive from each weighing, the more efficient your search for the marble will be. Think about how you get information from the balance: You place marbles on it and then look at the result. What are all the possible results? The left pan side could be heavier, the right side could be heavier, or both sides could weigh exactly the same. So there are three possible results, but so far you’ve been using only two of them. In effect, you’re only using 2/3 of the information that each weighing provides. Perhaps if you alter your method so that you use all of the information from each weighing you will be able to find the heavy marble in fewer weighings.
Using the binary search strategy, the heavy marble is always in one of the two pans, so there will always be a heavy side of the balance. In other words, you can’t take advantage of all the information the balance can provide if the heavy marble is always on the balance. What if you divided the marbles into three equal-sized groups, and weighed two of the groups on the balance? Just as before, if either side of the balance is heavier, you know that the heavy marble is in the group on that side. But now it’s also possible that the two groups of marbles on the balance will weigh the same - in this case, the heavy marble must be in the third group that’s not on the balance. Because you divided the marbles into three groups, keeping just the group with the heavy marble eliminates 2/3 of the marbles instead of half of them. This seems promising.
There’s still a minor wrinkle to work out before you can apply this process to the problem at hand. Eight isn’t evenly divisible by three, so you can’t divide the eight marbles into three equal groups. Why do you need the same number of marbles in each group? You need the same number of marbles so that when you put the groups on the balance the result doesn’t have anything to do with differing numbers of marbles on each side. Really, you need only two of the groups to be the same size. You’ll still want all three groups to be approximately the same size so you can eliminate approximately ⅔ of the marbles after each weighing no matter which pile has the heavy marble.
Now you can apply the three-group technique to the problem you were given. Begin by dividing the marbles into two groups of three, which you put on the balance, and one group of two, which you leave off. If the two sides weigh the same, the heavy marble is in the group of two, and you can find it with one more weighing, for a total of two weighings. On the other hand, if either side of the balance is heavier, the heavy marble must be in that group of three. You can eliminate all the other marbles, and place one marble from this group on either side of the balance, leaving the third marble aside. If one side is heavier, it contains the heavy marble; if neither side is heavier, the heavy marble is the one you didn’t place on the balance. This is also a total of two weighings, so you can always find the heavy marble in a group of eight using two weighings. An example of this process is illustrated in Figure 2
Important | Generalize your solution. What is the minimum number of weighings to find a heavy marble among n marbles? |
This is the part where the interviewer determines whether you hit on the preceding solution by luck or because you really understand it. Think about what happens after each weighing. You eliminate 2/3 of the marbles and keep 1/3. After each weighing you have 1/3 as many marbles as you did before. When you get down to one marble, you’ve found the heavy marble.
Based on this reasoning, you can reformulate the question as, “How many times do you have to divide the number of marbles by 3 before you end up with 1?” If you start with 3 marbles, you divide by 3 once to get 1, so it takes one weighing. If you start with 9 marbles you divide by 3 twice, so it takes two weighings. Similarly, 27 marbles require three weighings. What mathematical operation can you use to represent this “How many times do you divide by 3 to get to 1” process?
Because multiplication and division are inverse operations, the number of times you have to divide the number of marbles by 3 before you end up with 1 is the same as the number of times you have to multiply by 3 (starting at 1) before you get to the number of marbles. Repeated multiplication is expressed using exponents. If you want to express multiplying by 3 twice, you can write 3^{2}, which is equal to 9. When you multiply twice by 3 you get 9 - it takes two weighings to find the heavy marble among 9 marbles. In more general terms, it takes i weighings to find the heavy marble from among n marbles, where 3^{i} = n. You know the value of n and want to calculate i, so you need to solve this for i. You can solve for i using logarithms, the inverse operation of exponentiation. If you take log_{3} of both sides of the preceding equation you get i = log_{3} n.
This works fine as long as n is a power of 3. However, if n isn’t a power of 3, then this equation calculates a noninteger value for i, which doesn’t make much sense, given that it’s extremely difficult to perform a fractional weighing. For example, if n = 8, as in the previous part of the problem, log_{3} 8 is some number between 1 and 2 (1.893 … to be a little more precise). From your previous experience, you know it actually takes two weighings when you have eight marbles. This seems to indicate that if you calculate a fractional number of weighings you should round it up to the nearest integer.
Does this make sense? Try applying it to n = 10 and see whether you can justify always rounding up. log_{3} 9 is 2, so log_{3} 10 will be a little more than two, or three if you round up to the nearest integer. Is that the correct number of weighings for 10 marbles? For 10 marbles, you would start out with two groups of 3 and one group of 4. If the heavy marble were in either of the groups of 3, you could find it with just one more weighing, but if it turned out to be in the group of 4 you might need as many as two more weighings for a total of 3, just as you calculated. In this case the fractional weighing seems to represent a weighing that you might need to make under some circumstances (if the heavy marble happens to be in the larger group) but not others. Because you’re trying to calculate the number of weighings needed to guarantee you’ll find the heavy marble, you have to count that fractional weighing as a full weighing even though you won’t always perform it, so it makes sense to always round up to the nearest integer. In programming, the function that rounds up to the nearest integer is often called ceiling, so you might express the minimum number of weighings needed to guarantee you’ll find the heavy marble among n marbles as ceiling(log_{3}(n)).
Tip | For the group of 4 (out of the total of 10 marbles), you would divide the 4 marbles into two groups of 1 and one group of 2. If the heavy marble happened to be in the group of 2, you would need one more weighing (the third weighing) to determine which was the heavy marble. A fractional weighing may also represent a weighing that will always be performed but won’t eliminate a full 2 2/3 of the remaining marbles. For example, when n = 8, the fractional weighing represents the weighing needed to determine which marble is heavier in the case where the heavy marble is known to be in the group of two after the first weighing. In any case, it must be counted as a full weighing, so rounding up is appropriate. |
This is another example of a problem designed such that the wrong solution occurs first to most intelligent, logically thinking people. Most people find it quite difficult to come up with the idea of using three groups, but relatively easy to solve the problem after that leap. It’s not an accident that this problem begins by asking you to solve the case of eight marbles. As a power of 2, it works very cleanly for the incorrect solution, but because it’s not a power (or multiple, for that matter) of 3 it’s a little messy for the correct solution. People generally get the correct answer more quickly when asked to solve the problem for nine marbles. Look out for details like this that may steer your thinking in a particular (and often incorrect) direction.
This problem is a relatively easy example of a whole class of tricky problems involving weighing items with a two-pan balance. For more practice with these, you might want to try working out the solution to the preceding problem for a group of marbles in which one marble has a different weight, but you don’t know whether it’s heavier or lighter.
No comments:
Post a Comment