
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 lefttipped, righttipped and balanced in the three weighings. If 'A' is lighter then it will be righttipped, lefttipped 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 LLR
There are (weighins)^(outcomes) or 3^3 possibilities. (27)
First, it was obvious that EEE 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. ERE, ELE 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 weighin 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 weighin would demonstrate 5 coins grouped together. To separate them would require more than 3 weighins. In fact 3 weighins can separate at most 4 = 2^(31) coins.
Because we cannot separate more than 4 coins on the scales, we need to leave out two more coins for each weighin.
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 weighin results
EEL => A is heavier
EER => A is lighter
LLR => J is heavier
LRL => K is heavier
ELR => 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 wordsall 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
16 aside
79 and 912 on balance
Second time
13 and 79 aside
46 and 1012 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 16 or 712
Knowing that the
second tells us wether it's in 13 or 79 or 46 or 1012
Knowing that the Third time tells us
Which coin is different.
No in fact that doesn't work
damn
Thierry Schellenbach http://www.topdownload.net
Saturday, March 12, 2005
Recent Topics
Fog Creek Home
