How many weighings with a beam balance are required to rank five different weights from lightest to heaviest?

Pick 2 coins. You can rank these 2 coins using 1 weighing. Call the lighter one
A; the heavier one B.

Pick another. Weigh A against it. It might be heavier, so you must weigh B
against it. At any rate, a further 2 weighings are needed to rank the 3rd coin;
3 in all. The same applies if you'd weighed it against B first.

Now rename the coins A (lightest), B, C (heaviest).

It takes another 2 to place the 4th coin picked. Weigh it against B. If it is
lighter than B, weigh it against A next; if it is heavier than B, weigh it
against C next. Whatever the result, those 2 weighings have ranked the first 4
coins.

It takes another 3 to place the last coin. There are 5 possible results, so 2
weighings aren't enough. But 3 are enough.

1+2+2+3=8 weighings in all.

The general pattern is that the 1st 2 coins need 1 weighing, then the j'th coin
needs k weighings, where k is the lowest k where 2^k >= j. ( ^ means "to the
power".)

To see that this is enough, consider the situation where the (2^k)-1 coins have
been ranked, and the 2^k'th coin is to be ranked. Weigh it against the coin in
the middle of the ranking of the first (2^k)-1. (The one of median weight.) You
now have to rank the coin among either the heaviest or the lightest 2^(k-1) - 1
coins, which you do in the same way, by weighing it against the one in the
middle of this ranking. This sort of algorithm is known as "binary chop".

To see that more won't do, note that n weighings can only give 2^n results, and
with 2^n or more coins there are more than 2^n results to be distinguished, so n
weighings are not enough.

Note that 5 coins need 8 weighings, even though you might have thought that 7
would be enough: there are 120 possible orders, and 7 weighings can give any of
128 possible results.

-- Richard Sabey <rsa@swindon.gpsemi.com>

You've demonstrated that 5 coins need 8 weighings in an insertion
sort; you haven't demonstrated that there isn't some other sorting
method that requires only 7.

Weigh two coins, call the heavier A and the lighter B.  Weigh two
other coins; call the heavier C and the lighter D.  Weigh A against C.
Assume A is heavier (if not, relabel the coins).  Now we know A>C>D,
A>B.

Weigh E against C, then (if heavier) against A or (if lighter) against
D.  Now we know the complete order of A,C,D,E; we also know that B is
lighter than A.

Finally, weigh B against the middle one of C,D,E (if E is heavier than
A, just weigh B against C and D), then against the appropriate
(lighter, heavier) one.  This puts B in its place.

But now we're done.  The total number of weighings is 7.  (3 in the
first paragraph, 2 in each of the others).

-- Seth Breidbart <sethb@panix.com>

Nope.  You can do it in 7 weighings - here's how:

Pick any two and weigh them.  Pick any other two and weigh them.  Then
weigh the heavier ones of the previous weighings.  Now, there will be a
way to name the objects as A,B,C,D and E so that according to the previous
weighings, A>B C>D and A>C are all true (and E hasn't yet been weighed).
Name them so.

There will be 15 possible orderings left - continue weighing as follows:

  C>E D>E B>D B>C   => ABCDE
  C>E D>E B>D C>B   => ACBDE
  C>E D>E D>B B>E   => ACDBE
  C>E D>E D>B E>B   => ACDEB
  C>E E>D B>E B>C   => ABCED
  C>E E>D B>E C>B   => ACBED
  C>E E>D E>B B>D   => ACEBD
  C>E E>D E>B D>B   => ACEDB
  E>C A>E B>C B>E   => ABECD
  E>C A>E B>C E>B   => AEBCD
  E>C A>E C>B B>D   => AECBD
  E>C A>E C>B D>B   => AECDB
  E>C E>A B>C       => EABCD
  E>C E>A C>B B>D   => EACBD
  E>C E>A C>B D>B   => EACDB

Btw, this is not a unique solution with just 7 weighings.

-- Risto Lankinen <ristol@xerver.icl.fi>

[ Editor: no answer to the bonus puzzle was found in the collected
postings. ]