The "12 Coin Problem"
I first heard of the famous "12 Coin Problem" (or 12 Ball Problem, or whatever you want to call it) back in high school, but was recently re-reminded of it by an e-mail from my friend James Lin. I decided that it was one of my favorite problems, and so, having a good chunk of free time, I might as well put up a web page about it.
The basic gist of the problem is the following:
- You have 12 coins, one of which is counterfeit. The counterfeit coin can only be discerned from the others because it is either slightly heavier or slightly lighter than the others. (You don't tell which; nor can you tell without using a scale.)
- You have a two-pan scale on which you can place the coins. The scale will tell you if the coins balance, if the left side is heavier, or the right side is heavier.
- Using the scale only three times, how can you determine which coin is counterfeit, AND whether it is heavier or lighter?
- (There are no silly "tricks" to this problem -- the answer is gained through straightforward deduction.)
I think that if you take the time to solve it without looking at the solution, you'll feel pretty good about yourself. Of course, if you don't go for that sort of thing, you can try some of the links below. Also, if it's too easy for you, you can try the other problems on this page.
One alternative I've seen recently is termed the "non-adaptive" version of the problem. Basically, let's say you have the same problem with the added constraint that you don't know the results of any of the weighings until you're done with all three of the weighings.
That is, the answer to the problem above generally includes something like "If X side is heavier, than do this, or if Y side is heaver, then do this instead." That wouldn't be possible given this constraint, since you don't know any results and you need to plan all three weighings in advance.
A few other variants:
- If you have a pool of known non-counterfeit coins to use as well, you can extend the 12-coin problem to 13 coins. How would you do this?
- This problem should be generalizable, I think, to N coins and M weighings, though it's only an easy solution (easy = I can potentially solve it) if you also have the pool of non-counterfeit coins as in above. The problem should be solvable so long as N <= [(3^M)/2)]. Sometime when I have more free time, I'll come up with a rigorous proof of this; if you happen to have one, let me know. As an example, I've done the M=4, N=80.
|
Last Updated June 2005 |
| Home |
|