Fri 25 Jan 2008
Billiards Brainteaser
Posted by admin under Brainteaser
1 Comment
If you have 8 billiards balls, and one of them is heavier than the other 7 – given a balancing scale (where you compare the weight of something on one side of the scale to the other) what is the fewest number of times you need to weigh in order to find the heaviest ball?
I thought about this and came up with what I think is the right answer. I will post the answer tomorrow morning, Wednesday.
December 9th, 2009 at 2:39 am
Steven,
It turns out that after a moment’s thought it is possible to come up with an easy general solution to this problem (for any number of balls). Just round up the quotient of log[n] and log[3]. For example, the minimum number of measurements for 8 balls is ceil(log(8)/log(3)) = 2, using Matlab syntax. The proof lies in the fact that one can always with certainty eliminate in one round 2/3 of the total remaining balls, so you can always reduce your total number of balls to 1/3 or less in any round. Thus the solution for x of n*(1/3)^x <= 1 is the number of rounds required. That solution is, of course, x = ceil(log(n)/log(3)).