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.