Author |
Topic: Pan scales yet again (Read 442 times) |
|
Margit
Junior Member
Gender: 
Posts: 54
|
 |
Pan scales yet again
« on: Nov 23rd, 2006, 11:52pm » |
 Quote  Modify
|
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
|
|
 IP Logged |
|
|
|
jollytall
Senior Riddler
Gender: 
Posts: 585
|
|
Re: Pan scales yet again
« Reply #2 on: Nov 24th, 2006, 10:24am » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Pan scales yet again
« Reply #3 on: Nov 25th, 2006, 4:41am » |
Quote Modify
|
The theoretical minimum is log2(n!) .
|
|
IP Logged |
|
|
|
checker
Newbie
Posts: 44
|
|
Re: Pan scales yet again
« Reply #4 on: Nov 25th, 2006, 5:00am » |
Quote Modify
|
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....
|
|
IP Logged |
|
|
|
rmsgrey
Uberpuzzler
    
Gender:
Posts: 2874
|
|
Re: Pan scales yet again
« Reply #5 on: Nov 25th, 2006, 5:46am » |
Quote Modify
|
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 log3(n!)
If you can show that "balanced" results are never helpful, then you can raise the lower bound to log2(n!)
|
|
IP Logged |
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Pan scales yet again
« Reply #6 on: Nov 25th, 2006, 4:40pm » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: Pan scales yet again
« Reply #7 on: Nov 26th, 2006, 12:10am » |
Quote Modify
|
The equivalent formulation of this problem known in theory of sorting is “Sorting with minimal number of comparisons”. The sequence 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.
|
|
IP Logged |
|
|
|
Margit
Junior Member
Gender:
Posts: 54
|
|
Re: Pan scales yet again
« Reply #8 on: Nov 28th, 2006, 12:47pm » |
Quote Modify
|
How do you do it for 5 and 6?
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print