Fortunately, the weighting master's certificate could be awarded to Mister Frank Entrich from Norderstedt (Germany) because he was the first who solved this task completely and rightly how the answer from him below shows. If you still are brooding despairingly over it, then it is your best way to consult him directly.
I divide the spheres into three groups (four spheres in each):
0 0 0 0 0 0 0 0 0 0 0 0
1 2 3 4 5 6 7 8 9 10 11 12
1st weighing attempt:
I weight the groups 1 and 2 ( spheres 1 - 8 )
0000 = 0000 => the scales are in balance
1234 5678
=> the differing sphere is inside the third group
(spheres 9 - 12)
2nd weighting attempt:
I take 3 spheres from the third group as well as one sphere from the first
eight ones (furthermore one sphere of the third group is kept
unconsidered)
0 0 = 0 0 => the scales are in balance
9 10 11 5
=> the differing sphere is the not weighted yet
one
3rd weighting attempt:
I compare the not weighted yet sphere with a known sphere (sphere from
1 - 11). The scale's deflection says if it's heavier or lighter one.
0 <> 0 => the sphere 5 is known, weight like the
12 5 other spheres 1 - 11
or:
2nd weighting attempt:
Same measure as before, only the scales slopes below to a side
0 0 <> 0 0 => the scales are not in balance
9 10 11 5
=> Then one of the third group is the differing
sphere. But I know from this measure depending
to the sloping side where the possibility lighter
resp. heavier sphere is.
3rd weighting attempt:
Assumption: the scales are sloping below on the left side and above on the
right side. I compare the left side (sphere 9 with sphere 10)
0 = 0 => the scales are in balance
9 10
=> Referred to the assumption, the 11th sphere has to
the lighter one.
or:
3rd weighting attempt:
Same assumption !
But the scales aren't in balance.
0 <> 0 => the scales are not in balance
9 10
=> The side where the scales are sloping below is the
the side with the heavy sphere.
or:
the first weighting already slopes the scale's beam in an unbalanced state.
1st weighting attempt:
0 0 0 0 <> 0 0 0 0 => the scales are not in balance
1 2 3 4 5 6 7 8
=> Then in the third group there are
only any spheres with the same weight.
2nd weighting attempt:
Assumption: The scales is sloping below on the left side and above on the
right side while the first attempt.
I distribute the spheres on this weighting in such a way that I'm making
usefully the result from the first measure. I say that on the left side
there are the supposedly heavy spheres and on the right the supposedly
light spheres (referred to the assumption)
h h l h s k => abbreviation: h = supposedly heavy
0 0 0 = 0 0 0 l = supposedly light
1 2 5 6 3 9 k = sphere with known weight
=> the scales are in balance
=> the differing sphere has to be inside the
currently not obtained spheres 4 (h), 7 (l)
and 8 (l).
3rd weighting attempt:
I examine the spheres 7 ( l ) and 8 ( l ) now.
l l
0 = 0 => the scales are in balance
7 8
=> Then the sphere 4 has to be the heavy one.
or :
2nd weighting attempt:
Same assumption !
But this time, the scales are unbalanced during the second weighting.
h h l l h k
0 0 0 <> 0 0 0 => the scales are not in balance
1 2 5 6 3 9
=> Then the differing sphere can be only into
the following group of the 5 spheres 1, 2, 3,
5 and 6.
Case differing:
1. The scales are sloping on left below and right above:
In this case only the spheres 1 (h), 2 (h) and 6 (l) are relevant.
3rd weighing attempt:
Comparison between sphere 1 and 2
h h
0 = 0 => the scales are in balance
1 2
=> Then the 6th sphere has to be the light one.
or:
3rd weighting attempt:
Same comparison between Vergleichswägung but the scales are unbalanced.
h h
0 <> 0 => the scales aren't in balance
1 2
=> the heavier sphere is there where the scales are
sloping below.
2. the scales are sloping above on the left side and below on the right
side.
In this case only the spheres 5 (l) and 3 (h) are relevant.
3rd weighting:
I compare the 5th sphere with a known one. If the scales are in balance,
then the 3rd sphere is the heavy one. But if the scales are unbalanced,
then the 5th sphere is the light one.
To hand this problem systematically, please have a look about the information quantity of the wanted information: information, if the sphere's lighter or heavier: 2 states => log2(2) = 1 bit. Information, which sphere: log2(12) = 3.58 bits => total information = log2(2) + log2(12) bits = log2(2·12) bits = log2(24) bits. That means that you have to determine one possibility from a quantity of 24 ones. The delivered information quantity of the three weightings: information, if equal, greater or less: 3 states => log2(3) = 1.58 bits => Three weightings give you an information amount of 3·log2(3) bits = log2(3³) bits = log3(27) bits. That means that you will receive a little superfluous information.
The actual answer can be determined with aid of a cancelling table, this is the easiest way:
X = out of the question, ? = still possible
111
123456789012 => sphere number
heavier ????????????
lighter ????????????
At the beginning all is possible. The following first weighting is to make in such a way that the remaining information quantity of the both remaining weights is sufficient in all three weight cases to solve the problem: 2 weighting give 2·log2(3) bits = log2(3²) bits = log2(9) bits of information. This is sufficient to select one of 9 states exactly => that means that the resulting situation may contain max. 9 ?.
Example for a wrong first attempt: 3 spheres on both sides (Nº 1 - 3 left, Nº 4 - 6 right):
case 1 : heavier on the left side (>)
111
123456789012
heavier ???XXXXXXXXX (either the heavier »outsider« in 1 to 3
lighter XXX???XXXXXX or the lighter »outsider« in 4 to 6)
case 2 : balance (=)
111
123456789012
heavier XXXXXX?????? (the »outsider« has to be in 7 to 12, but you don't
lighter XXXXXX?????? know yet if it's heavier or lighter)
case 3 : heavier on the right side (<)
111
123456789012
heavier XXX???XXXXXX (either the lighter »outsider« in 1 to 3
lighter ???XXXXXXXXX or the heavier »outsider« in 4 to 6)
In the cases 1 and 3, 18 of these 24 possible states could cancelled, so you have to determine one of 6 states [log2(6) bits of information needed] for what these log2(9) bits of information still are sufficient. But in the 2nd case, only 12 possibilities could cancelled, for what log2(12) bits of information are needed but these log2(9) of information are not sufficient to determine the wanted result of the task. You especially must reckon with case 2 just as the two other cases because the problem is to solve without game of chance strategy. The following table shows you what is remaining for each case.
| Nº of spheres per scale pan | case > | case = | case < |
|---|---|---|---|
| 1 | 2 | 20 (>9!) | 2 |
| 2 | 4 | 16 (>9!) | 4 |
| 3 | 6 | 12 (>9!) | 6 |
| 4 | 8 | 8 | 8 |
| 5 | 10 (>9!) | 4 | 10 (>9!) |
| 6 | 12 (>9!) | 0 | 12 (>9!) |
The table above clearly shows that you only can continue with 4 spheres in both sides. For the correct attempt with 4 spheres in each pan (Nº 1 - 4 at the left, Nº 5 - 8 at the right), the following situation is resulting:
case 1 : heavier on the left side (>)
111
123456789012
heavier ????XXXXXXXX (either the heavier »outsider« in 1 to 4
lighter XXXX????XXXX or the lighter »outsider« in 5 to 8)
case 2 : balance (=)
111
123456789012
heavier XXXXXXXX???? (the »outsider« has to be in 9 to 12, but you don't
lighter XXXXXXXX???? know yet if it's heavier or lighter)
case 3 : heavier on the right side (<)
111
123456789012
heavier XXXX????XXXX (either the lighter »outsider« in 1 to 4
lighter ????XXXXXXXX or the heavier »outsider« in 5 to 8)
On all three cases, 16 possibilities could cancelled so the continuation is always possible. For the second weight comparison you continue the same process in such a way that only 3 possibilities in the maximum are remaining in each case (3 cases from the first weighting × 3 cases 2nd weighting = 9 cancelling charts!) because there are only log2(3) bits of information remaining in each case.
Go back to the problem situation again