A set of five coins are of differing weights, no two are equal.

Devise a method to sort the coins by weight using only a balance scale, subject to the restriction that only one coin may be placed on each side in each weighing.

Can this be done in the theoretical minimum of 7 weighings?

I was surprised to find that 7 weighings is achievable.
I tried to make sure to split the possible orderings as evenly as possible at each step.  The 4th weighing was the crucial step as 15 had to be split into 7 and 8.

label the coins A, B, C, D, E (5!=120 possible orders)
1st weighing: AvsB
(120/2=60 possible orders)
2nd weighing CvsD
(60/2=30 possible orders)
3rd weighing BvsD
(30/2=15 possible orders)
No symmetries have been broken at this point so we may assume
A<B<D and C<D.  The possible orders are
ABCD
ACBD
CABD
times 5 possibilities for E.
4th weighing BvsE (the lighter of the 3rd weighing)

CASE 1, on the 4th weighing B<E
(7 possible orders)
ABECD
ABCED
ABCDE*
ACBED
ACBDE*
CABED
CABDE*
The 3 cases marked with a * can be separated from the 4 without by 5th weighing DvsE.
If D<E the final two weighings are simple and have a few choices.
IF E<D the 6th weighing is BvsC and the 7th will be obvious.

CASE 2, on the 4th weighing E<B
(8 possible orders)
EABCD*
AEBCD
EACBD*
AECBD
ACEBD
ECABD*
CEABD*
CAEBD
The 4 cases marked with a * can be separated from the 4 without by 5th weighing EvsA
If E<A the 6th weighing is AvsC and the 7th will be obvious.
If A<E the 6th weighing is CvsE and the 7th will be obvious.

Posted by Jer on 2016-07-14 13:47:58