From: grabiner@math.harvard.edu (David Grabiner) Date: 14 Apr 1995 00:50:31 GMT
Subject: New Twelve (Eleven) Balls Puzzle (triple weighting)

In article <GRABINER.95Apr10221514@abel.harvard.edu>, I wrote:

> In article <3mcdon$sdh@gap.cco.caltech.edu>, Wei-Hwa Huang writes:
>> Obpuzzle:  You are given twelve seemingly identical balls.  Two of them are
>> heavier than the other ten by the same amount.  You are given a strange
>> 3-way scale that works this way:  You load the three pans, and if two of
>> them weigh the same, the third one will light up.  If they all weigh the
>> same or they are all different weights, you get no information between
>> the pans.  Identify the two balls with the least amount of weighings.

>> I can do it with 4 weighings.  Can anyone do better?

> Eleven balls, which give 55 cases, can be done with three weighings;
> this is a good puzzle.

Spoiler for 11 balls follows.  In fact, the weighings can be specified
in advance.

Note that if there are the same number of balls in all three pans, the
three weights cannot all be different, so the scale must balance.  

The first weighing is 12 vs. 34 vs. 56.

If they balance, the bad balls are among the other five.  Weigh 7 vs. 8
vs. 9.  If this balances, 10 and 11 are the bad balls; if 7 is different
>from  the other two, the bad balls are 8 and 9, 7 and 10, or 7 and 11,
and a 9 vs. 10 vs. 11 weighing will tell you which one.

If the first weighing doesn't balance, say that 12 is different.  The
bad balls may be 1 and 2, 1 or 2 and one of 7-11, or 3 or 4 and 5 or 6.
The second weighing is 13 vs. 57 vs. 68.

If this balances, the bad balls are 2 and one of 9, 10, or 11, so 9
vs. 10 vs. 11 will identify the other bad ball.

If 13 is different, the bad balls are 1 and one of 2, 9, 10, or 11, so 9
vs. 10 vs. 11 will identify the other bad ball.

If 57 is different, the bad balls are 1 and 8, or 2 and 7, or 3 and 6,
or 4 and 5, so 6 vs. 7 vs. 8 will identify the bad ball among 5-8, and
the other one follows.

If 68 is different, the bad balls are 1 and 7, or 2 and 8, or 3 and 5,
or 4 and 6, so 6 vs. 7 vs. 8 again identifies the bad ball among 5-8 and
the other one follows.

To specify the weighings in advance, we need a minor modification if the
first weighing balances; the second weighing then becomes 1 vs. 7 vs. 8.
If this balances, two of 9, 10, and 11 are bad, and 9 vs. 10 vs. 11 will
idenfity the good one.  If 1 is different, 7 and 8 are bad and the third
weighing is redundant.  If 7 or 8 is different, one of 9, 10, and 11 is
the other bad ball, so 9 vs. 10 vs. 11 will reveal it.

Now, to do this with weighings specified in advance, we add balls to
each of these weighings.

First weighing: 12 vs. 34 vs. 56.
Second weighing: 13 vs. 57 vs. 68.
Third weighing: 69 vs. 710 vs. 811.

The extra balls added are known to be good at the time of the weighing,
with the exception that if the first weighing balances and the second
weighing doesn't, we are using known bad balls.  This does not cause a
problem; if we know that 7 is bad and 6 and 8 are good, then 69 will be
different if 11 is bad, 710 will be different if 10 is bad, and 811 will
be different if 9 is bad.

--
David Grabiner, grabiner@math.harvard.edu
"We are sorry, but the number you have dialed is imaginary."
"Please rotate your phone 90 degrees and try again."
Disclaimer: I speak for no one and no one speaks for me.