|Main index||Other Papers index||About author|
Julian D. A. Wiseman
Abstract: There are 12 objects, identical in all respects except that one of these objects is a different weight, perhaps heavier, perhaps lighter. Determine which is the odd one out, and whether it is heavier or lighter, using only 3 weighings of an old-fashioned scale (which reports either that the left side is heavier, or that the right side is heavier, or that the two sides weigh the same).
There are 363 objects, …, using only 6 weighings, ….
There are (3w–3)/2 objects, …, using only w weighings, … (with w≥3).
Contents: Abstract, Publication history, Twelve objects in three weighings, Thirty-nine in four, One hundred and twenty in five, (3w–3)/2 in w
Publication history: here. Usual disclaimer and copyright terms apply.
We start with the case when w=3, and so there are 12 objects. Label these A to L. Weigh A&B&C&D versus E&F&G&H. If the scale balances, then move down to the next weighing in the table (which is A&K v I&J). But if it tips to the left (so that A+B+C+D > E+F+G+H) then down and left; and if it tips to the right, then move down and right. After three weighings the label of the differently-weighted object is reached, suffixed with a “+” or “–” to indicate its type.
|A & B & C & D versus E & F & G & H|
|A & B & E versus C & D & F||A & K versus I & J||A & E & F versus B & G & H|
|A v B||G v H||C v D||I v J||A v L||I v J||E v F||C v D||G v H|
It is easy to prove that 12 is the maximum possible using only three weighings. Each weighing is either ‘left’, ‘draw’, or ‘right’, so three weighings have 33=27 possible outcomes. If there are n objects, then there are 2n possible states (as we don’t know whether the odd piece is heavier or lighter). So n≤13. Assume that n=13, and generate an impossibility. How many objects do we put on either side of the scale on the first weighing? Four is too few, because a draw leaves 10 states remaining (the 5 unused objects times the two possible differentnesses), which is more than can be distinguished using only two weighing (10>32). But five is too many, because a non-draw leaves 10 states: either one of the five on the heavier side is heavy, or one of the five on the lighter side is light. Hence 13 is impossible and so 12 is the maximum.
So what about four weighings? Trivially, 34=81 so we can have at most 40 objects. Again, first-weighing considerations show that this is too many: 13v13 implies that a draw leaves 28 states (which exceeds 33), but 14 on each side also fails. So in four weighings more than 39 objects would be too many, and if there are 39 objects, then the first weighing must be 13v13. This first weighing is either a draw or a non-draw. If it is a draw then we have 13 objects of unknown weight, and 26 that are definitely standard. Weigh 9 unknowns against 9 standard-weights. If this second weighing is a draw, then 4 unknowns remain, which is exactly the first-weighing-draws subproblem of the w=3 case. If the second weighing is a non-draw, then it is known whether the odd 1 of the 9 is heavier or lighter: proceed by repeated partition into equal thirds. Back to the first weighing: if it is a non-draw, then we know that 13 objects cannot be light, 13 cannot be heavy, that exactly one of these 13+13=26 is odd, and that 13 are definitely standard. For the second weighing put 9 possible-heavies and 4 possible-lights on the left, against 4 possible-heavies and 9 standard-weights on the right. If this tips left then one of the 9 possible-heavies on the left is the odd one, and if this is a draw then one of the unused 9 possible-lights is odd — again proceed by repeated partition into equal thirds. And if this second weighing tips right, it remains to distinguish between 4 possible-heavies and 4 possible-lights, which is the first weighing a non-draw subproblem to w=3 case.
As an aside, there is an elegant solution to the w=4 n=36 problem. Weigh 12v12. A draw leads to the w=3 case. If a non-draw, then create 12 ‘double-objects’ by ‘gluing’ together pairs, each consisting of one perhaps-heavy and one perhaps-light. This results in 12 double-objects, one of which is a different weight, with three weighings remaining: the w=3 problem.
With five weighings 120 objects is the maximum. Start with 40v40. If this first weighing is a draw, then weigh 27 of the unused objects against 27 of the standard-weights. If this second weighing is a draw proceed by repeated partition, and if a non-draw then 13 unknowns remain, which is exactly the first-weighing-draws subproblem of the w=4 case. If the first weighing is a non-draw, weigh 27 possible-heavies and 13-possible lights against 13 possible-heavies and standard-weights. If this tips left then there are 27 possible heavies, if a draw then the (unused) 27 possible lights. And if this second weighing tips right, it remains to distinguish between 13 possible-heavies and 13 possible-lights, which is the first weighing a non-draw subproblem to w=4 case.
We are now ready to tackle the general case, in which (3w–3)/2 objects can be distinguished in w weighings, and proceed by induction, as described in the table.
|First weighing: weigh (3w–1–1)/2 against (3w–1–1)/2.|
|Draw: odd is one of unused (3w–1–1)/2 objects. Weigh 3w–1 unknowns against same number of standard-weights.||Non-draw: weigh 3w–2 possible–heavies and (3w–1–1)/2 – 3w–2 = (3w–2–1)/2 possible-lights against the other (3w–1–1)/2 – 3w–2 = (3w–2–1)/2 possible-heavies and 3w–2 of the standard-weights.|
|Draw: odd is one of (3w–2–1)/2, which is first-weighing-a-draw subproblem of case in which w is 1 smaller.||Non-draw: odd is one of 3w–2, and it is known if the odd is heavier or lighter: repeated partition into thirds.||Left: it is one of the left-side 3w–2 possible-heavies: repeated partition into thirds.||Draw: it is one of the unused 3w–2 possible-lights: repeated partition into thirds.||Right: have (3w–2–1)/2 each of possible-heavies and possible-lights, which is case when w is 1 smaller and first weighing a non-draw.|
|Julian D. A. Wiseman, 1st June 1999, with thanks to Dr Nicholas F. J. Inglis for remarking on the important and false assumption in the previous edition.|
|Main index||Top||About author|