Mathematical Spectrum, v 29 (1996/7), No 1, pp 14-15

The Oddball Problem

BRIAN D. BUNDY

This problem has appeared in several collections of mathematical brain-teasers and from time to time gets resurrected to challenge yet another generation of puzzlers. The problem can be stated as follows. We arc given twelve balls, identical in appearance but one of which is either heavier or lighter than the other eleven. We are allowed three weighings with a balance, to determine which is the odd ball and to find whether this ball is heavier or lighter than the others. What do we do?

We can suppose that we can, if it has not already been done, label the balls 1, 2, 3,..., 10, 11, 12 so that we can distinguish between and identify them using these labels. The solution usually given runs along the following lines. Weigh 1, 2, 3, 4 against 5, 6, 7, 8

1. They balance, so 9, 10, 11, 12 contain the odd ball. Weigh 6, 7, 8 against 9, 10, 11.

   1. They balance, therefore 12 is the odd ball and so weigh 12 against any other to discover whether it is heavy or light.

   2. 9, 10, 11 are heavy and so they contain an odd heavy ball. Weigh 9 against 10. If they balance, 11 is the odd heavy ball, otherwise the heavier of 9 and 10 is the odd ball.

   3. If 9, 10, 11 are light, we use the same procedure to reach the same conclusion for the odd light ball.

2. 5, 6, 7, 8 are heavy and so either they contain an odd heavy ball or 1, 2, 3, 4 contain an odd light ball. Weigh 1, 2, 5 against 3, 6, 10.

   1. They balance, so the odd ball is 4 (light) or 7 or 8 (heavy). Thus weigh 7 against 8. If they balance 4 is light, otherwise the heavier of 7 and 8 is the odd heavy ball.

   2. 3, 6, 10 are heavy, so the odd ball can be 6 (heavy) or 1 or 2 (light). Thus weigh 1 against 2. If they balance 6 is heavy, otherwise the lighter of 1 and 2 is the odd light ball.

   3. 3, 6, 10 are light, so the odd ball is 3 and light or 5 and heavy. We thus weigh 3 against 10. If they balance 5 is heavy, otherwise 3 is light.

3. If 5, 6, 7, 8 are light we use a similar procedure to that in 2.

This solution, which requires different courses of action depending on the outcomes of previous weighings, is not particularly elegant or easy to remember. We shall give a solution which involves a fixed course of action in all circumstances and which has the advantage of showing how this particular problem can be generalised.

In our method we weigh four specified balls against four other specified balls in each of the three weighings and note the result. If we observe say the left-hand side of the balance, then for an individual weighing there are three possible alternatives: the left-hand side is heavy (H), light (L) or equal (E) as compared with the right-hand side of the balance.

Since three weighings are allowed, the number of different results that can be obtained is just the number of arrangements (with repetitions allowed) of the three symbols H, L, E, i.e. 3³ = 27. If we use all twelve balls in the three weighings, and ensure that no particular ball appears on the same side of the balance in all three weighings, the outcomes HHH, LLL, EEE are not possible. We thus have only 24 possible outcomes and we shall show that it is possible to set up a one-one correspondence between these 24 outcomes and the conclusion that a particular ball among the twelve is heavy or light.

The 24 outcomes can be divided into two groups of twelve in each group. If we call the reverse of an outcome the outcome obtained by replacing H by L, L by H and leaving E unchanged, one group of twelve will be the reverses of the other group and vice versa. We can thus write the 24 outcomes in the form of two arrays, each array having three rows (the three weighings) and twelve columns (the twelve balls), so that each row contains four Hs, four Ls and four Es. Thus we have, for example,

We consider just the top array, and for each weighing (row) place the balls corresponding to an H in the left, and the balls corresponding to an L in the right of the balance. Thus we would weigh 1, 2, 3, 4 against 5, 6, 7, 8; then 7, 8, 9, 11 against 1, 5, 6, 10; and finally 2, 5, 8, 9 against 3, 7, 11, 12. The results of these three weighings as observed on the left of the balance are noted. If the outcome is H, L, E we conclude that ball 1 is heavy; if H, E, H ball 12 is heavy, etc; if E, E, L ball 12 is heavy. If we obtain an outcome that appears in the lower array, we conclude that the corresponding ball is light. Thus for L, H, E ball 1 is light, etc; E, E, H means ball 12 is light.

This method of solution allows us to see how the problem can be generalised. If two weighings are permitted we would have 3² - 3 = 6 different outcomes. These can be split into two groups of three, the one group being the reverses of the other. Thus with two weighings, weighing one ball against one other ball at each weighing allows us to find the odd ball among three. The arrays are

Thus weigh 1 against 2 and then 2 against 3 and note the result. Of course this is too easy a problem to set our puzzlers no matter how we solve it.

But if four weighings are allowed, the problem is probably too difficult, except by this procedure, when it is equally easy, even though it takes a bit longer to enumerate the outcomes. With four weighings there are 3⁴ - 3 = 78 possible outcomes, and these can be divided into two groups with 39 in each group. In this case we weigh thirteen balls against thirteen others at each weighing and note the results. This will allow us to pick out the odd ball among 39 balls. If five weighings are allowed we can find the odd ball, and whether it is heavy or light, among (3⁵ - 3)/2 = 120 balls.

In general, if n weighings are allowed, we can find the odd ball among (3ⁿ - 3)/2 apparently identical balls.

Weighing Coins, Balls, What Not ...

1. The Oddball Problem, B. Bundy
2. Weighing 12 coins, Dyson and Lyness' solution
3. Weighing 12 coins, W. McWorter
4. Thought Less Mathematics, D. Newman
5. Weighing with counterbalances
6. Odd Coin Problems, J. Wert
   • Odd Coin Problems, a shortened exposition
7. Six Balls, Two Weighings
8. 12 Coins in Verse
9. Six Misnamed Coins, Two Weighings
10. A Fake Among Eight Coins
11. A Stack of Fake Coins

|Contact| |Front page| |Contents| |Store|

Copyright © 1996-2012 Alexander Bogomolny