Just 9 items

Logic Level 4

You are given a balance scale without measurements, which can determine the order of increasing distinct weights in just one weighing. However, if we have 3 objects, then we will need 3 weighings to determine the relative order of their weights.

Now suppose you have been asked to rank 9 given objects in order of increasing weights, what is the minimum number of weighing needed to guarantee that we can perform this task?

The answer is 19.

2 solutions

Ivan Koswara
Jun 7, 2015

[This is not a (complete) solution either]

We need to distinguish $9!$ cases. By giving a small perturbations for the weights (for example add $2^i \epsilon$ to weight $i$ for small enough $\epsilon$ ), we will never get any two balanced comparisons (even if we compare multiple weights versus multiple weights), so each comparison only gives $1$ bit of information. This means we need at least $\log_2 9! \approx 18.47$ comparisons, or in other words $\boxed{19}$ comparisons. We still need to find out whether this is achievable, however.

This problem doesn't fall under the realm of "logic", more like "algorithmic trivia and/or guesswork." The above lower bound gives just that -- a lower bound -- and not a proof that it is possible in that. The proof is the existence of an algorithm that will do it in 19, and the algorithm is not something that anyone could be expected to produce without already knowing it. It's not something you can discover by logic.

Brian McSwiggen - 4 years, 10 months ago

Right, the lower bound of 19 is the "easy" part. It is not obvious how to construct the algorithm though.

Calvin Lin Staff - 6 years ago

Do you have the algorithm?

Agnishom Chattopadhyay - 6 years ago

This is from Wikipedia :

Determining the exact number of comparisons needed to sort a given number of entries is a computationally hard problem even for small n, and no simple formula for the solution is known. For some of the few concrete values that have been computed, see OEIS A036604.

The Wiki link is here . In response to your question, no one knows the algorithm.

Venkata Karthik Bandaru - 6 years ago

Can you explain how 19

Aman Gupta - 5 years, 3 months ago

My calculation seems to have coincided with the solution given. Does this solution require that the weights be distinct and/or that the sum of the weights of elements of nonempty sets be distinct, or does that simply result in an increase in the amount of information that can be obtained from weighings? (i.e., each weighing between disjoint sets A and B can have weights where A > B, A < B, or A = B)

Shawn Franchi - 5 years, 1 month ago

Can you please post the algorithm gauranteeing the sort in 19 moves, whatever be the initial case.

prasun bansal - 4 years, 11 months ago

The text might should be changed. It says what is the minimum number of weighing needed to rank 9 objects and there's a chance this can be done in 11 weighing. If you sort the 9 objects in 3 groups of 3 (and by chance they are all correlative in the ranking), and then, after a couple of lucky comparisons between lightest and heaviest elements of the three groups you can be sure you ranked right all 9 elements in just 11 weighing.

It would be sweet to calculate how improbable this would be, although it's still possible

Nilo Carron - 5 years, 4 months ago

Whenever it's about "find the minimum needed to X", it's always implicit that we want to guarantee doing X. Let me make that explicit. Thanks.

Calvin Lin Staff - 5 years, 4 months ago

The best I got is 21. By using something like Merge-Sort: get 2+2+2+2+1 ranked objects in 4 comparisons. Then join 2+2 in 3, 2+1 in 2, and the last 2 with 3 in 4 comparisons - we get 4+5 ranked weights in 9 comparisons. And those can be "joined" to get all 9 ranked in 8 more comparisons. So we have 4+9+8=21. But like you said, even though theoretical minimum is less, it's not that easy to get that...

Dejan Tomić - 5 years, 4 months ago

this is the good answer 21.

Mr X - 4 years, 7 months ago

@Calvin Lin @Ivan Koswara I think the optimal algorithm is this

Agnishom Chattopadhyay - 4 years, 11 months ago

Link doesn't appear to work

Charles Gaskell - 2 years, 11 months ago

The Ford-Johnson algorithm: https://github.com/decidedlyso/merge-insertion-sort/blob/master/README.md

Ron van den Burg - 3 years, 1 month ago

Agnishom Chattopadhyay
Jun 7, 2015

[This is not a solution]

See http://oeis.org/A036604

This only true if you are lucky to pick the biggest weight. The real answer is 18 to be absolutely sure. Weigh A-B, C-D, A-C, A-D, B-C, B-D giving A<B<C<D (6 weighs) When A<B + A<C + A<D + B>A + B<C + B<D C<D = ABCD

E-F, G-H, F-G, E-H, E-G, F-H giving E<F<G<H (6 weighs) As previously we have =EFGH A-E, D-E, (highest and lowest value) So we know now A<B<C<D<E<F<G<H (2 weights) J-D if J<D then J-F IF J<F if not we know a-b-c-d-j-e-f-g-h. J-G with the same reasoning as before. J-H giving the result.

Colin Lincoln - 4 years ago

(17). Letter A,B,C,D,E,F,G,H,I The order of lettering is not a factor. Complete 4 initial weighing pairs, leaving one to the side, say E. A>F, B>G, C>H, D>I; separate into two groups, heavier-lighter. (4) A,B,C,D and F,G,H,I Recompare: A>B, C>D; F>G, H>I. (4) Recompare: A>C, B>D; F>H, G>I; If A>B and B>D then A>D, applies to all comparisons. (4) By logic this leaves two left over. Recompare: B>C, G>H. (2) Compare: E to D, if E>D then E to A, if A>E, then E to B, If B>E, then B>E>D, (3) or If D>E, (1) then E to G, if E>G then E to F If F>E, (2) or if G>E, (1) then E to H, if E>H, (1) finished, or if H>E then E to I, I>E, (2)

Follow the logic path of all the comparisons, 17 comparisons

matt maxwell - 3 years, 9 months ago

Just 9 items

The answer is 19.

2 solutions

0 pending reports