Fog Creek Software
Discussion Board




Even harder coin problem

In three weighings there are 27 possible outcomes (3 * 3 * 3).  One
possibility (all balanced) is not useful to us since we are trying to
identify a single odd coin.  This leaves 26 useful results, or 13 pairs of
opposite results. (For example, RRB is the opposite of LLB.)

Since we want to know which coin is odd (1 in 12) and how it is odd
(heavier, lighter) it is necessary to consider the results as pairs of
opposites, with one pair indicating the coin, and which form indicating
whether it's lighter or heavier.

Since there are 24 actual possibilities (1 of 12 coins, light or heavy), I
have enough weighing results to cover all coins.  All we need to do now
is determine a proper ordering of the expected results which will map to a
possible weighing.

It turns out we need to weigh 8 coins at a time, 4 on each side.  So once
we determine the combinations of weighing results, we must order them so
any one weighing (first, second or third) has a particular result exactly
4 times.  (eg. for 12 outcomes, I can have the first weighing be
LEFT in exactly 4 of the outcomes.)

Here is the table I came up with of the 27 possible outcomes, paired with
their opposites and ordered as necessary to be useful for the problem:

Weighing  Opposite  Coin (see below)
A B C    A B C
--------  --------  ----------------
B B R  -  B B L        1
B R B  -  B L B        2
B L R  -  B R L        3
B L L  -  B R R        4
L B R  -  R B L        5
L B L  -  R B R        6
L R B  -  R L B        7
L B B  -  R B B        8
R L R  -  L R L        9
R R L  -  L L R      10
R L L  -  L R R      11
R R B  -  R R L      12

R R R - L L L -> leave out, for balance
B B B={not useful}

Notice that in each column (representing one weighing) there are 4 L's, 4
R's and 4 B's.  L's are LEFT, R's are RIGHT, and B's are BALANCED.

For each triplet of weighing results we get to choose one outcome.  But
the outcome we "assign" to a HEAVY weighing result determines the outcome
which must be assigned to a LIGHT weighing result for the same coin.  So
if BBR is the HEAVY result for COIN 1, then BBL must be the LIGHT weighing
result for COIN 1.  With this table ordered thusly, we can arbitrarily
assign the coins to the 12 result pairs (which I went ahead and did in
the above table). This then determines the weighing order.

I will arbitrarily decide that the left column of triplets indicates the
odd coin is heavy and the right column indicates the odd coin is light. 
So coins 1, 2 and 8 are present in only 1 weighing. Coins 3, 4, 5, 6, and
7 are present in 2 weighings; and coins 9, 10, 11, and 12 are present in
all three weighings.

All that's left is to translate the above map into the weighings we will
request.  Since the left column is the HEAVY result, I can see that coins
5-8 must be on the LEFT in the first weighing.  Likewise, 9-12 must be on
the right in the first weighing.  I continue mapping like this for each
column above and get this arrangement of weighings:


Weighing A:
    Left:  5 6 7 8
    Right: 9 10 11 12
 
Weighing B:
    Left:  3 4 9 11
    Right: 2 7 10 12
 
Weighing C:
    Left:  4 6 10 11
    Right: 1 3 5 9
 
By getting the results from these three weighings and comparing to the
above table, I can determine the odd coin and whether it's heavier or
lighter. For example, a weighing result of LRR indicates that 11 is the
odd coin and it is LIGHTER.  RLL indicates that 11 is odd and HEAVIER. 
BRB means 2 is HEAVY.  RBR means 6 is LIGHT.  And so on.  Because I
omitted RRR and LLL, these results should never appear.

This was a tough problem.  It took me about 5 minutes to determine that it was possible, and then about an hour to arrange everything so it worked and write up the results.

Phil Hord
Monday, October 28, 2002

Hi !
It took me a lot of time to prove that there exists a solution..., and then the same approach to solving it was followed - essentially start backwards with the outcomes and how the outcomes would result and then see if that can be forced.

It is still a nice exercise to come up with a formula for number of weighings needed for N coins (The BBB outcome can actually be used if N is odd)

There are altogether 27 outcomes to the weighings since each of the three weighings can be either
Left Tilt, Right Tilt or Balanced (LRB)

the outcomes are

LLL RRR
LLB RRB
LLR RRL
LBL RBR
LBB RBB
LBR RBL
LRL RLR
LRB RLB
LRR RLL

BLL BRR
BLB BRB
BLR BRL
BBL BBR

BBB

Notice that withe exception of BBB they are paired up such that the L and R
when exchanged give the other member of the pair.

Now we can arbitarily number our coins from 1 to 12 and assign each of these numbers
to the outcomes.

LLL RRR 1
LLB RRB 2
LLR RRL 3
LBL RBR 4
LBB RBB 5
LBR RBL 6
LRL RLR 7
LRB RLB 8
LRR RLL 9
BLL BRR 10
BLB BRB 11
BLR BRL 12
BBL BBR unused
BBB unused

Now just think of where the defective coin should be in a weighing so as to case the given outcomes.
One outcome is for if the coin is heavy and the other for if it is light.

Now you are allowed to choose either the left outcome or the right outcome and place the numbers for their positions in the balancing, you can just follow a dynamic allocation procedure and make corrections as you go on.

(LLL) RRR 1
LLB (RRB) 2
(LLR) RRL 3
LBL (RBR) 4
RBB (LBB) 5
(RBL) LBR 6
(RLR) LRL 7
RLB (LRB) 8
LRR RLL
BLL (BRR) 9
(BLB) BRB 10
BLR (BRL) 11
(BBL) BBR 12
BBB

In the process i was forced to drop the LRR RLL outcomes in favor of another because
it was not possible to balance the Left and right hand sides with it.

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


Q.E.D.
- Shyamal
Shyamal L, Bangalore, India

L. Shyamal
Tuesday, November 19, 2002

*  Recent Topics

*  Fog Creek Home