Tim West

Ranch Hand

Posts: 539

posted 13 years ago

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

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

Ranch Hand

Posts: 815

posted 13 years ago

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.

I've heard it takes forever to grow a woman from the ground

Tim West

Ranch Hand

Posts: 539

Nick George

Ranch Hand

Posts: 815

posted 13 years ago

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 ]

Good one, Tim!

[ May 17, 2004: Message edited by: Joseph George ]

I've heard it takes forever to grow a woman from the ground

Tim West

Ranch Hand

Posts: 539

posted 13 years ago

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

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

Greenhorn

Posts: 27

Tim West

Ranch Hand

Posts: 539

Nick George

Ranch Hand

Posts: 815

posted 13 years ago

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.

I've heard it takes forever to grow a woman from the ground

Tim West

Ranch Hand

Posts: 539

posted 13 years ago

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

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

It is sorta covered in the JavaRanch Style Guide. |