Given 8 balls, each weighing exactly the same except one (which we'll assume is heavier), and a scale, what is the least number of times you must use the scale to find the heavy ball?
The approach most frequently thought of is to split the 8 balls into 2 pairs 4 balls and place those on the scale. Then, go to the side that turns out heavier, and split those 4 balls into 2 pairs of 2 balls and place those on the scale. When one side turns out heavier, weigh those final 2 balls and you'll find the heavy ball.
But as anyone who has ever heard a riddle in his life would know, the most obvious answer is rarely the correct one. You can actually find the heavy ball using the scale only twice. To do this, you must set to balls aside, and weigh the final 6 with 3 on each side of the scale. If they balance, you know the heavy ball is among the final two and you need only weigh those. If they don't, you need only weigh 2 of the final 3, because, if those two balance, we know the heavy one is the final, unweighed ball, if they don't, the heavy ball would obviously be the heavier one of the two.
Pretty simple, yes? But then the question arises. What if you were given 9 balls? Or 20? 81 balls? What will the minimum usage of the scale be then? We worked on this for a bit, and got a table showing the least number of times required to find the heavy ball out of n balls. It started off like
1: 0*
2: 1
3: 1
4: 2
5: 2
6: 2
7: 2
8: 2
9: 2
10: 3
* If you have just one ball, you don't have to weigh anything to figure out it's the heavy ball.
Side Note:
Our table was actually a little bit more expressive. This is because of the fact that, in each case, you have the probability of finding the heavy ball on your first try, your second try, and so on, depending on how you weigh the balls. For example, given 4 balls, you could weigh 2 on each side, and weigh the heavier 2 again, giving you 0 chance of finding it on your first try. Or you could 1 on each side, and only weigh the remaining two if these balance out. But, if they don't balance out, then you'd have found the heavy ball in your first attempt. This post ignores that, as I haven't been able to find anything interesting when including these probabilities. That could be something for a later time.
Do you happen to see a pattern? For 1 ball it takes 0 weighings. For 2-3 balls it takes 1. For 4 - 9 balls it takes 2. Now, it turns out that for 10 - 27 balls it takes 3. I'm sure you've seen it by now. It is indeed a logarithmic growth rate, but of base 3, and not 2. The reason for this? Why, it's simple. While deciding how to weigh the balls one must consider both how many to place on each scale and how many to ignore. The naive method of simply splitting the balls in half and repeating completely disregards the information that can be gained from simply placing to the side a number of balls.
I won't bother at a formal proof that this is the least number of weighings needed to find the heavy ball. (If you don't believe me, you can try to find a more efficient way yourself). I will however, describe a simple method that can be used to find the proper way to weigh a set of "n" balls. You must keep in mind only two things. The number of balls you put on each scale and the number of balls you place aside. Each of these numbers must be less than the greatest power of 3 less than n. (the previous power of three to n.). As long as these criteria are met, you will weigh the balls most efficiently. For example, if given 100 balls, I'm allowed to put up to 81 on each scale (of course, the restraints of the number limit me to putting 50 on each scale), but I also must make sure not to put more than 81 aside. (Technically, I can only put 80 aside. If I put 81 aside, I'm left with 19 balls which I can't divide evenly among the scale).
Well, that's it for today. Hope you found it interesting.
