Q: You have 12 similar balls but one is defective and differs in weight
from the others. You do not know whether it is heavier or lighter.
You have a balance, and are permitted three weighings. How can you
find the defective ball and tell whether it weighs more or less than
the others?
A: Consider first a group of three balls, x y z, containing one known
to be heavier. A single weighing: x vs y, determines which it is.
Refer to this as Problem B.
Proceeding to the main problem:
Weighing 1: 1 2 3 4 vs 5 6 7 8
Case 1A : equality. The bad ball is among 9 10 11 12.
Weighing 2: 9 10 11 vs 1 2 3
Case 1A.2A : equality. 12 is the bad ball.
Weighing 3: 12 vs 1 discovers if it is light or heavy.
Case 1A.2B : left > right. The bad ball is heavier and among 9 10 11.
This is an instance of Problem B.
Case 1A.2C : left < right. The bad ball is lighter and among 9 10 11.
Problem B again.
Case 1B : left > right. The bad ball is heavier and among 1 2 3 4,
or lighter and among 5 6 7 8.
Weighing 2: 1 2 3 8 vs 9 10 11 4
Case 1B.2A : equality. The bad ball is lighter and among 5 6 7.
Again, we have an instance of Problem B.
Case 1B.2B : left > right. The bad ball is heavier and among 1 2 3.
Yet again, Problem B.
Case 1B.2C : left < right. The bad ball is heavier and is 4,
or lighter and is 8.
Weighing 3: 4 vs 9 determines which.
Case 1C : left < right. Analogous to case 1B.
Some comments.
A predecessor to this problem, posted earlier, specified 8 balls, one
lighter than the rest, and permitted two weighings. Here we apply B
twice over. First we weigh 1 2 3 vs 4 5 6 to determine which of three
groups of balls contains the lighter one. Then we apply B again to the
lighter group to pick the single bad ball. Two weighings, in fact,
suffice for 9 balls. (Did the setter feel that specifying 9 would give
the game away?)
This, of course, is not surprising. A weighing provides one of three
results, and combining two should allow us to discriminate between nine
possibilities: 1 lighter, 2 lighter, ... , 9 lighter.
Similarly, three weighings should discriminate among 27 possibilities:
1 lighter, 1 heavier, 2 lighter, ... So why not, in our question, 13
balls?
The problem with my solution is that three of the results are impossible.
In case 1A.2A weighing 3, we cannot have 12 = 1; similarly, in case 1B.2C
weighing 3, we cannot have 4 < 9; and the analogous situation arises in
case 1C.
So we have 24 possible results discriminating the 24 cases.
Is there, then, a different solution which allows for 13 balls? Actually,
not. It is easy to prove this impossible.
With 13 balls, there are 26 alternatives, which must be partitioned into
groups of 9, 9 and 8 by the three results of the first weighing. (A
group of 10 or more cannot be distinguished with the remaining two
weighings.)
But if the first weighing is 1 2 3 4 5 vs 6 7 8 9 10, equality separates
out a group of six alternatives (any of 11 12 13 either lighter or
heavier); while each inequality produces a group of ten.
On the other hand, if the first weighing is 1 2 3 4 vs 5 6 7 8, then
equality yields a group of ten alternatives, while each inequality
yields eight.
Actually, we might have suspected this. If the nature (heavier or lighter)
of the bad ball is unknown, symmetry tell us that the first partition can
only be into even groups: 8, 8, 10 or 10, 10, 6, not 9, 9, 8. (For every
"heavy" in each partition, there must also be a "light".)
Hence, for three weighings, 12 is the largest number of balls.