In the tradition of weighing puzzles, you have yet another batch of coins to sort. The only way to distinguish the coins is by their weights. This time there are nine coins. Three coins weigh 20g, three coins weigh 21g, and three coins weigh 22g.

You need to sort the coins by weight, but this time you must use an unusual three way scale. The scale operates as follows:

- Three weights must be placed on the scale for a meaningful result.
- If all three weights are equal, the scale will be in perfect balance.
- If one weight is lighter than the other two, the scale will show that weight is the lightest.
- If two weights are equal and are lighter than the third, the scale will indicate that scenario.

Examples:
Ex1: If A=30 B=30 C=30 then the scale will be in balance.
Ex2: If A=30 B=31 C=32 then the scale will indicate that A is the lightest of the three, but not tell which of B and C is lighter.
Ex3: If A=30 B=31 C=31 then the scale will indicate that A is the lightest of the three, but not tell that B and C are equal. (undistinguishable from Ex2)
Ex4: If A=30 B=30 C=31 then the scale will indicate that A and B are equal and less than C.

Using this three way scale, can you sort the coins in five weighings?

I think this solution works, but hopefully someone else can come up with a more elegant one.

Weigh any three non-overlapping triplets. (costs 3 weighings) There are a number of possibilities for the results:

1) all three balance.

We've separated the items, but we need to put them in order. Weigh one from each triplet to determine the lightest, then two from one of the remaining and one from the other remaining to determine the order of the other two. Total weighings: (5)

2) exactly two balance.

Impossible. If two balance then the remaining three are all equal and will also balance.

3) exactly one balances.

Since the two other weighings are now only between two choices, the lighter ones all match and the heavier ones all match, but we don't know where the balanced ones fit in weight-wise. Weigh two balanced ones vs one of the lights and against one of the heavies to place it in the correct order. (lighter on both makes it the lightest, heavier on both makes it the heaviest, else its the middle one.) Total weighings (5)

4) none balance.

Since all are imbalanced there are some number of "lighter" coins and some "heavier". There must be at least 3 "lighter" and no more than 6. But 6 is actually impossible, since it would require the three heavier coins to be the heaviest kind, and with an odd number each of medium and light, at least one pair would be uneven and hence not balance as in Ex4 above.

4a) none balance, three "lighter"

Since every "lightest" coin must be in the "lighter" set, the three "lighter" coins are the "lightest". Weigh the remaining 6 in two triplets. The lighter ones are "medium" coins and the heavier ones are "heavy" coins. (If the fourth weighing balances, weigh two from that set against one from the other three to determine which are the heavy ones and which the medium.) Total weighings: (5)

4b) none balance, four "lighter"

Since all of the "lightest"coins are necessarily in the ligher set, the pair is LL (two lightest) and one each of the singles are L and M. (If the pair is MM there's not enough coins for 3 L's.) Further the M is opposite HH (two heavies) or else it would have shown a pair as lightest. We need to know which of the singles is L vs M and which of the other three "heavies" is the H. Weigh the LL pair against one of the singles. If it matches the single is L otherwise its M, and the other single is the other. Now weigh the three unknowns (opposite the LL and L). Since one is H and two are M, the scale shows which is the H. Total weighings: (5)

4c) none balance, five "lighter"

This case is the same strategy as 4b) above. Now we know that the single lighter is L and the pairs are LL and MM, and that opposite MM is H (If the single were M then both pairs would have to be LL and that's one too many L). Weigh the known L against one of the lighter pairs -- if it balances you've got the LL pair otherwise the MM. Now weigh the three unknowns on the heavy side (which this time are HHM) and the light one on the scale is the M. Total weighings: (5)

I don't believe there are any other possible outcomes from the first three weighings, so in all cases, the coins can be completely identified in five weighings, even if the strategy depends quite a bit on the results of those first three.

Posted by Paul on 2005-09-06 02:26:36