Win a copy of Five Lines of Code this week in the OO, Patterns, UML and Refactoring forum!
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 all forums
this forum made possible by our volunteer staff, including ...
Marshals:
• Campbell Ritchie
• Bear Bibeault
• Ron McLeod
• Jeanne Boyarsky
• Paul Clapham
Sheriffs:
• Tim Cooke
• Liutauras Vilda
• Junilu Lacar
Saloon Keepers:
• Tim Moores
• Stephan van Hulst
• Tim Holloway
• fred rosenberger
• salvin francis
Bartenders:
• Piet Souris
• Frits Walraven
• Carey Brown

# Scales

Ranch Hand
Posts: 539
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
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
Well log_2 (9) is between 3 and 4. You can do better than this ;-)

-Tim

Nick George
Ranch Hand
Posts: 815
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
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
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
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
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
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

 Consider Paul's rocket mass heater.