Problem Suppose you have twelve golden coins all the same in

Problem: Suppose you have twelve golden coins, all the same in shape and size. However, one of them is fake: it does seem golden from the outside, but its core is made of a cheaper material. so its weight differs from the weight of others (all the others weigh equally). Using the scales as in the picture below, and taking at most three measurements. how can you find which coin is fake AND whether it is lighter or heavier than the others? You need to describe a procedure/algorithm so that whatever happens in each of the three measurements, the procedure will in any case lead to the answer.

Solution

Of 12 coins, one is counterfeit and weighs either more or less than the other coins. Using an old-fashioned balance with two scales, and performing only three measurements, you have to find out which coin is counterfeit, and whether it is lighter or heavier then the other coins. How would you do that? The basic idea of this solution is to perform the three measurements, look at the result of each measurement, and then look at the way each coin has participated in the measurements to identify the only coin that could have caused this particular combination of results. For instance, if the three results are: equal (0), right side heavier (R), left side heavier (L), or, in short, 0RL, then it must have been the coin that was not in the first measurement, on the right in the second measurement, on the left in the third measurement, and that coin is heavier than the others, or (mirrored) the coin that was not in the first measurement, on the left in the second measurement, on the right in the third measurement, and that coin is lighter than the others. Note how the measurement result 0RL and the participation of a heavier coin in the measurements coincide. So all we have to do is to distribute the 12 coins over the scales of the three measurements in such a way that no coin participates in the three measurements in the same way (or mirrored) as any other coin. The distribution below is one of many possible distributions that fulfills this requirement: 1, 2, 7, 10 against 3, 4, 6, 9 1, 3, 8, 11 against 2, 5, 6, 7 2, 3, 9, 12 against 1, 4, 5, 8 If the measurements result in 0RL, then it can be seen from this distribution that coin 8 is lighter than the other coins. No other coin can explain the outcome 0RL.