Fog Creek Software
Discussion Board




even harder coin problem

Interestingly, to me the "even harder" coin problem was in fact much easier than the "easier" one.  The reason is that knowing that THERE IS a nonadaptive solution which also tells you whether the coin is lighter or heavier helps a lot.

Let's label the coins with the letters 'A' ... 'L'.  For each of the weighings we assign a label to each coin as follows: '+' if the coin is on the left hand side, '-' if it is on the right hand side and '0' if the coin is not part of the weighing.  The full solution then assigns a triplet of these symbols to each of the twelve coins, e.g. (A: +-0 ; B: -0- ; ... ) as follows:

  1.  The number of '+' and '-' assignments should be equal for the each of the three labels as in each weighing the coins on the left and right hand side of the scales should be equal.
  2. For a given coin, the assigned triplet also tells us the result of the weighing in case the coin is counterfeit.  For example if +-0 is assigned to 'A' and 'A' is heavier than the others then the scale will be left-tipped, right-tipped and balanced in the three weighings.  If 'A' is lighter then it will be right-tipped, left-tipped and balanced.
  3. No triplet should be assigned to two different coins otherwise we will not be able to tell which one is counterfeit.
  4. If a triplet is assigned to a coin, its inverse should not be assigned to another coin, otherwise we cannot tell the difference between the cases when one is a heavier counterfeit or the other one is a lighter counterfeit.  (The inverse of a triplet is of course when the signs are reversed.)
  5. The triplet 000 should not be assigned to a coin otherwise if that coin is counterfeit we won't be able to tell whether it is heavier or lighter.

There are 27 such triplets, 000 is excluded which leaves us with 13 pairs (triplet and its inverse), of which we should drop exactly one, which must be +++/--- to satisfy the parity constraint 1. above.

Then all we need to do is pick one of each of the 12 pairs in such a way that the + and - signs are equal for each of the three weighings.  A solution is:
-00, 0+0, 00-, 0--, 0-+, -0-, -0+, ++0, +-0, -++, +-+, ++-
which corresponds to the weighings:
HIKL - AFGJ
BHJL - DEIK
EGJK - CDFL

Tamas Hauer
Tuesday, January 04, 2005

>There are 27 such triplets, 000 is excluded which leaves >us with 13 pairs (triplet and its inverse), of which we >should drop exactly one, which must be +++/--- to satisfy >the parity constraint 1. above.

We do not necessarily have to drop the +++/--- pair.

Here is an example from another thread copy and pasted here.

Test 1 :
Left pan : 3 4 9 12
Right Pan : 6 7 10 11


Test 2:
Left Pan : 1 5 9 11
Right Pan : 4 6 7 8


Test 3:
Left Pan :  2 3 7 10
Right Pan :  5 6 8 11

Coin #6 is the one with the --- triplet.

JHY
Tuesday, January 04, 2005

> We do not necessarily have to drop the +++/--- pair.

Yep, you are right, thanks.  One of the +++, ++-, +--, +-+ pairs should be dropped.  I preferred dropping the +++/--- because the solution is more symmetric and I guess I got carried away overlooking the other possibilities.

Apologies if this was discussed before, I have not found another thread.

Tamas Hauer
Tuesday, January 04, 2005

First off, I would like to say I really enjoyed this problem.  It was a very good mental exercise.

I approached the problem by first viewing the different permutations of the results. 

Let's define the results as:
L=Left Tilt
E=Even Balance
R=Right Tilt

e.g. after three balancing acts... we could have L-L-R

There are (weigh-ins)^(outcomes) or 3^3 possibilities. (27)

First, it was obvious that E-E-E does not help us, because at best it can tell us which coin id bad, but not tell us if it were lighter or heavier.  Leaving us with 26 useful result permutations.

Second, because we have 12 coins and they can each be either heavier or lighter, requiring 24 permutations.

I then noticed that there are 6 permutations involving two (2) even balances.  Each of these has a polar opposite (R opposite L).  e.g. E-R-E, E-L-E can determine the same coin is either heavier or lighter.  This covers 3 coins...

The only way to achieve two even balances is if the bad coin is out of the weigh-in twice.

So I started with

    Out  Left  Right
1) AB    C      ?
2) AC    B      ?
3) BC    A      ?

Now, there are 9 coins remaining.  We must ensure that all pairings of these 9 coins are both together and separated on the scales at some point in time.  If we put the remaining coins on the scales (along with A,B, or C), then we will have five on either side.  The first weigh-in would demonstrate 5 coins grouped together.  To separate them would require more than 3 weigh-ins.  In fact 3 weigh-ins can separate at most 4 = 2^(3-1) coins.

Because we cannot separate more than 4 coins on the scales, we need to leave out two more coins for each weigh-in.

    Out      Left  Right      Still to be placed
1) ABDE    C      ?          FGHIJKL
2) ACFG    B      ?          DEHIJKL
3) BCHI    A      ?            DEFGJKL

As for DE, FG, and HI... The two times that they are included on the scales, they must be both paired and separated.  So let's place them now...

First, paired....
    Out      Left  Right      Still to be placed
1) ABDE    C      FG        HIJKL
2) ACFG    B      HI        DEJKL
3) BCHI    A      DE        FGJKL

Then separated
    Out      Left  Right      Still to be placed
1) ABDE    CH    FGI        JKL
2) ACFG    BD    HIE        JKL
3) BCHI    AF      DEG      JKL

Now all that is left is to place all the different permutations of JKL as (2)(1)

    Out      Left      Right
1) ABDE    CHJK    FGIL
2) ACFG    BDJL    HIEK
3) BCHI    AFKL      DEGJ

sample weigh-in results
E-E-L  => A is heavier
E-E-R  => A is lighter
L-L-R  => J is heavier
L-R-L  => K is heavier
E-L-R  => D is heavier.

Will Smith
Friday, January 07, 2005

You already have the correct solution; my only contribution is to suggest trinary arithmetic makes quick work of this problem.

Anonymous
Friday, January 07, 2005

The last suggestion, trinary logic, seemed like the obvious method to me as well: Knowing that there was a solution, the maximum information gathered in one weighing was obviously a single trit (trinary digit).

Three trits makes for 27 combinations, while we need 12*2 = 24 to determine both coin number and heavy/light status.

Terje

Terje Mathisen
Wednesday, February 02, 2005

Actually, I don't understand why everyone of you are so sure that three trits can found out the counterfeit one out of 12?

thanks a lot.

Dennis Chow (from Hong Kong)
Monday, February 14, 2005

should be three weighing, not three trits

Dennis Chow (from Hong Kong)
Monday, February 14, 2005

How about this one, which I had to do the other day for class:

You have twelve coins. A MAXIMUM of 1 coin is counterfeit (in other words--all coins COULD be legit) Determine in three weighings whether there is a counterfeit coin and whether it is lighter or heavier.

Phillip
Saturday, February 26, 2005

First time
1-6 aside
7-9 and 9-12 on balance

Second time
1-3 and 7-9 aside
4-6 and 10-12 on balance

Third time
3,6,9,12 aside
1,4,7,10 and 2,5,8,11 on balance


First weighing gives us wether the coin is in 1-6 or 7-12
Knowing that the
second tells us wether it's in 1-3 or 7-9 or 4-6 or 10-12
Knowing that the Third time tells us
Which coin is different.

No in fact that doesn't work
damn

Thierry Schellenbach http://www.top-download.net
Saturday, March 12, 2005

*  Recent Topics

*  Fog Creek Home