I recently came across this puzzle:

There are 12 coins, all identical in appearance, and all identical in weight except for one, which is either heavier or lighter than the remaining 11 coins. Determine which is the counterfeit coin in only 3 weighings with a balance scale.

After struggling with this, both mentally and using pencil and paper, I decided to write a web page to simulate the problem; it can be found here. You may find it interesting to attempt this puzzle there before reading the discussion below.

Simplifying the puzzle, we will first attempt two simpler problems; these will help us in formulating the answer to the original problem.

First, we will solve the problem for 3 coins when we know whether the fake coin is lighter or heavier. We can establish the fake by weighing any two coins against each other. If they do not balance then the fake is the lighter (or heavier if the counterfeit is known be heavier) of the two; if they balance then the fake is the remaining coin. We will refer to this as as Solution 1.

We can now find the solution for 3 coins when we do not know whether the fake coin is heavier or lighter than the genuine coins. This quickly reveals that only 2 weightings are necessary, one to establish a good coin and one to determine the weight of the counterfeit. Weigh coin 1 against coin 2. There are two possibilities:

- The coins balance. This means that coin 3 is counterfeit. Weigh it against coin 1 to determine whether it is lighter or heavier.
- The coins do not balance. This means that coin 3 is a genuine coin. Weigh the lighter coin against coin 3. If they balance then the heavier coin is the fake. If they do not balance then the lighter coin is the fake.

We will refer to this as Solution 2.

Solution 2 can be extended to any number of coins which are a multiple of 3. If we can separate the coins into 3 equal groups we can apply this procedure to determine which group contains the counterfeit coin and whether it is lighter or heavier than a genuine coin.

For example, if we have 6 coins we can allocate them into 3 groups each containing 2 coins. Using the above procedure we can establish which group contains the counterfeit coin and whether it is lighter or heavier than the genuine coins. We can then weight the 2 coins in this group against each other to establish which is the counterfeit.

If we have 9 coins we can separate them into 3 groups of 3. Having established which group contains the counterfeit coin and whether it is lighter or heavier we can discard the other two groups. We can then use Solution 1 to solve this problem.

Extending this procedure to 12 coins we can determine that the counterfeit coin is one of a group of 4 and whether it is lighter or heavier. However, we cannot then determine which of the 4 is the counterfeit using our one remaining weighing.

After much experimentation I finally came up with this solution. Place 4 coins on each side of the balance. There are two possibilities:

- The two sides balance. This means that the counterfeit coin is one of the remaining 4. Balance 3 of these suspect coins against 3 known good coins.
- The two sides balance. This means that the counterfeit is the remaining coin. Balance it against a known good coin to establish whether it is lighter or heavier.
- The two sides do not balance. The counterfeit coin is one of these 3 and it is lighter or heavier as indicated by the weighing. Use Solution 1 to get the answer.

- The two sides do not balance. This means that the counterfeit coin is one of these 8, but we have established that the remaining 4 coins are genuine
- Remove three of the suspect coins from the heavier side. Move three of the coins from the lighter side to the heavier side and replace them on the lighter side by three known good coins.
- The two sides balance. This means that the counterfeit coin is one of the three that were removed from the heavier side (and it is heavier). Use Solution 1 to get the answer.
- The two sides still do not balance and the lighter side is still the side that was lighter on the last weighing. This means that the fake coin is either the coin that remained on the light side or the coin that remained on the heavy side. We can weigh one of these coins against a known good coin, if they do not balance then this is the fake coin else it is the other one.
- The two sides still do not balance but the side that was heavier is now lighter. This means that the fake coin is one of the three coins that was moved and that it is lighter. Use Solution 1 to get the answer.

Comprehensive solution.

Is there a way of using three weighings without the weighings depending on the previous results?