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 7-8 split, with the latter number being the extreme that another 3 weighings would handle.

The only way to get a 7-8 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 4-4 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 2-2. 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 7-8 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 2004-05-31 10:56:46