Here is a different solution I came up with driving from
Charlottesville to Fairfax.
The 12 Ball Problem
Assume you are given 12 identical looking balls. 11 balls are of a
standard weight and one ?oddball? weighs a little more or a little
less. You do not know which balls are which. Then you can identify the
odd ball and tell if it is heavier or lighter than the standard ball
in 3 weighings.
To solve this first we solve:
The 4 + 1 Ball Problem
Assume you are given 4 identical looking balls. 3 balls are of a
standard weight and one ?oddball? weighs either a little more or a
little less. You do not know which balls are which. Also assume you
have a 5th ball known to be standard. Then you can identify the odd
ball and tell if it is heavier or lighter than the standard ball in 2
weighings.
Proof. Let the 4 unknown balls be labeled A1, A2, A3, and A4 and the
known standard ball be labeled A5.
Weighing #1: Compare A1&A2 with A3&A5
Case 1. They are equal. Then A1, A2, and A3 are standard and A4 is the
oddball. A4 can be determined to be heavy or light in Weighing #2 by
comparing A4 with any one of the standard balls such as A5
Case 2. A1&A2 is heavier that A3&A5. Then exactly one of the balls A1
or A2 is heavy and the all the others standard or A3 is light and all
the others standard. So rename balls A1 and A2 to be A1-H and A2-H
(because one of them may be heavy) and rename A3 to be A3-L (because
it may be light). Now in Weighing #2 compare A2-H&A3-L with A4&A5
(Both of these last two are standard; A5 is standard by assumption and
A4 is standard because in Case 2 we know one of A1, A2, or A3 is the
oddball).
Note: A ball with an H suffix may be heavy or standard but it can
never be light. Similarly, a ball with an L suffix may be light or
standard, but never heavy.
Subcase 2.1 If A2-H&A3-L and A4&A5 are equal then A1-H is the heavy oddball
Subcase 2.2 If A2-H&A3-L is heavier than A4&A5 then A2-H is the heavy oddball
Subcase 2.3 If A2-H&A3-L is lighter than A4&A5 then A3-L is the light oddball
Case 3 A1&A2 is lighter that A3&A5. This is the same as Case 2 with
the H and L labels reversed
The 12 Ball Problem.
Assume you are given 12 identical looking balls. 11 balls are of a
standard weight and one ?oddball? weighs a little more or a little
less. You do not know which balls are which. Then you can identify the
odd ball and tell if it is heavier or lighter than the standard ball
in 3 weighings.
Proof. Let the 12 unknown balls be labeled A1, A2, A3, A4, B1, B2, B3,
B4, C1, C2, C3, C4.
Weighing #1: Compare A1&A2&A3&A4 with B1&B2&B3&B4
Case 1. A1&A2&A3&A4 is equal to B1&B2&B3&B4 .Then all the balls
weighed are standard and the oddball is one of C1, C2, C3, C4. Apply
the 4+1 Ball Problem to C1, C2, C3, and C4 with any one of the 8 known
standard balls as the 5th known standard ball.
Case 2. A1&A2&A3&A4is heavier B1&B2&B3&B4. Then C1, C2, C3, and C4 are
all standard. Relabel A1 to be A1-H, A2 to be A2-H, etc., to reflect
the possibility that one of them may be a heavy oddball. Similarly,
relabel B1-to be B1-L, B2 to be B2-L, etc. to reflect the possibility
that one of them may be a light oddball.
Define the 4 ?twin balls? D1=A1-H + B1-L, D2=A2-H + B2-L, D3=A3-H +
B3-L, D4=A4-H + B4-L. Thus, each of these 4 twin balls contains one
(single) ball that is possibly heavy and one that is possibly light.
Define a 5th standard ball D5=C1 + C2 (we know none of the ?C balls?
are oddballs by the assumption of Case 2). The 4+1 Ball Problem now
applies to the 4 (twin) balls D1, D2, D3, and D4 plus the 5th known
standard (twin) ball D5. By that proposition we can identify the odd
(twin) ball DX where X is one of 1, 2, 3, or 4 and whether it is heavy
or light in 2 more weighings for a total of 3.
To complete the identification from the twin oddball ball to the
single oddball we do not need an additional weighing because the twin
oddball (like all the oddballs) is made from a possibly heavy (single)
ball plus a possibly light (single) ball. Thus the rest is pure
deduction (recalling the note from the proof of the 4+1 Ball Problem).
Subcase 2.1 If DX is heavy then since DX=AX-H + BX-L we must have AX-H
is the heavy oddball.
Subcase 2.2 If DX is light then since DX=AX-H + BX-L we must have BX-L
is the light oddball.
Case 3. A1&A2&A3&A4is lighter B1&B2&B3&B4. This is the same as Case 2
with H and L labels reversed. |
