Let's try another balancing problem:
This time, the collector has twelve coins, the fake doesn't weigh the same as the others, but he can't remember if it's heavier or lighter. Now, how many weighings does it take to determine the fake coin?
A hint: The previous problem relied simply on reducing the number of coins which might be the counterfeit. In this problem, the coins you know are genuine are just as important.
1 comment:
Note that it might take two weighings to find the fake among three coins - if your first two balance, it's the third, but if they don't, you have to weigh one of them against the third (which you now know is real) to determine the fake. Four coins also take two weighings - the first weiging narrows it down to two coins, then you weigh one of those against a coin you know is real.
For twelve, it takes three weighings. The first weighing is four-on-four. If they balance, the fake is in the third group of four, and you have two weighings from there.
If they don't balance, it gets tricky. Call the coins on the balance Group A and Group B, and say Group A was heavier. For the second weighing, put two coins from Group A and one coin from Group B on each side of the scale. If they balance, it's one of the other two coins from Group B, and you can weigh one of those against a coin you know is genuine for the third weighing.
If they don't balance, you've narrowed it down to three coins - the two Group A coins on the heavier side, or the Group B coin on the lighter side. Weigh the two group A coins against each other. If they balance, it's the Group B coin. If they don't, the heavier coin is the fake.
You can actually get up to 13 coins in three weighings (two groups of four and a group of five). After that, the second and subsequent weighings become increasingly complicated, but with n weighings, you can have up to... um... the sum of the first n-1 powers of three, plus one (so for four, it's 1 + 3 + 9 + 27 = 40). I don't know how to do that in HTML, but in TeX, it would be $\sum^{n-1}_{0}3^{n}$.
Post a Comment