I explain the solution to a common, moderately difficult logic puzzle, and propose a novel variation with maximised difficulty. The wording of this variation, without solution, can be found in this footnote. The (obfuscated) solution is available in this footnote. The method is provided in the main text.
About two weeks ago, I attempted a set of logic puzzles that I came across on the Internet. I solved the first few, but there was one that I did not complete (mainly because my bus reached its stop). After getting off the bus, I forgot about the puzzle and did not think further on it.
Until yesterday. I had some free time, and found my mind wandering over various things, and for some reason thought about the puzzle. Since I had nothing better to do, I set about to solving it.
The puzzle went something like this:
“You have a bag of 12 balls, of which one is defective. The balls are all identical, except for the defective ball, which weighs slightly less or more; you do not know which. You have a scale which can tell you which of two sets of balls weigh more, or if they are the same weight. What is the minimum number of uses of the scale you need to identify the defective ball with certainty?”
I will go on to explain my thoughts and my solution to this puzzle, and raise related puzzles. If you want to attempt the puzzle by yourself, now is the time to do so.
Having done vaguely similar puzzles before, I immediately framed the question in terms of information. This is what I thought:
“There are twelve balls, therefore the location of the defective ball is described by three-point-something binary bits of information. Each comparison provides one bit of information. Ergo, four comparisons should be the minimum required.”
I then set out to find the exact algorithm that would find the ball, and immediately found something wrong.
I imagined weighing six of the balls against six of the others. The scale would tip to one side, but the problem is that this doesn’t provide any information as to the location of the defective ball. I wouldn’t know which side the defective ball was, since I didn’t know whether it was supposed to be lighter or heavier.
This seemed to indicate that one additional bit of information would be required to identify whether the defective ball was heavier or lighter, making a total of five bits.
At this point, alarm bells started going off in my head. Five comparisons seemed to be far too high a number for this problem. There also seemed to be a significant amount of wasted information from the comparison operations. I was also wondering why twelve balls were given, rather than sixteen, which I imagined would eliminate information redundancy which should strictly increase the difficulty of the puzzle.
After some thought, I realised that I had gotten two things wrong:
- The location of the defective ball is not described by one in twelve possibilities, instead it is one in twenty-four, accounting for whether it is heavier or lighter.
- The comparison does not give one binary bit of information, instead it gives one ternary bit: in addition to telling which side is heavier, both sides could be equal.
The approach to obtain a solution becomes clear: I need to find an algorithm that distributes the twenty-four possibilities as flatly as possible in a ternary outcome tree, minimising the maximum depth of the tree. Since twenty-four is two-point-something ternary bits, I should expect a solution to use no more than three comparisons.
The Weighing Operation
Before we proceed, we must establish what exactly happens in a single weighing operation.
Suppose I weigh one ball against one ball, and the scale shows the left side is heavier. Out of the four possibilities (Ball 1 is heavier, Ball 1 is lighter, Ball 2 is heavier, Ball 2 is lighter), I have eliminated half of them, and these two remain: Ball 1 is heavier, Ball 2 is lighter.
I shall abbreviate these as follows:
- 1HL means that neither of “Ball 1 is heavier” or “Ball 1 is lighter” have been eliminated.
- 5H means that “Ball 5 is lighter” has been eliminated, and “Ball 5 is heavier” remains.
- 12- means that both possibilities have been eliminated, and 12 is certainly not the defective ball.
So weighing balls 1HL vs 2HL gives:
- Case 1: 1 is heavier
- Case 2: 2 is heavier
- Case 3: Equal weight
However, the above is not complete, failing to take into account the implications on the other balls. The complete list would be:
- Case 1: 1 is heavier (1 > 2)
- Case 2: 2 is heavier (1 < 2)
- Case 3: Equal weight (1 = 2)
Thus, within each of Case 1 and 2 there are 2 remaining possibilities, and within Case 3 there are 20. If we want to minimise the depth of the tree, we need to even out the spread of possibilities between each of the 3 cases.
The First Step
It turns out that for the first comparison, weighing 4 balls against 4 balls gives the best spread:
- Case 1: (1-4) > (5-8)
- (1-4)H, (5-8)L, (9-12)- [8 possibilities]
- Case 2: (1-4) < (5-8)
- (1-4)L, (5-8)H, (9-12)- [8 possibilities]
- Case 3: (1-4) = (5-8)
- (1-8)-, (9-12)HL [8 possibilities]
Notice that Cases 1 and 2 are effectively identical, with 4 balls H and 4 balls L, therefore any algorithm that proceeds to solve Case 1 will also apply identically to Case 2.
Solving Case 1
Cases 1 can be solved quite easily. We want to split the 8 possibilities evenly into 3 cases of 3, 3, 2, such that only one more weighing is required.
To do this, I chose to weigh Left: 1H, 2H, 5L vs Right: 3H, 4H, 6L, leaving 7L and 8L aside.
- Case 1a: Left > Right
- Case 1b: Left < Right
- Case 1c: Left = Right
After this, the solution is trivial. If we have 1H, 2H and 6L, we just weight 1H vs 2H to see which is heavier; if equal, then 6L is the solution.
This solves Case 1, and therefore Case 2.
Solving Case 3
Case 3 is a little more difficult. It is not obvious (to me, at least, at the time) what needs to be done to split the 8 possibilities into cases of 3, 3, and 2.
However, a solution exists, by borrowing a ball (1-) that has already had its possibilities eliminated.
We weigh Left: 9HL, 10HL vs Right: 11HL, 1-.
- Case 3a: Left > Right
- Case 3b:
- Case 3c:
Cases 3a and 3b is the same situation found in Case 1: weighing a pair with the same polarity will yield the result. As for Case 3c, it is already solved, although we do not know whether the defective ball is heavier or lighter. However, if we want to find out, we can simply weigh it with 1-.
Thus Case 3 is solved, and thereby the puzzle.
Variation #1: 13 balls, 26 possibilities
Even though I obtained the solution, one question remained in my mind. Why did the puzzle author specify 12 balls? 3 weight comparisons are, in theory, sufficient to distinguish 13 balls: 3 ternary bits can distinguish 27 possibilities, and 13 balls only present 26 possibilities.
As it turns out, a solution is possible.
With 13 balls, it is not immediately possible to split the 26 possibilities into 3 cases of less than 9 each. Weighing 4v4 results in 8,8,10, and 5v5 results in 10,10,6. If there are more than 9 possibilities in one case, then two weighings, each of which provide one ternary bit of information, cannot distinguish every subcase.
However, if we have access to another ball 14-, which is known to be non-defective, we can weigh 5v5 with 14- on one side. This splits the cases into 9,9,8, perfect for our purposes.
As before, Case 1 and 2 are identical, and Case 3 is the same as in the original puzzle. So we need only solve Case 1.
Case 1 is not difficult to solve. It contains 5 balls of one polarity and 4 balls of the other. Let’s take the case where we have (1-5)H and (6-9)L.
We weigh Left: 1H, 2H, 6L vs Right: 3H, 4H, 7L, leaving 5H, 8L and 9L aside.
- Case 1a: Left > Right
- Case 1b: Left < Right
- Case 1c: Left = Right
In all three cases, to solve we need only weigh two balls with the same polarity to distinguish between the three remaining possibilities, solving the puzzle.
We can see that there are 3 possible reasons why the puzzle author didn’t include the thirteenth ball:
- They didn’t want to involve the use of an additional ball. (However, this could have been overcome by making the setting of the question in a “ball factory”, making more balls readily available. This would have the possibly desirable side effect of increasing the difficulty of the question.
- They didn’t think to use an additional ball. They tried 13, couldn’t make it to work, and reduced it to 12.
- They wanted to reduce hints at the solution. 12 is divisible by many factors, thereby not hinting at any particular method to the solution. (Although 13 is prime and similarly doesn’t hint at a solution, 13 immediately discourages thinking about the question in a binary fashion, which is the mistake I made and which by my best guess would be the mistake most people would make.)
Variation #2: 27 possibilities
What if we wanted to have 27 possibilities? We could include another half-ball: 14H. This ball only has one possibility enabled.
As it turns out, this is also possible. The solution is left as an exercise to the reader.
Variation #3: More than 27?
My initial mischaracterisation of the problem as having 12 possible states was flawed, but not unjustified. Although there are 24 states, the answer only distinguishes between twelve balls; the puzzle does not require us to state whether the defective ball is heavier or lighter. Therefore, there might exist some optimisations of the solution where the H and L cases of some balls are grouped together. By grouping these cases, we save the information required to distinguish the H and L cases.
I argue that we can only optimise one ball.
Looking at the weighing operation, so long as a ball is weighed on the scale, at least one of its cases will necessarily be eliminated. If it falls, its L case is eliminated, if it rises, its H case is eliminated, if balanced, both are eliminated.
However, to make use of grouping for optimisation, both H and L cases must remain open. If we have eliminated one of the cases, then we have already expended the information that we want to save by combining the cases.
Combining the above two facts, we deduce that we can only combine cases on a ball we have not weighed before.
This is important because it also guarantees that only one ball can be optimised by combining cases. If we have two balls we can optimise on, then we cannot have weighed either of them. But by symmetry, we also cannot distinguish the two, and therefore we do not know which is the solution. Therefore, if the question is to be solved, only one ball can have both cases remaining.
As we saw in “Solving Case 3”, case 3c, optimisation is possible, as we grouped together cases 12H and 12L. So, theoretically, we are able to solve a puzzle with 14 balls.
Let’s see if this is in fact possible:
We follow the same procedure in Variation #1, weighing 5v5 balls where one of the balls is taken from elsewhere and known to be not defective. This splits cases into 9,9,10. Case 1 and 2 are identical to Variation #1 and can be solved by the same method. The crux is in Case 3, where we seem to have insufficient information.
In Case 3, we have balls (10-14)HL. The solution in fact follows the same lines as Variation 1: we weigh Left: 10HL, 11HL vs Right: 12HL, 1-, with 13HL and 14HL set aside.
- Case 3a: Left > Right
- Case 3b:
- Case 3c:
Cases 3a and 3b are trivial, following the same method outlined previously. Case 3c is the focus, containing 4 possibilities where all others contain 3.
To solve, we weigh 13HL vs 1-.
- Case 3ci: 13HL > 1-
- Case 3cii: 13HL < 1-
- Case 3ciii: 13HL = 1-
And thereby, 14 balls can be solved.
As the 14 ball variant is solvable, and I have shown above that no more information can be saved by this method, I believe that 14 balls is the maximum that can be distinguished in this type of problem.
This leads me to propose Variant #3 of this problem:
You have 10 bags, each containing N balls. All balls are identical, with the sole exception of exactly one ball in bag #4. You do not know which ball is the defective ball. It looks identical, but weighs slightly less or more, you do not know which. You have a scale which can tell you which of two sets of balls weigh more, or if they are the same weight. What is the maximum value of N, such that you can certainly identify the defective ball within 3 uses of the scale?
I believe that this variant is the hardest possible variation of this problem. Not only does it require all the reasoning of the original variation, it also requires the reader to:
- realise that the question phrasing allows access to additional balls of known weight, and apply this knowledge.
- realise that although 3 uses of the scale can technically distinguish only 27 possibilities, the nature of the question allows 28
I expect that most people will be able to reach an answer of 12. Only some will reach 13, and only the most careful will realise that 14 is possible. I suspect that if I were to pose this question to myself, I might not even reach 12, due to my initial binary misconception; I might even guess 8.
I have solved the most common variation of this problem, and created several variations with increased difficulty, including one with maximal difficulty. I hope that this post has shed light on how to approach and solve this general type of logic puzzle, as well as on the nature of information.