Fog Creek Software
Discussion Board




can anyone solve this coin problem?

I have struggled in vain to solve the even harder coin problem. Does anyone have any insight on this problem?

James kloberdance
Friday, November 14, 2003

No special insight here, just organization.

Write down the 27 possible measurements--Left, M(level) and Right for weighings 1, 2, and 3.

LLL
LLM
LLR
LML
LMM
....

Then enumerate the 24 possible conclusions-each coin being either heavy or light:

1H
1L
2H
2L
....

Then draw some spots for you to work out where the coins are at each weighing.
Left pan  Off scale    Right pan
_ _ _ _    _ _ _ _      _ _ _ _
_ _ _ _    _ _ _ _      _ _ _ _
_ _ _ _    _ _ _ _      _ _ _ _

Then start marking down the correspondence between
measurements and conclusions. If you decide "left, level, left" should mean coin 4 is heavy, write down 4H next to LML on the first list, cross off 4H on the second list, and place 4s in the pans so:

Left pan  Off scale    Right pan
4 _ _ _    _ _ _ _      _ _ _ _
_ _ _ _    4 _ _ _      _ _ _ _
4 _ _ _    _ _ _ _      _ _ _ _

Ham Fisted
Friday, November 14, 2003

I must admit, that even with you hint, I still can't solve this problem. I don't understand how your approach can work. We could conduct a simple experiment to see if your method works: I will pick which coin is the right coin and it's weight; you give me three weigh permutations and I will tell you the result of each weigh based on my knowledge of the correct answer; and then you will use your system to deduce which coin and whether its heavier or lighter.

James kloberdance
Friday, November 14, 2003

Sure thing.

First, put coins 1, 2, 7 and 10 in the left pan. Put coins 4, 6, 8, and 12 in the right pan.

Second, put 1, 5, 7, and 12 in the left pan and 3, 6, 9, and 10 in the right pan.

Third, put 1, 5, 9, and 10 in the left and 2, 4, 7, and 11 in the right.

Ham Fisted
Friday, November 14, 2003

Thanks for your patience. The first measurement would be balanced; the second would tilt to the right; the third would also tilt to the right.

James kloberdance
Friday, November 14, 2003

Here is one more also: balance,balanc, left tilt. Thanks.

James kloberdance
Friday, November 14, 2003

MRR - coin 5 is light.

MML - coin 11 is light.

Ham Fisted
Friday, November 14, 2003

You are a true genius. Thanks.

James kloberdance
Friday, November 14, 2003

Well, the solution above is not a solution it's a magic.
A SOLUTION should answer the question WHY.
And this problem is kind of trivial :) ...  I will explayn why:

We can represent every round as a regiter with 3 possible values therefore We have numeric system with base 3 (each register can be 0,1,2 or L,R,B)

So we can convert the task above to:
1. Map array (A1..An) to 3 register digit represented in (numeric system with base 3)
2. Be sure that every register gets same value (L,R or B) no more than n/3 times.

I think every one of you can solve this for 2 minutes :)
And it is obvious that there is more than one decision.
Example: (n = 12) 2 solutions
1  = LLL ; RLR
2  = LLR ; LLR
3  = LRB ; BRR
4  = LRL ; RRR
5  = RBR ; LBL
6  = RBB ; BBL
7  = RLL ; RLL
8  = RLR ; LLL
9  = BRB ; BRB
10 =BRL ; RRB
11 =BBR ; LBB
12 =BBB ; BBB
so on and so forth ...

OK :) so my question is:
How many solution do you have in your case (12 coins)?

Atanas Georgiev
Tuesday, February 03, 2004

Please excuse my english...
I did not finish the explanation ;).
Solution 1 gives us the following weight sequence
round one (all indices that have value L in the first register are present in the left pan; all indices having R in the first register are present ub the right pan; all with B in the first register are no used in the round) ... round II and III are extracted from register 2, 3 using same approach:
1  = LLL, 2  = LLR, 3  = LRB, 4  = LRL, 5  = RBR, 6  = RBB
7  = RLL, 8  = RLR, 9  = BRB, 10 =BRL, 11 =BBR, 12 =BBB
I.  1,2,3,4  <> 5,6,7,8
II.  1,2,7,8  <> 3,4,9,10
III. 1,4,7,10 <> 2,5,8,11

Atanas Georgiev
Tuesday, February 03, 2004

The above reasoning is certainly on the right track.  However, after reading the whole thing, you can just feel that there is something fishy.  But what?

After pondering on that for a while, it finally dawned on me.  The "SOLUTION" does not answer the question of whether the counterfeit coin is heavy or light.  In the puzzle it explicitly demands "you want to say whether the coin weighs more or less than it should."  But if you never put coin #12 on the balance, then how do you know whether it is heavy or light if it happens to be the counterfeit coin?

There must be some more restrictions on the way to map the coins to the "registers" to make it work.  Maybe it is not so trivial after all.

JHY
Wednesday, February 04, 2004

Furthermore, solution 2 is flawed by the same reason - the solution has to take into account that the counterfeit coin could be either heavier or lighter than usual.

If you assign RRR to coin #4, you cannot assign LLL to coin #8.  For example, if the three weighings were RRR, then how would you know if coin #4 is counterfeit or if coin #8 is counterfeit?

There are definitely more than one solution though as this simple applet will demonstrate.

http://www.sharemation.com/irvine/Files1/CounterfeitCoinDemo.html

JHY
Thursday, February 05, 2004

IIf anyone has solved the adaptive version this is simply a case where you combine the adaptive tests into a single 'big' test.    (L means left side lighter in my lingo)

for example to solve 4 coins in 2 weighings (I need one std weight coin = S ):

1 2  <>  3 S
the adaptive version is if L or R then weight 1 vs 2 if Equal then weigh 4 against any other (all std)

these two tests can be combined  into the following
1 4  <> 2 S

so
LL = 1 lighter
LR = 2 lighter
LE = 3 heavier
RL = 2 heavier
RR = 1 light
RE = 3 lighter
EL = 4 light
ER = 4 heavy

By this same techinique you can combine the tests you would perform if an intial 4coin vs 4coin weighing was L or R with these tests (when Equal 1st)

-PB

Paul Bethe
Tuesday, February 10, 2004

*  Recent Topics

*  Fog Creek Home