Posted 19 July 2007 - 06:24 PM
Each weighing has three outcomes:
Left side is [lighter than] [equal to] [heavier than] Right side.
Three weighings can thus discern among [3]x[3]x[3]= 27 cases.
We have only 24 cases:
one of 12 balls is heavier or lighter than the rest.
So we can solve the problem, so long as ...
[1] The first weighing reduces the cases to no more than 9.
[2] The second weighing reduces the cases to no more than 3.
[3] The third weighing then distinguishes among 3 or fewer cases.
First weighing:
Set aside four balls. Why?
Because, if the first weighing balances, we have 8 [fewer than 9] cases:
One of the 4 excluded balls is heavier or lighter.
[1] Weigh 1 2 3 4 <=> 5 6 7 8
Outcome 1[a] 1 2 3 4 balances 5 6 7 8.
Since only one ball is odd, 1 2 3 4 5 6 7 8 must all be normal.
We have 8 cases: 9 10 11 or 12 is H or L
[shorthand: H=heavier; L=lighter]
[2] Weigh 1 2 3 <=> 9 10 11 [we know 1 2 3 are normal]
If this balances, 9 10 11 are also normal, and 12 is H or L.
[3] Weigh 12 <=> [any other ball]
If 12 rises, then 12L; if 12 falls, then 12H.
If [2] 9 10 11 rises, we have 3 cases: 9L, 10L or 11L
[3] Weigh 9 <=> 10.
If [3] balances, then 11L;
If 10 rises, then 10L; If 9 rises, then 9L
If [2] 9 10 11 falls, we have 3 cases: 9H, 10H or 11H
[3] Weigh 9 <=> 10.
If [3] balances, then 11H;
If 10 falls, then 10H; If 9 falls, then 9H
end of Outcome 1[a]: balance.
Outcome 1: 1 2 3 4 falls, and 5 6 7 8 rises.
This gives 8 cases: 1H, 2H, 3H, 4H, 5L, 6L, 7L, or 8L
The second weighing in this case becomes tricky.
Remember each of its three outcomes can lead to no
more than 3 cases for the third weighing to resolve.
Again, we exclude a number of balls and involve the others.
We exclude any three of the balls. Why? Because if the
other [included] balls balance, we have exactly 3 cases.
Without loss of generality we exclude balls 1 2 3.
Since that leaves an odd number of balls, 4 5 6 7 8,
we need to use one of the normal balls.
Finally we choose which three to weigh against the others.
And here's the only hard part of this problem.
We must mix some of the possibly light balls with some
of the possibly heavy balls. Otherwise, one of the
outcomes of the second weighing will leave us with more
than 3 cases, and the third weighing will not resolve this.
[2] weigh 4[H] 5[L] 6[L] <=> 1[normal] 7[L] 8[L]
in parentheses I've indicated the POSSIBLE cases
that we have determined:
4[H] means 4 is heavier if it's not normal.
Outcome 2[a]: 4 5 6 balances 1 7 8
These balls are all normal.
We have 3 cases: 1H 2H or 3H.
[3] weigh 1 <=> 2
If [3] balances, then 1 and 2 are normal, and 3H
if 2 falls, then 2H
if 1 falls, then 1H
Outcome 2b: 4 5 6 falls, and 1 7 8 rises.
We have 3 cases: 4H 7L or 8L
[3] weigh 7 <=> 8
if [3] balances, then 7 and 8 are normal, and 4H
if 7 rises, then 7L
if 8 rises, then 8L
Outcome 2[c]: 4 5 6 rises, and 1 7 8 falls.
We have 2 cases: 5L or 6L.
[3] weigh 1[normal] <=> 5[L]
If 5 rises, then 5L
If balance, then 5 is normal, and 6L
Now we can go back and take the remaining case
Outcome 1[c]: 1 2 3 4 rises, and 5 6 7 8 falls.
to distinguish among the remaining 8 cases:
1L 2L 3L 4L 5H 6H 7H and [b]8H
exactly as we analyzed Outcome 1b.
Simply substitute H for L and v.v.
Problem solved.
The greatest challenge to any thinker is stating the problem in a way that will allow a solution. - Bertrand Russell
rookie1ja 
Sign In
Register
Help
MultiQuote