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 3, 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 3, 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 4, 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 5, 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   Fog Creek Home