wu :: forums - Print Page


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

        riddles >> medium >> find one from 50 balls
        
(Message started by: chetangarg on Oct 18^th, 2007, 12:37am)

Title: find one from 50 balls
Post by chetangarg on Oct 18^th, 2007, 12:37am

There are 50 (1gm, 2gm,3gm..........50gm) identical by shape balls. you pick a ball at random and you have to find out the ball's weigh with the help of a weighing pan and these balls , the weighing pan will only tell you the heavier and lighter (or equal ) side from the two pans not the difference of weight of two sides. In how many minimum weighing u can tell the ball's weight.

Title: Re: find one from 50 balls
Post by gotit on Oct 18^th, 2007, 1:12am

One simple and obvious solution is to weigh the ball with all the other balls and keep track of the number of balls that weigh less than it. If n is the number of balls weighing less than it, then the balls weight will be n+1. But this requires 49 weighings to be done. I suppose you are looking for an answer that requires less weighing.

Title: Re: find one from 50 balls
Post by chetangarg on Oct 18^th, 2007, 1:14am

u r rite...

Title: Re: find one from 50 balls
Post by gotit on Oct 18^th, 2007, 1:21am

Right about what? The answer or my thinking that you need a better solution.

Title: Re: find one from 50 balls
Post by Grimbal on Oct 18^th, 2007, 1:22am

Interesting question.

For a starter, an upper bound would be 49 by the trivial method of comparing the ball with all others. I'd say that would be the minimum if you didn't know the weights of the balls. But for time being, I don't see an effective way to use the actual ball weights.
A theoretical lower bound would be given by log(50)/log(3) = 3.56 which puts the minimum at 4. I feel it is far from the actual minimum.

Title: Re: find one from 50 balls
Post by chetangarg on Oct 18^th, 2007, 1:22am

obviously a better solution...

Title: Re: find one from 50 balls
Post by chetangarg on Oct 18^th, 2007, 1:25am

on 10/18/07 at 01:22:47, Grimbal wrote:

I feel it is far from the actual minimum.

I really don't know..

Title: Re: find one from 50 balls
Post by towr on Oct 18^th, 2007, 1:52am

on 10/18/07 at 01:22:47, Grimbal wrote:

A theoretical lower bound would be given by log(50)/log(3) = 3.56 which puts the minimum at 4. I feel it is far from the actual minimum.

Two sets of balls having equal weight is very unlikely, so I doubt you can get an average log₂3 bits of information per weighing.

Perhaps we should tackle the problem for smaller numbers of balls first, because 50 is a bit much to use brute force analysis :P

Title: Re: find one from 50 balls
Post by Grimbal on Oct 18^th, 2007, 2:45am

on 10/18/07 at 01:52:21, towr wrote:

Two sets of balls having equal weight is very unlikely, so I doubt you can get an average log₂3 bits of information per weighing.

Indeed! It is a theoretical bound I can prove... But in fact, even log₂50 would be difficult to achieve due to the uncertainty on which ball is which. You are bound to get some information about the other ball's weights.

Title: Re: find one from 50 balls
Post by chetangarg on Oct 21^st, 2007, 6:10am

Ain't there any way of reducing the solution from 49 ???

Title: Re: find one from 50 balls
Post by towr on Oct 21^st, 2007, 10:04am

on 10/21/07 at 06:10:46, chetangarg wrote:

Ain't there any way of reducing the solution from 49 ???

Probably; but it isn't as yet obvious how.
It seems to be a good puzzle; it puzzles us to no end.

Title: Re: find one from 50 balls
Post by RandomSam on Oct 26^th, 2007, 3:42am

I must agree, I've no idea where to start with 50 balls! Here are my thoughts with small numbers:

0, 1, 2 balls: trivial.
3 balls of mass 1kg, 2kg, 3kg: definitely no solution with an expected number of comparisons less than 2.
3 balls of mass 1kg, 0kg, -1kg: solvable in 1 comparison.
4 balls: I ran out of paper while comparing the possibilities. I haven't yet found a solution using less than 3 comparisons on average.

If I could guess the weight of each ball by holding it in my hand, but needed to prove I was right using as few comparisons as possible, then there could be some short cuts of order log(n) along the lines of:
1+2<4, 1+2+4<8, 1+2+4+8<16... etc.