Twelve Balls

Things that amused us when we should have been working

I came across a note I made in 1970 (on the right of the notepad, above):

                                        SHINE BALD TOP
                                        BALD SPOT
                                        SLAB DINE
                                        HEAP LIST

It took me a while to remember what it was. Eventually it came back: it was the solution to the twelve balls problem (sometimes known as the twelve coins problem). One of the management staff posed it in November, 1969, when we were auditing Spencer and Halstead, an engineering manufacturer at Ossett. We couldn’t solve it. Insufferably, he wouldn’t tell us the answer until our next visit four months later.

The Problem: You have twelve identical-looking balls (or they could be coins or anything similar). One of them is a forgery and is therefore different in weight to others: it could be heavier or it could be lighter but you do not know which. You have a simple balance to weigh the balls against each other, but you can use it only three times – no more. How do you identify the fake ball and whether it weighs more or less than the others?

Note that you do not know whether the fake is heavier or lighter. If you knew for certain that it was, say, definitely lighter than the others, the problem is slightly different: it becomes a question of how to find a single fake out of nine coins in two weighings, or out of twenty-seven coins in three weighings. This is simpler and is not addressed here.

You may wish to pause to consider it further at this point. Or, if you’ve glazed over already, you may wish to jump to the end to find out about the other notes on the notepad.

                                                                *          *          *

The answer is to label the twelve balls with the letters of the first phrase above, and then weigh them in groups of eight – four against four – as specified in the three pairs of words.

For example, if the three weighings come out as (i) balance (ii) left heavy (iii) right heavy, then you know the faulty ball is not one of those in the first weighing, so it must be H, I, N or E. The second weighing eliminates H which is not there, and because I, N and E are on the light side, one of these must be lighter than all the others. Of these only E is on the light side in the third weighing, so E is the fake, and it is lighter than the others.

I wondered how this could work for all possible answers. Well, first of all, because each weighing can have three possible outcomes – left heavier, right heavier or balance – there are 3 x 3 x 3 i.e. 27 possible outcomes across the three weighings. Secondly, as there are twelve balls, and as we know that only one of them is either heavier or lighter, there are 24 possible answers. So the number of possible outcomes exceeds the number of possible answers, suggesting that each outcome could identify a different answer, with three outcomes unused.

One of the unused outcomes has to be where all three weighings are in balance, because that would mean all balls had identical weight. 

Not being one to let this kind of thing pass by without further thought, I could not resist creating the following table (L means left heavy, R means right heavy and B means balance). Hey, some people enjoy crosswords, I enjoy doing this. Get over it!

S heavy = RLR	S light = LRL
H heavy = BBL	H light = BBR
I heavy = BRR	I light = BLL
N heavy = BRB	N light = BLB
E heavy = BRL	E light = BLR
B heavy = LLB	B light = RRB
A heavy = LLL	A light = RRR
L heavy = LLR	L light = RRL
D heavy = LRB	D light = RLB
T heavy = RBR	T light = LBL
O heavy = RBB	O light = LBB
P heavy = RBL	P light = LBR
Not used: BBB, RLL, LRR

You can see that the outcomes for heavy balls are mirror images of the outcomes for light balls. Also, the ‘unused outcomes’ are ones which do not occur.

In fact, the table also tells you where to place each ball in the three weighings. Looking just at the left hand column: Ball A should be placed on the left of the balance in all three weighings; Ball O should be placed on the right in the first weighing and omitted from the second and third weighings.

With this insight, we could now create our own mnemonic for the solution. How about:

                                        READ THIS BLOG
                                        READ BITS
                                        BEAR GOLD
                                        THOR SLED

I think it works. It’s just a case of finding a phrase consisting of twelve different letters, and then jiggling the letters and weighing patterns around until you get words.

I wondered why a pair of outcomes is left over: RLL / LRR as well as BBB. It is because the solution only needs 24 rather than the full 26 of the 3 x 3 x 3, i.e. 27 possible outcomes. So could it be used for a thirteenth ball? Unfortunately not, because if you placed a thirteenth ball on the balance you would be weighing six balls against seven each time, which would tell you nothing. However, I think you could use this outcome instead of one of the others provided you switched round other balls to preserve the equality of the three four-against-four weighings.

Could you do four balls in two weighings? Theoretically, this has 8 possible answers with 3 x 3 i.e. 9 outcomes from two weighings. But, you get only a partial solution. You have to weigh one against one each time (with two two-against-two weighings, neither would balance, and five of the nine possible outcomes would be non-occurring). For example, labelling the balls A, B, C and D, and weighing A against B and then A against C:

A heavy = LL	A light = RR
B heavy = RB	B light = LB
C heavy = BR	C light = BL
D heavy =BB	D light = BB (also)
Not used: RL, LR

It identifies all outcomes except when ball D is the fake, which is identified correctly but not whether heavy or light. However, it would work if you had only three balls and two weighings. I suspect this was the starting point for the person who originally formulated the problem.

What if you were allowed four weighings? What, then, would be the maximum number of balls from which you could identify a lighter or heavier fake? There would then be 3 x 3 x 3 x 3, i.e. 81 possible outcomes. Forty balls would have eighty possible answers, but I suspect you would have insufficient non-occurring / unused outcomes to be able to do it.

Well, I’ve worked it out (I told you I’m a loony). Four weighings would allow you to find the fake amongst thirty-nine balls. If you want to know how I did it, look here. It actually gives quite an insight into how the whole things works. It appears there is always a variety of ways to formulate the groups used in the weighings.

What if, rather than just one, there were two fake balls? How would you weigh them then? O.K., this is beginning to go beyond even my limits of pointless curiosity. Proper mathematicians have come up with formulae to show how many balls can be done in N weighings (in the main case considered here it’s ½(3ⁿ-1)-1 if you want to know, but it can get a lot more complicated).

It’s clever stuff. Out of the millions of ways in which twelve balls can be weighed against each other, it is genius to realise that you can arrange things so that each combination of outcomes identifies a different solution. And just as brilliant is the realisation that the balls can be labelled with the letters of a phrase so that the three weighings can be selected using pairs of words made from the letters of that phrase. But cleverest of all is whoever it was that came up with the problem in the first place.

                                                     *                 *                *

The other notes on the paper, by the way, are also things which amused us during our working hours.

The first is supposedly a telegram sent by a sailor to his wife on returning from a long voyage. It was intended to read “In today, home tonight, lots of love, Rodney” but got garbled during transmission and came out probably as what he was really thinking.

The second refers to a philanderer who took out policies with different insurers to provide for his loved ones. The policy for his baby was with General Accident, and so on.

So, we did not spend our entire time thinking about combinations and permutations. Welcome to the wonderful misogynistic world of business and commerce, 1970.