You have four coins to sort with a standard balance scale. Their weights are 20g, 21g, 22g and 23g. Prove that there is no strategy which can guarantee sorting the coins with only three weighings.

I think you forgot the cases A, B =21, 22, C=23 D=20 the step AB=CD AC>BD Thus, if AB=CD AB>CD, the cases to consider are (in order A,B,C,D)

23 20 22 21
22 21 23 20
20 23 22 21
22 21 20 23

Then you have 4 possibilities and only two possible results. Doing anything different after AB=CD wouldn't change this problem, as you would have 8 possibilities if AB=CD (ie the arbitrary first weighing results in it being equal)

Due to equality being commutative, you can't favor one side over the other, so after AB=CD and {AC>BD, AC<BD} all that is known is that A or C is 20, and B or D is 23.

Posted by Gamer on 2007-03-10 14:55:51