Juhan wants to order by weight five balls of pairwise different weight, using only a balance scale. First, he labels the balls with numbers 1 to 5 and creates a list of weighings, such that each element in the list is a pair of two balls. Then, for every pair in the list, he weighs the two balls against each other. Can Juhan sort the balls by weight, using a list with less than 10 pairs?
Problem
Source: Finalround Problem 2
Tags: combinatorics unsolved, combinatorics
Bugi
29.07.2008 22:53
Well, we take 3 balls and in 3 moves we can see ther sortings(e.g. A>B>C-the ball with the most weight is first). Then we take the last ball from those 3(C) and in 3 moves we compare that ball and remaining two(D and E). That's six moves(we can't have more than 3 moves more).WLOG D>E, and A>B>C
1) D>E>C
1. move: B v. D
If B>D then it' s over. If B<D then:
2. move: A and D
3. move B and E
2) D>C>E
In 3 moves we compare A,B and D
3) C>D>E
It's over(A>B>C>D>E)!
The weightings are moves for me(it's easier to write )
randomgraph
30.07.2008 00:10
Bugi - I believe the idea in this problem is to define a static list of "moves", that is a sequence of weighings that does not depend on the outcome of previous ones. This has to be like "compare A and B, then compare B and C, then A and D, ..." where in the end you're able to sort the five balls completely with the information collected in the process. The relevant term is Sorting Network, and the problem is asking for a network of 5 inputs with 9 comparators (see more info here). This is well known to be optimal (i.e. there is no way to sort 5 balls with just 8 weighings).