Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Suppose that I have 5 balls with different weights. A scale tells me which one ball is heavier than another. I have to write down the the pairs of balls I use before I use the scale. Is it possible to write down at most nine pair of balls which tells me the order of balls weights?

I guess the answer is no as 4+3+2+1=10>9 but I have no proof.

share|improve this question
add comment

2 Answers

up vote 4 down vote accepted

As you point out, there are 10 pairs of balls. If we renumber the balls, any weighing of 9 pairs will omit one pair, so let us say we write down all the pairs except 4 vs 5. Any ordering of the weights that has 4 and 5 neighbors will be indistinguishable from the same ordering with 4 and 5 reversed. So you are right that if you have to specify the weighings in advance there are cases you cannot resolve with 9 weighings. You could tell 14253 from any other order, but could not tell 14523 from 15423.

share|improve this answer
    
+1 I wonder if you were allowed to specify the pairs after knowing the previous results... I think that even then, in the worst case, you would need 10 pairs –  leonbloy Aug 28 '12 at 20:02
    
@leonbloy: no, we could do with less. First weigh 1 vs 2 vs 3 (3 weighings) to get the order. Say it is 123. If we now weigh 4 vs 2, we will not need one of 4 vs 1 and 4 vs 3. Similarly for 5. So we can do it with 8 at most, but I have not proven 8 necessary. –  Ross Millikan Aug 28 '12 at 20:07
    
@RossMillikan Are you sure you can do it with 8? I'm seeing results that say that sorting 5 numbers requires 9 comparisons, and that would seem to be equivalent to this problem; e.g. en.wikipedia.org/wiki/Sorting_network#Optimal_sorting ... –  Steven Stadnicki Aug 28 '12 at 20:20
2  
@StevenStadnicki: the article you link to is a different problem from both the original and from my claim of 8. My claim of 8 is if you get to choose your comparisons as you go along, while a sorting network has to have the comparators selected in advance. You could see oeis.org/A001855 for the maximum comparisons by binary insertion, where it gives 8 for 5 items. –  Ross Millikan Aug 28 '12 at 20:29
    
@RossMillikan That's a good point - I'd missed that particular detail. At least in theory you might even be able to do 7 (since 120<128), but that seems unlikely. I'm sure TAOCP vol. 3 has something to say about this, but sadly my copy's at home right now. –  Steven Stadnicki Aug 28 '12 at 20:33
add comment

You must know the number of different pairs you can do with $5$ balls (the minimal number of checks) which is $$\frac{5!}{2!.(5-2)!}=10$$

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.