This is a classic question for consulting job interviews. A solution for n=12 can be found
here.
Cut and pasted below:
<<
Practice Question #5
You have 12 balls. All of them are identical except one, which is either heavier or lighter than the rest. The odd ball is either hollow while the rest are solid, or solid while the rest are hollow. You have a scale, and are permitted three weighings. Can you identify the odd ball and determine whether it is hollow or solid?
This is a pretty complex question, and there are actually multiple solutions. First, we'll examine what thought processes an interviewer is looking for, and then we'll discuss one solution. (This question is reportedly in use at McKinsey, incidentally.)
Start with the simplest of observations. The number of balls you weigh against each other must be equal. Yeah, it's obvious, but why? Because if you weigh, say three balls against five, you are not receiving any information. In a problem like this, you are trying to receive as much information as possible with each weighing.
For example, one of the first mistakes people make when examining this problem is that they believe the first weighing should involve all of the balls (six against six). This weighing involves all of the balls, but what type of information does this give you? It actually gives you no new information. You already know that one of the sides will be heavier than the other, and by weighing six against six, you will simply confirm this knowledge. Still, you want to gain information about as many balls as possible (so weighing one against one is obviously not a good idea). Thus, the best first weighing is four against four.
Secondly, if you think through this problem long enough, you will realize how precious the information gained from a weighing is: You need to transfer virtually every piece of information you have gained from one weighing to the next. Say you weigh four against four, and the scale balances. Lucky you! Now you know that the odd ball is one of the unweighed four. But don't give into the impulse to simply work with those balls. In this weighing, you've also learned that the eight balls on the scale are normal. Try to use this information.
Finally, remember that consultants love that out-of-the-box thinking. Most people who work through this problem consider only weighing a number of balls against each other, and then taking another set and weighing them, etc. This won't do. There are a number of other types of moves you can make - you can rotate the balls from one scale to another, you can switch the balls, etc.
Let's look at one solution:
For simplicity's sake, we will refer to one side of the scale as Side A, and the other as Side B.
Step 1: Weigh four balls against four others.
Case A: If, on the first weighing, the balls balance
If the balls on our first weighing balance we know the odd ball is one of those not weighed, but we don't know whether it is heavy or light. How can we gain this information easily? We can weigh them against the balls we know to be normal. So:
Step 2 (for Case A): Put three of the unweighed balls on Side A; put three balls that are known to be normal on Side B.
I. If on this second weighing, the scale balances again, we know that the final unweighed ball, is the odd one.
Step 3a: Weigh the final unweighed ball (the odd one) against one of the normal balls. With this weighing, we determine whether the odd ball is heavy or light.
II. If on this second weighing, the scale tips to Side A, we know that the odd ball is heavy. (If it tips to Side B, we know the odd ball is light, but let's proceed with the assumption that the odd ball is heavy.) We also know that the odd ball is one of the group of three on Side A.
Step 3b: Weigh one of the balls from the group of three against another one. If the scale balances, the ball from the group of three that was unweighed is the odd ball, and is heavy. If the scale tilts, we can identify the odd ball, because we know it is heavier than the other. (If the scale had tipped to Side B, we would use the same logical process, using the knowledge that the odd ball is light.)
Case B: If the balls do not balance on the first weighing
If the balls do not balance on the first weighing, we know that the odd ball is one of the eight balls that was weighed. We also know that the group of four unweighed balls are normal, and that one of the sides, let's say Side A, is heavier than the other (although we don't know whether the odd ball is heavy or light).
Step 2 (for Case B): Take three balls from the unweighed group and use them to replace three balls on Side A (the heavy side). Take the three balls from Side A and use them to replace three balls on Side B (which are removed from the scale).
I. If the scale balances, we know that one of the balls removed from the scale was the odd one. In this case, we know that the ball is also light. We can proceed with the third weighing as described in step 3b from Case A.
II. If the scale tilts to the other side, so that Side B is now the heavy side, we know that one of the three balls moved from Side A to Side B is the odd ball, and that it is heavy. We proceed with the third weighing as described in step 3b in Case A.
III. If the scale remains the same, we know that one of the two balls on the scale that was not shifted in our second weighing is the odd ball. We also know that the unmoved ball from Side A is heavier than the unmoved ball on Side B (though we don't know whether the odd ball is heavy or light).
Step 3: Weigh the ball from Side A against a normal ball. If the scale balances, the ball from Side B is the odd one, and is light. If the scale does not balance, the ball from Side A is the odd one, and is heavy.
Whew! As you can see from this solution, one of the keys to this problem is understanding that information can be gained about balls even if they are not being weighed. For example, if we know that one of the balls of two groups that are being weighed is the odd ball, we know that the unweighed balls are normal. Once this is known, we realize that breaking the balls up into smaller and smaller groups of three (usually eventually down to three balls) is a good strategy - and an ultimately successful one.
>>
Facebook
Twitter