You have five jars of pills. One jar of pills is contaminated. The only way to tell which pills are contaminated is by weight. A regular pill weighs 10 grams; a contaminated pill weighs 9 grams. You are given a scale and allowed to make just one measurement with it. How do you tell which jar is contaminated?
Solution: This is a classic technical interview puzzle. There really isn’t a trick— it is a matter of working through the possible solutions to find one which works. There are possibly some assumptions you have to get out of the way—make sure you’ve framed the problem correctly—and then the answer emerges. Consider how The Critical Connection blog (http://w-uh.com/) analyzes the puzzle:
You basically have five unknowns—each of the jars could be the one which is contaminated. You are only allowed to perform one weighing, and the answer must discriminate amongst the five unknowns. So how does one weighing give you one of five possibilities? Well, clearly the result of the weighing is a number, so you have to design the experiment so the numeric result tells you what you want to know.
One of the assumptions you have to get through is that weighing the jars themselves is helpful. After a little thought you realize it isn’t. Another assumption is that you can only weigh one pill from each jar. This is not a stated constraint, and in fact weighing only one pill from each jar won’t get you the answer. The solution is to weigh a different number of pills from each jar. Say you take one pill from jar 1, two from jar 2, three from jar 3, and four from jar 4 (You can take five from jar 5 or more elegantly zero from jar 5, either way you’ll get the answer.) Now there are five cases and five possible results:
Jar 1 is contaminated. The weight will be 1 9 + 2 10 + 3 10 + 4 10 = 99
Jar 2 is contaminated. The weight will be 1 10 + 2 9 + 3 10 + 4 10 = 98
Jar 3 is contaminated. The weight will be 1 10 + 2 10 + 3 9 + 4 10 = 97
Jar 4 is contaminated. The weight will be 1 10 + 2 10 + 3 10 + 4 9 = 96
Jar 5 is contaminated. The weight will be 1 10 + 2 10 + 3 10 + 4 10 = 100
For a more conversational approach to this puzzle, consider this candidate’s response:
If I’m allowed just one weighing, I need to get all the information necessary to discriminate between contaminated and non contaminated pills. Here’s one way to approach the problem. First, mark the jars with numbers from 1 to 5. Now, take 1 pill from jar 1, take 2 pills from jar 2, take 3 pills from jar 3, take 4 pills from jar 4, and take 5 pills from jar 5. Put all of the 15 selected pills on the scale and take the measurement. Now, if all the pills were non contaminated, that is each weighed 10 grams, the total weight on the scale would be 150 grams (1 10 + 2 10 + 3 10 + 4 10 + 5 10). But since a number of contaminated pills actually weigh 9 grams, the total will be somewhat less. How much less? Subtract the actual measurement from 150, and the resulting number will point directly to the contaminated jar.
I’m not aware of any other way to solve this problem. By the way, it is easy to demonstrate that this solution works. Assume that jar 4 has the contaminated pills. Then the total weight on the scale will be (1 10 + 2 10 + 3 10 + 4 9 + 5 10 = 146. Now subtract 146 from 150, which leaves 4, the number of the jar containing the contaminated pills.
Answer: Take as many pills from each jar as corresponds to the number of the jar.