🚀 go-pugleaf

Capt Scott (retired) writes:
>I was told a puzzle recently and it is driving me spare.
>I have a feeling it is probably  standard puzzle so if anyone
>can help me ....
>
>This is it:-
>	You have 12 bolts, totally identical except 1 is either 
>lighter or heavier. Using a balance-scale 3 times find the 
>Dud.
>
>Any help appreciated
>Scott
>
>-- 
>-----------------------------------------------------------------
> Scott Gilhooly             |The only thing more dangerous than |
> Glasgow University         |a programmer with a screwdriver is |
> gilhoosg@dcs.gla.ac.uk     |a user with an idea                |

Wow. We just discussed this today in my Winter Study course at
Williams College - puzzle solving.  I think it may be a FAQ, but
here's our solution:
 
Let the numbers 1 - 12 represent the 12 bolts:

1 2 3 4 5 6 7 8 9 10 11 12

Divide into three groups of four:

(1 2 3 4)    (5 6 7 8)    (9 10 11 12)

Weigh (1 2 3 4) vs (5 6 7 8).  If they weigh the same, then bolts 1-8
weigh the same, so one of 9-12 weighs more or less than the others.
Weigh (9 10 11) vs (1 2 3) (normal weight).  If it weighs
the same, then 12 is the odd bolt, and you can easily find out if it
is heavy or light using the last weighing.  Otherwise, 9, 10, and 11
is either heavier or lighter than 1, 2, and 3, and the odd bolt will
be heavier or lighter correspondingly.  Weigh 9 vs 10.  If they are
equal, then bolt eleven is odd (and you know if it is heavy or light)
otherwise, you know from weighing 9 vs 10 which is not normal, since
you know if the odd one is heavy or light.  

Now, assume that (1 2 3 4) does not balance (5 6 7 8).  We may assume WLOG
that (1 2 3 4) is heavier.  Thus, either one of (1 2 3 4) is too heavy, or
one of (5 6 7 8) is too light.  Weigh (1 2 5) vs (3 4 6).  (Note that
(1 2 5) is essentially the same as (3 4 6) - 1, 2, 3, 4 *might* be too
heavy, 5, 6 *might* be too light) If they balance, then either 7 or 8
is too light.  In this case, weigh 7 vs 8, and the lighter of the
two is the odd one.  Otherwise, assume WLOG that (1 2 5) is heavier
than (3 4 6).  Then either 1 or 2 is too heavy, or 6 is too light.
Weigh 1 vs 2.  If one of them is heavier, it is the odd bolt, and is
too heavy, otherwise 6 is too light.
 

Sorry if this is too complicated, but it is complete (I'm convinced,
at least) and it even tells if the odd bolt is too heavy or too light
(Ooh, Aah :-)  I hope this helps.

-Chris


-- 
- Chris Kollett
  Christopher.S.Kollett@williams.edu
  WUFO - 1992 Division II Champs!