Weighing balls discussion

This puzzle is described here and the solution is given here.

The first technique to think about is how you split up the balls to weigh them. A common technique is binary splitting. This means that you split a set into two, discard one half, then split the other into two, again discard half, and so on. This enables you to narrow in on a single item very quickly. Here we can be even more efficient. If we divide the balls into three rather than two, and weigh one set against another while ignoring the third, we can not only say something about the eight balls being weighed, we can also say something about the four that are not being weighed. If we knew at the start whether the odd ball is heavy or light, then the first weighing, a third of the total against a different third, would immediately narrow the balls down to a third. In fact, we could start with 27 balls, knowing one ball to be light, for example, and in three weighings, we could isolate the light ball. But it's not that easy when you don't know whether the odd ball is light or heavy!

When doing a weighing, there are three possible answers, first set is lighter than second, first set is heavier than second, both sets equal. With three weighings, there are 27 different results, as long as you make sure that each weighing gives you the maximum possible information, and you are not losing information by, in some way, repeating part of a weighing where you already know the answer. There are 24 possible solutions to the problem, first ball heavier, first ball lighter, second ball heavier, etc. So since the weighings have more possible results than the solutions do, the situation is not impossible! However, all these possible answers need to be thought about. They are listed below.

First weighing: ball 1, 2, 3, 4 against ball 5, 6, 7, 8

If these are equal, then the odd ball is either 9, 10, 11 or 12. This means that all the balls 1-8 are OK, and if you want, you can use them to weigh against the others to check that they are OK or not. So the second weighing weighs three of the OK balls, say ball 1, 2, 3, against three of the odd ball set, say ball 9, 10, 11. If these are equal, then the only ball left is ball 12, and this must be the odd one. Weigh it (third weighing) against any OK ball to see if it is heavier or lighter.

If ball 1, 2, 3, 4 are equal to ball 5, 6, 7, 8, but at the second weighing, ball 1, 2, 3 is not equal to ball 9, 10, 11, then we know that the odd ball is either 9, 10 or 11, and what's more, we know whether this ball is heavier or lighter (from the result of the second weighing). Let's say that it is heavier. Now we can weigh ball 9 against ball 10 (third weighing). If ball 9 is heavier, then that's the odd ball. If ball 10 is heavier, then that's the odd ball. If they are equal, then the remaining ball, 11, is the odd one, and we already know that it's heavier. Exactly the same logic apples if set 9, 10, 11 are lighter.

Now to explore what happens if ball 1, 2, 3, 4 are not equal to ball 5, 6, 7, 8. Let's assume that ball 1, 2, 3, 4 are heavier. We still don't know whether the odd ball is heavier or lighter, so we don't know whether the odd ball is in balls 1-4 or 5-8. Never mind! Second weighing: weigh two of the heavier balls and one of the lighter balls against the remaining two heavier balls, and another of the lighter balls, say ball 1, 2, 5 aginst ball 3, 4, 6 (second weighing). If these are equal, the the odd ball is either 7 or 8 and we know that it is light (as both 7 and 8 belonged to the light set). So weigh them against each other (third weighing), and the lighter will be the odd ball.

But what if ball 1, 2, 5 is not equal to ball 3, 4, 6? This was the second weighing, and we only have one weighing left, and we still don't know if the odd ball is heavier or lighter. Don't worry! Let's assume that ball 1, 2, 5 is heavier than ball 3, 4, 6. Remember that we know that balls 1-4 are heavier than balls 5-8. So either ball 1 or 2 is the odd one out, and it's heavier, or ball 6 is the odd one out, and it's lighter. We can work out which by weighing ball 1 against ball 2 (third weighing). If ball 1 is not equal to ball 2, then the heavier one is the odd one out. If they are equal, then the odd one out must be ball 6, and it's lighter.

I have made various assumptions about a group being heavier or lighter, but the reverse assumptions will be processed in the same way. The above discussion shows the different techniques that you use to find the odd ball. Click here for an interactive demonstration for a particular odd ball. You can try it again and again for any choice of odd ball.

This is quite a concentrated piece of thinking, but no special knowledge is required. You need to take each step carefully, and evaluate all possible outcomes, which gets quite complicated! The first weighing (which splits the balls into three and weighs the first set against the second) means that you get the maximum amount of information at that stage. Some of the subsequent stages are easier to cope with, but some of tricky. You need to remember all previous infromation that you have found out. You also need to think about the last weighing. If you have only one more weighing, and you have too many balls to evaluate, then you cannot do it. So don't weigh too few balls at the second stage, or if they are equal, then you will have too many left to cope with. On the other hand, if you weigh too many at the second stage, and they are unequal, again there will be too many to sort out.