wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> medium >> Pan scales yet again
        
(Message started by: Margit on Nov 23^rd, 2006, 11:52pm)

Title: Pan scales yet again
Post by Margit on Nov 23^rd, 2006, 11:52pm

Using pan (balance) scales, we would like to sort objects (of differing weights) according to their weight. How many weighings do we need for :
a) 4 objects
b) 5 objects
c) 6 objects
d) n objects

Title: Re: Pan scales yet again
Post by towr on Nov 24^th, 2006, 1:49am

In the general case I'd go with [hide]merge sort[/hide]

Title: Re: Pan scales yet again
Post by jollytall on Nov 24^th, 2006, 10:24am

Something tells me that it might not necessarily be the best. In the mentioned algoritm you use only single values when the actual "measurment" is done. Here we have many more options, e.g. measure A+B vs. C+D. While in the sorting algoritm every step is mandatory, here we can make decisions on what to measure next depending on the result of earlier, combined meaurement(s).

But it not necessarily will give a better result.

Title: Re: Pan scales yet again
Post by Grimbal on Nov 25^th, 2006, 4:41am

The theoretical minimum is [hide] log2(n!) [/hide].

Title: Re: Pan scales yet again
Post by checker on Nov 25^th, 2006, 5:00am

The theoretical minimum is log2(n!) .
could you please tell me where did u get that (proving).For as far as I know we generally slove such problems by DECISION TREES....

Title: Re: Pan scales yet again
Post by rmsgrey on Nov 25^th, 2006, 5:46am

There are n! possible starting orders. The weighing process has to distinguish between each since each requires a different transformation to order the balls.

Each weighing can produce three different outcomes - left heavier, right heavier and balanced.

So a lower bound would be log₃(n!)

If you can show that "balanced" results are never helpful, then you can raise the lower bound to log₂(n!)

Title: Re: Pan scales yet again
Post by Grimbal on Nov 25^th, 2006, 4:40pm

In the worst case the weights are such that no combination of weights on the 2 pans do balance. So the minimum is log2(n!).

note: by "minimum" I mean that no method can guarantee to work with less than so many weights.

Title: Re: Pan scales yet again
Post by Barukh on Nov 26^th, 2006, 12:10am

The equivalent formulation of this problem known in theory of sorting is “Sorting with minimal number of comparisons”. The sequence A036604 (http://www.research.att.com/~njas/sequences/A036604) in Sloane’s database has the solution for n <= 13. Note that the last entry was proved only four years ago!

As far as I know, the best practical algorithm for this type of sorting is “merge insertion sort” (so after all, towr was close) discovered by Ford Jr. and Johnson back in 1959. A brief description of their algorithm may be found in chapter 2 of the following paper (http://www.mat.unb.br/~ayala/4FordJohnson.ps).

Title: Re: Pan scales yet again
Post by Margit on Nov 28^th, 2006, 12:47pm

How do you do it for 5 and 6?