Scales

[Tim West]

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

[Nick George]

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]

Well log_2 (9) is between 3 and 4. You can do better than this ;-)


-Tim

[Nick George]

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]

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

[C Chavan]

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]

I thought of that...that's why the original answer says deterministically determine the gold ball. That algorithm isn't deterministic


--Tim

[Nick George]

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]

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