Fog Creek Software
Discussion Board




classic weighing for grandmothers

I'm not sure if this solution is simpler to explain to grandma than the given one, but I suspect so.

First, it's obvious that each weighing has to weigh the same
number of pills against the same number of pills.

For each weighing, there are 3 outcomes: the left side will be heavier, lighter, or equal.  So there are 27 possible outcomes.

A pill being lighter instead of heavier will basically "invert" the outcomes -- light will become heavy, and vice versa.  So for each pill, there are two associated outcomes, each the "inverse" of the other.  And no two pills can share outcomes.

So, we now map each pair of outcomes to a pill.  Call the weighings X, Y, and Z, and call the pills A, B, C, ...

A: all heavier (or all lighter)
B: XY heavier, Z lighter (or XY lighter and Z heavier)
C: XZ heavier, Y lighter (..)
D: YZ heavier, X lighter (..)
E: XY heavier, Z equal (or XY lighter and Z equal)
F: XZ heavier, Y equal (..)
G: YZ heavier, X equal (..)
H: X heavier, Y lighter, Z equal
I: X lighter, Y equal, Z heavier
J: X equal, Y heavier, Z lighter
K: X heavier, YZ equal
L: Y heavier, XZ equal
M: Z heavier, XY equal
N: all equal

(yes, I have 14 pills now)

Now, we place the pills so that those outcomes match:

X: ABC EF HK vs DI
Y: AB DE GJL vs CH
Z: A CD FGiM vs BJ
(pill N is nowhere)

Obviously each weighing we have 7 pills vs 2 pills.  This is not
useful.  So we put EFG on the other side:

X: ABC HK vs DIEF
Y: AB DJL vs CHEG
Z: A CDiM vs BJFG

Almost there.  I guess we can remove pills A and N, we don't need 14 pills anyway:

X: BC HK vs DIEF
Y: B DJL vs CHEG
Z:  CDiM vs BJFG

And you're done!  Note that if we had a guaranteed safe pill (call it Q), then we can put it on the right side, and now we can handle 13 pills, including A).  And even 14 pills if we include N, but we won't be able to tell if N is heavier or lighter.

Wei-Hwa Huang
Thursday, August 15, 2002

*  Recent Topics

*  Fog Creek Home