All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars
 perplexus dot info

 Four Coins and Three Weighings (Posted on 2007-03-08)
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.

 See The Solution Submitted by Brian Smith Rating: 4.3333 (3 votes)

Comments: ( Back to comment list | You must be logged in to post comments.)
 proof | Comment 2 of 10 |

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 BADCACBD 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 > BCAC < BD  imposs.  abcd/acbd  imposs.AC = BD abdc/adbc  imposs.  bacd/bcadAC > 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 BDCACABD 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 > BCAC < BD acdb/adcb  imposs.  cabd/dbadAC = 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

 Search: Search body:
Forums (0)