EC4 Describe the algorithm which in 3 comparisons with lever

EC4. Describe the algorithm which in 3 comparisons with lever scales finds among 12 coins a single false coin (which is different from standard in weight) and also finds if the false coin is lighter or heavier than a standard

Solution

Let\'s number the coins for our convenience: {1,2,3,4,5,6,7,8,9,10,11,12} Let\'s say we weigh {1,2,3,4} and {5,6,7,8} first. Now 3 cases would arise: 1) Both have same weight: Now we know, the defective coin is in lot {9,10,11,12}. But, if you will simply weigh you won\'t be able to tell it is lighter or heavier. So, take one of the non-fake coins that you already know, say 8. We weigh {8,9} and {10,11} now ..leaving out 12. SubCase 1: If {8, 9} is heavier, then either 9 is heavy or 10 is lighter or 11 is lighter. Weigh {10} and {11}. If they balance, 9 is false coin (heavier). If they don’t balance then whichever one is lighter is false coin (lighter) SubCase 2: If {8, 9} is lighter, then either 9 is light or 10 is heavy or 11 is heavy. Weigh {10} and {11}. If they balance, 9 is fake (lighter). If they don’t balance then whichever one is heavier is fake (heavier). Case 2: If {1,2,3,4} is heavier, we know either one of {1,2,3,4} heavier or one of {5,6,7,8} is lighter. Now, it is guaranteed that {9,10,11,12} are not fake. Weigh {1,2,5} and {3,6,9} ( Here, 9 is not fake - just like earlier we are using it) If they balance, then either 4 is heavy or 7 is light or 8 is light. Following the last step from the previous case, we weigh {7} and {8}. If they balance, 4 is fake(heavier). If they don’t balance then whichever one is lighter is fake (lighter). If {1,2,5} is heavier, then either 1 is heavy or 2 is heavy or 6 is light. Weigh {1} and {2}. If they balance, 6 is fake (lighter). If they don’t balance then whichever one is heavier is fake (heavier). If {3,6,9} is heavier, then either 3 is heavy or 5 is light. Weigh {5} and {9}. They won’t balance. If {5} is lighter, 5 is fake (lighter). If they balance, 3 is fake (heavier). Case 3: If {5,6,7,8} is heavier, it is the same situation as if {1,2,3,4} was heavier. So, the algorithm would go on the following lines: 1. Take two N/3 parts and weigh them . // N is the size = 12 2. if(weight same) //defective coin is in remaining N/3, let\'s call this array R weigh ( R[0], known non-fake) and (R[1],R[2]) if(R[0], known non-fake heavier) => R[0] heavy or R[1] light or R[2] light. weigh R[1] and R[2] if (same weight) return R[0] heavier; else if R[1] lighter return R[1] lighter; else return R[2] lighter; else => R[0] is light or R[1] is heavy or R[2] is heavy .. // do it similarly 3. else // weight different, now R has non-fake elements //let\'s call first array P and second array Q if (P heavier) => either defective coin is in P and is heavier or it is in Q and lighter. Weigh (P[0],P[1],Q[0]) and (P[2],Q[1], non-fake) if (same weight) => either P[3] heavy or Q[2] light or Q[3] light weigh Q[2] and Q[3] if (same weight) return P[3] heavier else if Q[2] lighter return Q[2] lighter else return Q[3] lighter else if((P[0],P[1],Q[0]) heavier) => either P[0] heavy or P[1] heavy or Q[0] Light Weigh P[0] and P[1] //elements of same group if (same weight) return Q[0] lighter else if P[0] heavier return P[0] heavier else return P[1] heavier. else ... // P[2],Q[1], non-fake are heavier , .. do it the same way else ... //case 3