Puzzle of the week - Week #2
You have sixteen coins. One of them is a counterfeit, and the other fifteen are genuine, but identical in appearance to the counterfeit. The counterfeit’s weight is different from that of a genuine coin, but you don’t know if the counterfeit is heavier or lighter than a genuine coin. You also have an unusual balance (the picture shows a top view of it), with three pans instead of the usual two. Any number of coins can be placed in each of the three pans, and the balance will tilt toward the heavier pan or pans if the weights are unequal.
What is the minimum number of weighings needed to identify the counterfeit? (You may put coins in all three pans in a single weighing.)
A single counterfeit coin can be identified in only two weighings. Here’s how it’s done:
Put four coins on each pan for the first weighing. If the weights are equal, the counterfeit must be among the remaining four coins; otherwise, the counterfeit is one of the four coins that are in the heavy (or light) pan.
Empty the pans, and put one coin from the group of four that is known to include the counterfeit in each pan. If the weights are equal, the counterfeit is the remaining coin from the group of four; otherwise, it’s the one with the odd weight.
This procedure doesn’t necessarily reveal whether the counterfeit is heavy or light. A third weighing would be needed in order to settle this question if the weights were equal in both of the first two weighings.
The traditional version of this puzzle involves finding a counterfeit among twelve coins, using a two-pan balance, for which three weighings are needed (why?). A particularly challenging variation of the three-pan puzzle is to determine the best strategy for identifying two identical counterfeits among 16 coins. As many as six weighings appear to be necessary; can you prove this, or show how to do the job in fewer than six weighings?
Comment by praveen — January 25, 2006 @ 10:14 pm