You have five coins, apparently alike, but actually of different weights. You also have a two arm scale.
Can you manage to sort the coins in ascending order, using the scale only seven times?
Bonus question: can it be done in fewer weighings?
After A vs B halves the possibilities from 120 to 60, and the lower weight arbitrarily renamed A if necessary,
and C vs D halves the possibilities from 60 to 30, and again renaming the lighter one C if necessary,
only weighing A vs C or B vs D will halve the possiblities from 30 to 15. Let's say we weigh A vs C, and we again rename the lighter one A. The possibilities are:
abcde
abced
abecd
acbde
acbed
acdbe
acdeb
acebd
acedb
aebcd
aecbd
aecdb
eabcd
eacbd
eacdb
we have 4 weighings left, giving 2^4 = 16 possibilities to take care of, so we're still good, but 15 is odd so the best we can do is a 78 split, with the latter number being the extreme that another 3 weighings would handle.
The only way to get a 78 split is by weighing C vs E.
In the worse case, C < E, leaving 8 possibilities:
abcde
abced
acbde
acbed
acdbe
acdeb
acebd
acedb
at which point to get an even 44 split, we need to weigh D vs E. In the above cases they are symmetrical so it doesn't matter which we choose: say D < E:
abcde
acbde
acdbe
acdeb
Then only B vs D splits it 22. Again, if B<D (if not, rename):
abcde
acbde
Then C vs B settles the matter.
The only matter not covered is the possibility of 7 in the 78 split being the case, where you'd have
abecd
aebcd
aecbd
aecdb
eabcd
eacbd
eacdb
with 3 weighings left, but this is as easily accomplished as in the 8 side of the split.

Posted by Charlie
on 20040531 10:56:46 