5

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.

mathboy
  • 53

2 Answers2

4

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.

Ross Millikan
  • 374,822
  • +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. http://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 http://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
0

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$$

dot dot
  • 1,582
  • 1
  • 12
  • 22