There are 12 coins. One of them is fake: it is either lighter or heavier than a normal coin. Find the fake coin and tell if it is lighter or heavier by using a balance the minimum number of times possible.
There are 24 different potential answers: any of the 12 coins could be the fake, and the fake could be either heavier or lighter. Each time we use the balance, we have three different possible answers: the left cup weighs less/equal/more than the right cup. Hence, by using the balance twice, we can anticipate 9 different outcomes; and by using it three times — 27 different outcomes. Therefore, we can't do the problem in two steps, although we can try to do it in three steps.
We will try to arrange each use of the balance in such a way that the answers are divided into three equal (or nearly equal) groups. So the first weighing should be four coins in the left cup and four coins in the right cup. If the left cup weighs less than the right cup, then we have 8 potential outcomes for the right answer: the fake coin is one out of the four on the left, and it is lighter, or the fake coin is one out of the four on the right, and it is heavier. Similarly, we have 8 potential outcomes in each of the other two cases.
Suppose the left cup is lighter than the right cup. Let us denote the left coins as coins 1, 2, 3, and 4 and the right coins as 5, 6, 7, and 8. For the next step, we should divide the 8 potential answers into groups of 3, 3 and 2. For example, we want to have three answers in the case when the left cup is lighter or equal to the right cup, and 2 answers when the left cup is heavier than the right cup. That means that 3 out of the 8 coins should be left in the same place that they started, 3 should be taken away, and 2 should change places. We may use coins 9, 10, 11, and 12 to supplement each weighing, in order to have an equal number of coins in each cup. For example, we can leave coins 1, 2, and 5 in their places, coins 3, 4 and 6 can be removed from the balance, and coins 7 and 8 can change cups. In this case, we need to add three good coins, so our second weighing is: 1, 2, 7, and 8 in the left cup; and 5, 9, 10, 11 in the right cup. If the cups are equal, then the fake coin will be found among 3, 4 or 6. If the left cup is lighter, then the fake coin is among 1, 2, and 5, and if the left cup is heavier, then the fake coin is among 7 or 8, and for each number we know if it is heavier or lighter.
Finishing the problem and considering other such cases is left to the reader.
Last revised June 2009