posted 21 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