You have a scale which compares two weights but instead of telling which is heavier or lighter, this scale returns the difference of the weights but will not tell which is heavier. In order for the scale to display an accurate result, the amount of weight on each side must be at least 20g and the difference can not exceed 20g. The scale will not report a result unless there is a weight on each side. If the difference exceeds 20g, the scale will report an error.

Use this scale no more than six times, sort an otherwise identical set of six coins with weights of 20, 21, 22, 23, 24, and 26 grams.

Examples:
Ex 1: If A=30 B=30 then the scale reports 0 (equal)
Ex 2: If A=31 B=29 then the scale reports 2
Ex 3: If A=29 B=31 then the scale reports 2 (undistinguishable from example 2)

First, choose a coin arbitrarily and call it A.  For the first 5 trials, weigh A agains each of the other coins.  The following table shows the number of each result for each possible weight value for A:

•  A:    1   2   3   4   5   6
• 20g   1   1   1   1   0   1
• 21g   2   1   1   0   1   0
• 22g   2   2   0   1   0   0
• 23g   2   1   2   0   0   0
• 24g   1   2   1   1   0   0
• 26g   0   1   1   1   1   1

In particular, note that they are all distinct, so after using the scale 5 times, we know the weight of A.  Further, each '1' in the above table determines the weight of another coin uniquely.  This means for A = 20 or 26, we're already done. 

For A = 21 or 24, there is only one ambiguity to resolve, and we know the weights of 4 out of six.  All that remains is to weigh one of the ambiguous coins against one that we already know besides A.  This result will resolve the ambiguity and solve the problem for these cases.

It remains to consider A = 22 or 23. 

If A = 23, we know the weight of A, and we know which coin weighs 21, but we have two ambiguities to resolve.   Consider weighing the two coins we know against one coin that gave us a 3 earlier, and one that gave us a 1 earlier.  Now on the left we know we have 44 (23+21), and the right is one of {20+22=42, 20+24=44, 22+26=48, 24+26=50}, so the possible results are {2, 0, 4, 6}.  Each of these results is unique, and so is each possible combined weight on the right, so this determines exactly which coins are on the right, and this solves the problem.

Finally, we have the case of A = 22.  In this case, we know which coin weighs 26.  Consider weighing this coin alone against two coins: one each that gave us 1 and 2 weighted against A.  The possible arrangements on the right are now {20+21=41, 20+23=43, 21+24=45, 23+24=47}, which means the possible results are {15, 17, 19, error}.  Again, there's no ambiguity to these results, so they determine exactly which coins are on the right, and this solves the problem.  QED

Posted by josh on 2005-07-01 17:33:00