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.

First the basics: the differences in weight as small in comparison to the weight of each coin, so the number of coins on each side of the balance must be the same.

When one coin is balanced against one other, there are only two possibilities: one or the other is heavier, as there are no equal weight coins. When two coins are balanced against two others, one or the other pair can be heavier, or they balance equally.

There are 4! = 24 possible orderings for the weights of the coins.

If the first balance is one coin vs one coin, say A vs B, and, say, A is lighter, then this cuts the possibilities by 1/2, as there are as many orderings in which A < B as there are where A > B, so the possibilities are reduced to 12.  But the next two weighings can have only 3 possible results each, for a total of 9 combinations--not enough to distinguish among 12 possibilities.  So the first balancing cannot be between 1 coin vs 1 coin.

If the first balancing is between two pairs of coins, say AB vs CD, there are three possible outcomes: AB < CD, AB > CD and AB = CD. (Addition of weights assumed here--not multiplication). Without loss of generality we can let AB < CD represent the inequality. In that case the possibiliies are, from light to heavy:

ABCD ABDC BACD BADC
ACBD ADBC BCAD BDAC

Since there are more than 2*3=6 possibilities, the next two weighings will both have to be two against two. Or at least the second weighing would have to be 2 vs 2, and in two of its three possible outcomes, another 2 vs 2.  Also, A can't be paired with B again--that would be pointless. In fact, as there are only three possible ways of weighing 2 against 2, the remaining two weighings would have to be AC vs BD and AD vs BC. A table of outcomes consistent with the first weighing is:

         AD < BC   AD = BC   AD > BC
AC < BD  imposs.  abcd/acbd  imposs.
AC = BD abdc/adbc  imposs.  bacd/bcad
AC > BD  imposs.  badc/bdac  imposs

(and also, regardless of whether AC vs BD was done first or AD vs BC, in either case, equality might result, in which case there are four possibilities, precluding the possibility of a switch to comparing 1 vs 1 just for some instances.)

So it would be impossible to differentiate ABCD from ACBD, where A and B are defined as the ones on the low-weight side of the first weighing and BC those on the high-weight side.

So the question is moot as to whether the order could be found if equality between AB and CD was originally found, as we had wanted to guarantee a sorting regardless of the order of weights, but just for sake of curiosity:

The possibilities would be:

ACDB ADCB BCDA BDCA
CABD CBAD DABC DBAC

which is also more than 6 possibilites and so would require the remaining two balances of two vs two:

         AD < BC   AD = BC   AD > BC
AC < BD acdb/adcb  imposs.  cabd/dbad
AC = BD  imposs.   imposs.   imposs.
AC > BD dabc/dbac  imposs.  bcda/bdca

In this case, inequality regardles of which 2 vs 2 is done first, would preclude being saved by a possibility of switching to a 1 vs 1 for some outcomes.

Posted by Charlie on 2007-03-08 15:46:14