2
$\begingroup$

In looking through the questions already posted about balance scales, they seemed to mostly center around finding counterfeit coins compared to good coins. The question I'm trying to investigate is if I have 5 coins, all of different weights, and I only have a balance scale, how many weighings will it take to be able to put 5 coins in order from heaviest to lightest.

From what I've been able to uncover so far, with 8 weighings, you'll always be able to put 5 coins in order. However, it was suggested that there might be a strategy that will only take 7 weighings. Here's what I came up with so far...

Weigh two coins against each other. Then weigh a third coin against the first and that third coin against the second. Then you can place those three coins in order from heaviest to lightest (call it coin A heaviest, coin C the lightest, and coin B in between). It might take less than those three weighings, but worst case scenario, you'll need three weighings. Then take a fourth coin and weigh it against coin B. If heavier, weigh it agains coin A to determine where it goes, if lighter, weigh it against coins C to determine where it goes. This took two more weighings so we're up to a total of 5 weighings. Lets say that this coin is actually the lightest. We now have from heaviest to lightest of A, B, C, and D. We now have one final coin to figure out where it goes. If we compare it to B, find out it's lighter, so we compare it to C, find out it's lighter, then compare it to D, we would finally know for certain, after 3 more weighings (a total of 8 weighings) the order of coins from heaviest to lightest (A, B, C, D, E).

I didn't think it would be productive to weigh pairs of coins since we don't know the exact weights of any of the coins), but I haven't explored that yet. Are there different strategies I haven't thought of yet that might help reduce the number of weighings to guarantee an order.

$\endgroup$
3
$\begingroup$

Using only weighings with one coin on each side, one can prove that the ordering can be determined with seven weighings:

Weigh coins $A$ versus $B$, then $C$ versus $D$, and then the heavier in each pair against each other. We can re-label the heaviest found as $D$, its original partner as $C$, and the loser of the "weigh-off" as $B$. These three weighings have led knowledge that $D>B>A$ and $D>C$.

Next weigh the coin $E$ (which has thus far not been touched) against $B$, and then against $D$ if $E>B$, or against $A$ if $E<B$. These fourth and fifth weighings tell you the exact order of $D, E, B$ and $A$. For example, you might find that $D>B>A>E$. It does not matter which of the possibilities you find; the important facts are that you know the order and that the second lightest and the lightest are not $D$.

For the sixth weighing, weigh coin $C$ against the second lightest of the other coins. In our example, we would weigh $C$ versus $A$. Then the only doubt left is the relative weight of $C$ and just one other coin. In our example, if $C>A$ then we can complete the full ordering by weighing $C$ versus $B$ because we already know that $D>C$.

Thus the seventh weighing determines the complete order.


The way to figure this out was:

Without loss of generality, one can assume that the first weighing tells you that coin $B$ is heavier than coin $A$ (written as $B>A$). Then there are only two classes of choices of next weighings:

(1) Weigh coin $C$ against coin $A$ (or any equivalent weighing against an already-weighed coin): Here, a possible result is $C>A$ which leaves 40 allowed orders. Since each weighing provides only one bit of information, discerning among $40$ orders requires at least six weighings, for a total of eight.

(2) Weigh coin $C$ against coin $D$ (or any equivalent weighing of two not-yet-weighed coins): Then there are three classs of next weighing choices available.

(2a) If the third weighing is $E$ versus $D$ (or any of the already-weighed coins) then one possibility says that $E<D$, which leaves $20$ allowed orders, requiring at least $5$ further weighings, for a total of eight.

(2b) If the third weighing is $D$ versus $A$ (or equivalently $B$ versus $C$) then the answer $D>A$ leaves $25$ possible orderings (slotting $E$ into any of $5$ positions, with the first four ordered $DCBA, DBCA, DBAC, BDAC$ or $BDCA$) which again requires at least $5$ further weighings, for a total of at least eight.

(2c) If the third weighing is $D$ versus $B$ (or equivalently $A$ versus $C$) then the answer must be equivalent to $D>B$. So $D>B>A$ and you can slot $C$ into any of three positions (but not into $C>D$) and then $E$ into any of $5$ positions. With $15$ allowed possibilities, it might still be possible to discern the ordering in only four more weighings.

So assume we have (in three weighings) $D>B>A$ and $D>C$. The next weighing needs to involve coin $E$ because if we weigh $C$ against $B$ or $A$ there will be some chance of leaving two remaining positions possible for $C$, thus two times five remaining allowed orderings, which cannot be disambiguated in only three further weighings.

3a) Say the next choice (the 4th weighing) is to weigh $E$ versus $B$ (this is the obvious one to try because $D>B>A$). Then if we find $E<B$ we will end up knowing that $D>B>E>A$ or $D>B>A>E$. We spend our fifth weighing on $A$ versus $E$ to fully order those four. Since we know $D>C$ we can now find where $C$ belongs in only two more weighings (starting from weighing $C$ against the second lightest of the others), for a total of seven weighings.

Similarly, if we find $E>B$ we will end up knowing that $D>E>B>A$ or $E>D>B>A$. We spend our fifth weighing on $D$ versus $E$ to fully order those four. And again we can properly place $$ in two more wiehings, for a total of seven.

(3b) If the fourth weighing were to be $E$ versus $A$ or $E$ versus $D$, then we would require eight weighings in the end.

$\endgroup$
  • $\begingroup$ Thanks Mark. Thanks makes a lot of sense. That thinking about how each weighing can cut the number of allowed orders in half had never occurred to me. Very much appreciated! $\endgroup$ – Josh C. Jul 19 '17 at 0:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.