• Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Jeanne Boyarsky
  • Ron McLeod
  • Paul Clapham
  • Liutauras Vilda
Sheriffs:
  • paul wheaton
  • Rob Spoor
  • Devaka Cooray
Saloon Keepers:
  • Stephan van Hulst
  • Tim Holloway
  • Carey Brown
  • Frits Walraven
  • Tim Moores
Bartenders:
  • Mikalai Zaikin

Scales

 
Ranch Hand
Posts: 539
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
You have balls, one of which is gold; the rest are brass. They all look identical.

The only way you have to tell them apart is to use some balancing scales. Of course, the gold ball is heavier than the others. The others all have an identical weight.

What is the smallest number of measurements you can do to be deterministically sure which ball is gold? How can you do it?

(Of course, when you pick the balls up to put them on the scales, you don't notice a weight difference. The only tool at your disposal is the scales.)


-Tim
 
Ranch Hand
Posts: 815
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
as a 10-second, first impression guess without giving it any real thought, I'd say log base 2 of the number of balls. Put half on one side, half on the other. take the heavier side, and repeat. Best, worst, and average times of log base 2.
 
Tim West
Ranch Hand
Posts: 539
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Well log_2 (9) is between 3 and 4. You can do better than this ;-)


-Tim
 
Nick George
Ranch Hand
Posts: 815
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Upon further consideration, I say log_3. Divide the balls into 3 groups, two of which are equal, and a third of which is as close to being equal as is possible, (i.e. for 10, do 3,3,4). Put the two equal piles on the scales. The heavier one has the gold ball. if neither is heavier, the third pile has the gold. Repeat.

Good one, Tim!
[ May 17, 2004: Message edited by: Joseph George ]
 
Tim West
Ranch Hand
Posts: 539
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Well done So 2 measurements for 9 balls...if anyone can beat that I'll be impressed

I guess strictly speaking, it's only log_3 x if x is a power of 3. Otherwise, it's the ceiling of log_3 x (that is, the smallest integer greater than log_3 x. This accounts for that fact that with 10 balls for example, it could take 3 measurements if the gold ball is in the final pile of four.

How convenient that the original problem used a power of 3, eh?

--Tim
 
Greenhorn
Posts: 27
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
for 9 balls, best result can be achieved in 1 measurement. put 4 balls in each scale. if they come out equal, remaining ball is of gold. ofcourse, if the 4 balls don't weigh equal, it will take total 3 measurings to find out gold ball.
 
Tim West
Ranch Hand
Posts: 539
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
I thought of that...that's why the original answer says deterministically determine the gold ball. That algorithm isn't deterministic


--Tim
 
Nick George
Ranch Hand
Posts: 815
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Here's the interesting question: Is there any proof that log_3 is the best way? or do we just have to say "Oh yeah? find a better one?" I shall now include a completely gratuitus smiley to test the new thing.
 
Tim West
Ranch Hand
Posts: 539
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Ugh, the burden of proof...

Actually I think this proof would be pretty simple. At any weighing, you can divide set of balls (B) into three disjoint subsets: those on one half of the scales (set S1), those on the other half (set S2), and those that aren't weighed (set W). Now, we must have

|S1| = |S2| (ie, same cardinality)

or the weighing doesn't help us, and if it doesn't help us it can't contribute to the minimum number of weighings. (A bit hand-wavey there, but it makes sense to me, at least...).

Now, in this situation we can always determine which group of 3 the gold ball is in.

Thus we reduce the problem to showing that the "ideal" condition is when |S1| is very very close to |W|, or more precisely, you can't do better than:

if |B| % 3 == 0, |S1| = |W|
if |B| % 3 == 1, |S1| = |W| - 1
if |B| % 3 == 2, |S1| = |W| + 1

Because in this condition we divide by 3 in each iteration, so it's gonna terminate in log_3 time. (Yeah OK need more proof there).

OK, so from here, break it into the 3 conditions. Eg for the first condition:

suppose you split it up so |S1| != |W|. Then, either |S1| > |W|, or |S1| < |W|. In the former case, if it turns out the gold ball is in S1, you can't do it in log_3 measurements, in the latter, if the ball is in W, you can't.

Hmm...I think that's sorta a back-of-envelope start...?

*stops waving hands*


--Tim
 
They worship nothing. They say it's because nothing is worth fighting for. Like this tiny ad:
a bit of art, as a gift, the permaculture playing cards
https://gardener-gift.com
reply
    Bookmark Topic Watch Topic
  • New Topic