Behold the solution to Planet of the Puzzle Apes #6. If you have forgotten the question, click here to see it again.

The answer cannot be less than seven. There are 5! = 120 ways to arrange the coins. Now, each weighing will give you one piece of information: if the left side is heavier we are in ONE case, and if the right side is then we are in a DIFFERENT case. So with each weighing we are dividing the universe of remaining possibilities into two groups. Therefore, one weighing could distinguish between at most 2 possibilities, two weighings could distinguish between at most four, etc. Therefore six weighings could only give you enough information to distinguish between 64 different possibilities, and is therefore not enough. We need at least seven.

But can we figure out a way to sort them with seven weighings? In other words, can our theoretical mininum be acheived? I did not require such an algorithm to be written out for credit, but I thought you would like to see it. The following algorithm is due to Captain Recursion - Doctor E's friend at Northern Michigan University:

Compare the first two coins. Name the lighter one A and the heavier one B. (one weighing has taken place)
Compare the two different coins. Name the lighter one C and the heavier one D. (two weighings have taken place)
Name the remaining coin E.

Now compare the lighter coins, A and C. (three weighings have taken place). To save space, we will assume that A was the lightest. If not, that is another case which works exactly the same, changing the labels A with C and B with D. So, assuming that A was the lighter of A and C...

So far we have A< C< D, and A< B.

We next want to put E into its proper place in the (A,C,D) list. This will take 2 weighings. Compare E with C, and then compare E with either A or D
depending on how the comparison with C went. We are now at five weighings. We only have two more!

All that remains is to put B into its proper place. We already know A < B.

CASE 1: E < A. We put B in its proper place in the (C, D) list and we are done. (six weighings total)
CASE 2: E > A. We put B in its proper place in the (C, D, E) list (compare B with D and then compare B with either C or E depending on how the comparison with D went) and we are done (seven weighings total)

This problem is actually very interesting and important in the field of computer science. The following comment comes directly from Captain Recursion:

It is not too hard to figure out how to sort the coins with 8 weighings. Doing it with 7 is much harder to see. In the 1950's, this was still an unsolved problem: they knew it couldn't be done with 6, and they knew it could be done with 8, but could it be done with 7? In 1959, Ford and Johnson developed the Merge Insertion sort algorithm which sorts 5 elements with only 7 comparisons. (It uses the exact strategy I described to Dr. E!) In fact, this algorithm was developed by first figuring out how to sort 5 elements and then expanding these ideas to sort larger amounts of elements.

The Merge Insertion sort will sort up to 12 elements with the smallest possible number of comparisons (sorting 12 requires a minimum of 30 comparisons). Then after that it isn't perfect anymore, but it is still the best known method. There is no known formula for the minimum number of comparisons needed to sort any number of elements. For small numbers of elements, we know the minimum number from computer trial-and-error experimentation, but for larger numbers of elements, beyond the power of modern computing, we still do not know the minimum number of comparisions required!

Nobody got them all, so weep not.

The deadline for sending in solutions has expired. But feel free to take some time to work on this one, and click here to see the answer. Alternatively, click here to see the current challenge.

Web Page design: Doug Shaw