Another math puzzle

The answer to the first math puzzle will be posted in the comments there in another 24 hours, so get cracking.

Here’s a short puzzle from the theory of computation. You have 5 objects and a balance scale which allows you to compare their weights. How many weight comparisons do you need to sort them from heaviest to lightest? You must both find a procedure and prove that no better procedure exists (the measure is worst-case meaning the most comparisons you need if you are unlucky, rather than the average number of comparisons you need).

Hint: since there are only 10 pairs of objects (ab, ac, ad, ae, bc, bd, be, cd, ce, de) your answer had better be at most 10.

When I interviewed job candidates for mathematician/programmer jobs, I would give them this problem. There was also an extra credit problem: “find the best lower and upper bounds you can for the maximum number of comparisons needed to sort 100 objects”. It was quite impressive how well the extra credit problem distinguished between various levels of mathematical ability or experience (it couldn’t distinguish between ability and experience so well, but either one was good and doing badly meant they had neither). The dumbest non-insane answers were 50 for the lower bound (because everything has to get weighed at some point) and 10,000 for the upper bound (100×100 since 2 numbers specify a comparison), but there were about 4 different levels of progressively smarter answers.

(Added 11/10: see comments for the solution to the first part of the problem)


About Polymath

Discoverable with effort
This entry was posted in Uncategorized. Bookmark the permalink.

9 Responses to Another math puzzle

  1. Fortitudine Vincimus says:

    Guess: 8?

  2. No credit, since you gave neither a procedure for accomplishing it in 8 nor an argument that 7 isn’t enough.

  3. Jehu says:

    Hmm, I’m quite fatigued right now, but my guess is 7. There are 5! different arrangements of the weights possible, which is 120, which is nearest to 128 in powers of 2, or 7 bits of information. If we assume that we can garner one bit of information from each weighing, that’s 7 weighings required. As to a procedure to do this, I imagine we could do a quicksort-like approach, but I’m too tired right now to write one up.

  4. Jehu, very astute. Your lower bound is correct, but 120/128 is cutting it rather close. The fact that you have so little leeway restricts your choices, so with a little more work you should be able to either do it in 7 or prove that 8 are necessary.

  5. OK, here’s the solution to the first part. It can be done in 7 comparisons. Compare a with b, c with d, and (without loss of generality) assume a>b and c>d. Compare a with c (again WLOG assume a>c). Now we have used 3 comparisons and have this structure:

    c b

    Now use 2 comparisons to determine where e goes relative to the a-c-d chain: first compare e with c, if it is bigger compare it with a, otherwise compare it with d. Then use the last 2 comparisons to determine where b goes relative to the 3 lowest elements of the chain containing a,c,d,e (you know it can’t be on top of the whole 4-element chain because it is less than a).

    Note the binary splitting technique for inserting an element into a linearly ordered chain — compare with the middle element (or closest approximation to it), then compare with the middle element of the half you have now determined it belongs to, etc.

    Given this big hint, does anyone want to tackle the extra credit problem?

  6. OK, I see the class hates homework problems. I’m trying to show you math is fun, so here’s the next lowest level of answers to the extra credit problem:
    Lower bound is at least 99 comparisons because if you draw a line between each pair you compare, the whole structure had better be connected at the end or else you would never know which of two items unconnected to each other was heavier. If it is not obvious that you can’t connect 100 items with fewer than 99 lines, think about it.

    Upper bound is at most 4950 comparisons since that is how many distinct pairs of numbers there are from 1 to 100 (1-2, 1-3, 1-4, …, 99-100) — there are 100×100 = 10000 ordered pairs of numbers, subtract the 100 corresponding to comparing an object against itself to get 9900 and then divide by 2 because weighing 1 vs 2 is the same as weighing 2 vs 1.

    Can you do better?

  7. narciso says:

    ok, i’ll try… note: i have not taken a math class beyond what is taught in high school.

    minimum: 525
    because in a worst case scenario, after any comparison, half or more of the possibilities are still there.
    my reasoning: let’s say the current comparison is ‘a’ versus ‘b’; then half or less of the remaining possibilities will go one way (say a b). in the required worst case scenario we’d get the one with half or more possibilities intact (here that’s a > b).
    therefore, i figure that to get a lower bound we can just keep dividing in half, since that’s the “best of the worst” so to speak.
    there are, what, 100! ways to arrange all 100 of them; google says that is 9.33262154E157.
    if you keep dividing this in half, you need 525 such divisions to reach 1 unique possibility, since (again thanks mr. google) 2^525 is the biggest power of two that’s bigger than that godawful thing.

    maximum: 573
    if you are inserting a 2nd element into a “line” that only contains 1 element, then you only need 1 comparison.
    if you are inserting a 4th element into a line of 3 elements, you only need 2 comparisons: if you compare to the middle element first, then the next step is the same as inserting into a “line” of only 1 element.
    if you are inserting an 8th element into a line of 7 elements, you only need 3 comparisons, etc.
    generalizing this pattern (i think you could probably prove it with the “math induction” from my algebra 2 book … heh) you can insert up to the 2^N th element using N comparisons.
    um… so…
    1st element = 0 comparisons
    2nd element = 1 comparison
    3rd-4th elements = 2 comps each
    5th-8th = 3 comps each
    … blah blah
    … 65th-100th = 7 comps each
    that’s 1 + 2(2) + 4(3) + 8(4) + 16(5) + 32(6) + 36(7) = 573 = shitty upper bound
    i know this is shitty, because the same method gives 1 + 2(2) + 3 = 8 comps for five elements, which you already did with seven comps.

  8. narciso says:

    ok, i’ve just learned that one cannot type “less than” signs on wordpress. well, you should get the idea.

  9. Polymath says:

    Narciso, you get an A and would have gotten the job if you had come up with this in the interview. (The A is for not only reaching 573 but noticing that you can do better by using the “sort 5 in 7 comparisons” result from the original problem. An A+ would have been improving on the 525.)

    I wish you’d been around to try the poker and tennis problems before I posted the answers. Both of them involve one of my specialties, polynomial mathematics (another reason for my blog-name).

    I’ll post a new problem later today.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s