Puzzle‎ > ‎

### 12 coin problem

 you have 12 coins. one of them is counterfeit. all the good coins weigh the same, while the counterfeit one weights either more or less than a good coin. your task is to find the counterfeit coin using a balance-scale in 3 weighs. moreover, you want to say whether the coin weighs more or lessthan is should and, and this is the real kicker, your weighs must be non-adaptive. that is, your choice of what to put on the balance for your second weigh cannot depend on the outcome of the first weigh and your decision about what to weigh for round 3 cannot depend on what happened on either your first or second weigh. for example, you can't say something like "take coin #1 and coin #2 and weigh them. if they balance, then take coins 3,4,5 and weight them against 6,7,8...if 1 and 2 don't balance, then weigh #1 vs #12..." youhave to say something like:round #1: do thisround #2: do thisround #3: do thisif the results are left tilt, balanced, and left tilt, respectively, then coin #11 is heavier than it should be.     Solution:   #1: Divide into 3 bins, A, B, C. Compare A and B. IF[ 4A == 4B ] #1{         A and B are Good, 8G         Take 3 from each G and C        IF[ 3G == 3C ] #2        {                 Take remaining C                IF[ G < C ] C is Heavy #3                ELSE C is Light        }        ELSE IF[ 3G < 3C ] #2         {                 Take 1 EACH from C                 IF[ C1 == C2 ] C3 is Heavy #3                 ELSE IF[ C1 < C2 ] C2 is Heavy                 ELSE C1 is Heavy         }        ELSE IF[ 3G > 3C ] #2         {                 Take 1 EACH from C                 IF[ C1 == C2 ] C3 is Light #3                 ELSE IF[ C1 < C2 ] C2 is Light                 ELSE C1 is Light         } } IF[ 4A < 4B ] #1 {         Rest 4 are Good, 4G         IF[ A1 + B2 + G < A2 + A3 + B1 ] #2         {                 IF[ A1 < G ] A1 is Light #3                 ELSE B1 is Heavy #3         }         ELSE IF[ A1 + B2 + G == A2 + A3 + B1 ] #2         {                 IF[ B3 == B4 ] A4 is Light #3                 ELSE IF[ B3 < B4 ] B4 is Heavy                 ELSE B3 is Heavy         }         ELSE IF[ A1 + B2 + G > A2 + A3 + B1  ] #2         {                 IF[ A2 == A3 ] B2 is Heavy #3                 ELSE IF [ A2 < A3 ] A2 is Light                 ELSE A3 is Light         } } IF[ 4A > 4B ] #1 same as less than condition