You have 12 coins. They are completely identical except six of them weigh 24g and the other six weigh 25g. You have only a balance scale to sort them out. What is the minimum number of weighings which guarantees all the coins to be sorted?

If you weigh two at a time, there are 6 pairs to weigh (six weighings) in the first round. If each of these weighings balance, then you have 6 pairs each of member of which is equal in weight to its partner. In the next three weighings weigh one representative of each against the representative of another. In at least one case there must be an unequal weighing, showing that in that pair which is the heavy and which is the light coin. In the third round, just weigh the heavy against a representative of one of the other two pairs: that determines which of those pairs has heavy coins (and in turn the groups of four from the original round).

This is 10 weighings.

If unequal weights come up earlier than in the above scenario, the number of unknown coins goes down by 2 for each such balance tipping, so you could get by with just 6 weighings, if each pair in the initial round weighed unequally.

By information theory, the minimum possible number of weighings (with no guarantee there's actually a way of doing it in this few), would be the base-3 log of 12C6.

12C6 = 924 and its base-3 log is 6.2..., so even theoretically no solution could guarantee less than 7 weighings.

One thing that contributes to the excess over the information theoretic value is that certain combinations of results cannot happen, such as a single equal weighing followed by 5 straight unequal weighings in the remainder of the paired coins in the first round.

On second thought
You don't need the sixth weighing in the above worst-case scenario: If the first 5 weighings all are equal, then so will the 6th, so it is not needed. On the other hand, in the second round, the third of those three weighings can't be dispensed with, as you don't know which of the two is the heavier, even though you know one must be.

This reduces the worst case scenario to 9 weighings.

This also still leaves the way for more clever methods to reduce the worst case to 8 or 7 weighings, but I don't see how that can be done.

Posted by Charlie on 2004-01-18 12:34:11