Author |
Topic: find one from 50 balls (Read 696 times) |
|
chetangarg
Newbie
Gender: 
Posts: 30
|
 |
find one from 50 balls
« on: Oct 18th, 2007, 12:37am » |
 Quote  Modify
|
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.
|
|
 IP Logged |
|
|
|
gotit
Uberpuzzler
Gender:
Posts: 804
|
|
Re: find one from 50 balls
« Reply #1 on: Oct 18th, 2007, 1:12am » |
Quote Modify
|
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.
|
|
IP Logged |
All signatures are false.
|
|
|
chetangarg
Newbie
Gender:
Posts: 30
|
|
Re: find one from 50 balls
« Reply #2 on: Oct 18th, 2007, 1:14am » |
Quote Modify
|
u r rite...
|
|
IP Logged |
|
|
|
gotit
Uberpuzzler
Gender:
Posts: 804
|
|
Re: find one from 50 balls
« Reply #3 on: Oct 18th, 2007, 1:21am » |
Quote Modify
|
Right about what? The answer or my thinking that you need a better solution.
|
|
IP Logged |
All signatures are false.
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: find one from 50 balls
« Reply #4 on: Oct 18th, 2007, 1:22am » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
chetangarg
Newbie
Gender:
Posts: 30
|
|
Re: find one from 50 balls
« Reply #5 on: Oct 18th, 2007, 1:22am » |
Quote Modify
|
obviously a better solution...
|
|
IP Logged |
|
|
|
chetangarg
Newbie
Gender:
Posts: 30
|
|
Re: find one from 50 balls
« Reply #6 on: Oct 18th, 2007, 1:25am » |
Quote Modify
|
on Oct 18th, 2007, 1:22am, Grimbal wrote:| I feel it is far from the actual minimum. |
|
I really don't know..
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: find one from 50 balls
« Reply #7 on: Oct 18th, 2007, 1:52am » |
Quote Modify
|
on Oct 18th, 2007, 1:22am, 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 log23 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 
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: find one from 50 balls
« Reply #8 on: Oct 18th, 2007, 2:45am » |
Quote Modify
|
on Oct 18th, 2007, 1:52am, towr wrote:| Two sets of balls having equal weight is very unlikely, so I doubt you can get an average log23 bits of information per weighing. |
|
Indeed! It is a theoretical bound I can prove... But in fact, even log250 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.
|
|
IP Logged |
|
|
|
chetangarg
Newbie
Gender:
Posts: 30
|
|
Re: find one from 50 balls
« Reply #9 on: Oct 21st, 2007, 6:10am » |
Quote Modify
|
Ain't there any way of reducing the solution from 49 
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: find one from 50 balls
« Reply #10 on: Oct 21st, 2007, 10:04am » |
Quote Modify
|
on Oct 21st, 2007, 6:10am, 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.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
RandomSam
Newbie
Gender:
Posts: 20
|
|
Re: find one from 50 balls
« Reply #11 on: Oct 26th, 2007, 3:42am » |
Quote Modify
|
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.
|
| « Last Edit: Oct 26th, 2007, 3:43am by RandomSam » |
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print