even harder coin problem I'm suggesting a solution which has a defect: I can't calculate in one case if the coin is lighter or heavier... It is similar to the one I suggested for the 12 pills problem: First, I'm writing a more detailed explaining of how it was perceived: We divide the pills (coins, balls whatever) into three sets of four: 1234, ABCD and  abcd . We put on the balance 1234 versus ABCD 1.    1234 > ABCD (means that either one of the 1234 is the wanted one and is heavier or it’s one of the ABCD and it’s lighter) We put 12AB versus bcdD 1.1.    12AB > bcdD (means that one of the common with the first weighing is the wanted one, or it’s the 1 or 2 and heavier or the D and lighter) We put 1 versus 2 1.1.1.    1 > 2 (means that it’s 1 and heavier) 1.1.2.    2 > 1 (means that it’s 2 and heavier) 1.1.3.    1 = 2 (means that it’s D and lighter) 1.2.    12AB < bcdD (means that one of the reversed is the one, which is either A or B) We put A versus B 1.2.1.    A > B (means that it’s B) 1.2.2.    A < B (means that it’s A) 1.3.    12AB = bcdD (means that it’s one of the missing, which is either 3 or 4 and heavier or C and lighter) We put 3 versus 4 1.3.1.    3 > 4 (means that it’s 3) 1.3.2.    3 < 4 (means that it’s 4) 1.3.3.    3 = 4 (means that it’s C) 2.    1234 < ABCD (means that either one of the 1234 is the wanted one and is lighter or it’s one of the ABCD and it’s heavier). We put 12AB versus bcdD 2.1.    12AB < bcdD (means that one of the common with the first weighing is the wanted one, or it’s the 1 or 2 and lighter or the D and heavier) We put 1 versus 2 2.1.1.    1 > 2 (means that it’s 2 and lighter) 2.1.2.    2 > 1 (means that it’s 1 and lighter) 2.1.3.    1 = 2 (means that it’s D and heavier) 2.2.    12AB > bcdD (means that one of the reversed is the one, which is either A or B and heavier) We put A versus B 2.2.1.    A > B (means that it’s A) 2.2.2.    A < B (means that it’s B) 2.3.    12AB = bcdD (means that it’s one of the missing, which is either 3 or 4 and lighter or C and heavier) We put 3 versus 4 1.3.4.    3 > 4 (means that it’s 4) 1.3.5.    3 < 4 (means that it’s 3) 1.3.6.    3 = 4 (means that it’s C) 3.    1234 = ABCD (means that it’s one of the abcd and is heavier or lighter). We put 12AB versus bcdD 3.1.    12AB > bcdD (means it’s either b or c or d and lighter) We put b versus d 3.1.1.    b > d (means it’s d) 3.1.2.    b < d (means it’s b) 3.1.3.    b = d (means it’s c) 3.2.    12AB < bcdD (means it’s either b or c or d and heavier) We put b versus d 3.2.1.    b > d (means it’s b) 3.2.2.    b < d (means it’s d) 3.2.3.    b = d (means it’s c) 3.3.    12AB = bcdD (means it’s a lighter or heavier) 3.3.1.    No solution for the weight of a… We then can make the following steps: a) 1234 versus ABCD b) 12AB versus bcdD c) 1A3b versus 2B4c, where the third step is the combination of all the above mentioned third steps. So, if we called ">" the case the left to be heavier than the right, "<" the opposite case and "=" the equality, we would have the following: 1) >>> gives 1 heavier 2) >>< gives 2 heavier 3) >>= gives D lighter 4) ><> gives B lighter 5) ><< gives A lighter 6) >=> gives 3 heavier 7) >=< gives 4 heavier 8) >== gives C lighter 9) <>> gives A heavier 10) <>< gives B heavier 11) <<> gives 2 lighter 12) <<< gives 1 lighter 13) <<= gives D heavier 14) < => gives 4 lighter 15) <=< gives 3 lighter 16) <== gives C heavier 17) =>> gives d lighter 18) =>< gives b lighter 19) =>= gives c lighter 21) =<> gives b heavier 22) =<< gives d heavier 23) =<= gives c heavier 23) == gives a but not if heavier or lighter I guess there is a combination that gives the right solution but I cannot figure it now. I give up. Panagiotis Monday, April 18, 2005 The probable combinations are 3^3=27. we apparently want 24 (12 coins * 2 (heavier or lighter)). Three combinations are inacceptable ><=, <>= and another one because they give contradictory results. ==> and ==< give such results. Panagiotis Monday, April 18, 2005 If on turn 1: ABCD = 1234 then on turn 2: weigh ABC ? abc if ABC > abc, then a or b or c is heavy so weigh b ? c to find out which if ABC < abc, then a or b or c is light so weigh b ? c to find out which If ABC = abc, then d is heavy or light so weigh A ? d to find out if it is heavy or light WanFactory Tuesday, April 19, 2005 Oh wait, never mind my solution is not deterministic, ignore above post WanFactory Tuesday, April 19, 2005 I think I've got it: (label the balls, 0123456789AB) round 1: 1234 vs 5678 round 2: 1678 vs 59AB round 3: 1269 vs 037A the balance on any round will be (L)eft heavy, (R)ighty heavy, or (B)alanced. This gives 27 possible triplets of results, 3 of which should be impossible, the remaining 24 of which will pick out a ball and identify it as heavy or light. Havent done all the details but it looks ok so far WanFactory Thursday, April 21, 2005 I must confirm that your solution is correct, giving the following results: I must tell you that I envy you that you found it... Bouhou LLL    1heavy LLR    impossible LLB    5light LRL    7light LRR    6light LRB    8light LBL    2heavy LBR    3heavy LBB    4heavy RLL    6heavy RLR    7heavy RLB    8heavy RRL    impossible RRR    1light RRB    5heavy RBL    3light RBR    2light RBB    4light BLL    Alight BLR    9light BLB    Blight BRL    9heavy BRR    Aheavy BRB    Bheavy BBL    0light BBR    0heavy BBB    impossible Panagiotis Monday, April 25, 2005 heres another solution, i think, using 1-12 1 2 3 4 v 5 6 7 8 1 4 5 9 v 2 6 11 12 3 7 9 12 v 1 2 6 10 with the solutions: flat    flat    left        10 is light flat    flat    right        10 is heavy flat    left    flat        11 is light flat    left    left        9 is heavy flat    left    right        12 is light flat    right    flat        11 is heavy flat    right    left        12 is heavy flat    right    right        9 is light left    flat    flat        8 is light left    flat    left        3 is heavy left    flat    right        7 is light left    left    flat        4 is heavy left    left    left        6 is light left    left    right        1 is heavy left    right    flat        5 is light left    right    right        2 is heavy right    flat    flat        8 is heavy right    flat    left        7 is heavy right    flat    right        3 is light right    left    flat        5 is heavy right    left    left        2 is light right    right    flat        4 is light right    right    left        1 is light right    right    right        6 is heavy i hope... flange Thursday, May 26, 2005 I heard this problem a long time ago, but it was with 13 balls.  1 was corrupt (i.e. heavier or lighter).  It can be done in 3 weighings, but you cannot determine in all cases whether the ball is heavier or lighter. Adam Freund Sunday, June 12, 2005 general solution to the classic weighing problem in general if you know either the coin is heavier or lighter you can find the coin out in n weighings among  3^n coins (at the maximum). (note: if the number of coins falls between 3^(n-1) and 3^n you would still require n weighings) however if you just know its a counterfeit one i.e you do not know if its heavier or lighter you can find out the countefeit coin in n weighings among (3^n - 3)/2 coins. (note: if the number of coins falls between (3^(n-1)-3)/2 and (3^n - 3)/2 you would still require n weighings) can anyone prove either of the above mathematically ..if so please mail me the solution. Abyss Wednesday, June 15, 2005   Fog Creek Home