Coins and a balance scale

There is an old riddle: "You have twelve coins and a balance scale. One of the coins does not weigh the same as the other eleven, but you don't know if the odd coin is heavier or lighter than the others. How can you determine, in three weighings, which coin is the odd coin?"

With three weighings you can actually find the odd coin in a group of thirteen coins. Every version of this question that I have seen asked about a group of twelve coins, but the maximum is thirteen.

I wrote a computer program to find the minimum number of weighings for thirteen and larger numbers of coins; this was basically a turning point when I realized that I have no life.

Some versions of this problem say that at the end of the three weighings, you have to know which coin is the odd coin and know whether it is heavier or lighter than the others. In that case, twelve coins really is the maximum number of coins that can be solved in three weighings.

Solution

If the two pans are even, then you have five coins left to look at, and you still don't know whether the odd coin is heavier or lighter. Take three of those unknown coins, and three coins from the group of eight that you know are "normal", and weigh those groups of three against each other. If the unknown group of three is heavier, then you know that the coin is one of those three and you know that it's heavier than the rest, so you can easily find it in the last weighing. Similarly if the unknown group of three is lighter.

If the scales balance, then you know the odd coin is one of the last two coins. Take one of those coins and weigh it against one of the ten coins that you know are normal. Then if the scales don't balance, that coin is the odd coin, and if they do balance, the odd coin is the one left over.

Note that in the very last case -- "the odd coin is the one left over" -- you don't know whether the odd coin is heavier or lighter than the rest, since it never touched the balance scale. This is why if you want to find the odd coin in a group of thirteen and determine whether it's heavier or lighter than the rest, then you need four weighings; for that problem, the largest number of coins that can be solved in three weighings is twelve.

Other curiosities about the problem

• Sometimes it makes a difference whether you have an unlimited supply of "normal coins" that you can use in your weighings. For example, if you want to find the fake coin in a group of five coins, and you don't know whether the fake coin is heavier or lighter than the others, you can do it in two weighings if you have at least three other coins that you know are not fake. But if those five coins are all that you have, you need three weighings.
• Thirteen is the smallest number of coins for which the answer to the question depends on whether you need to find out whether the fake coin is heavier or lighter than the rest. (OK, one coin is really the smallest number -- with one coin, you need zero weighings to find the fake coin, but you can never determine whether it's heavier or lighter than a "normal" coin!)
• Frans Faase has a page at
  http://home.wxs.nl/~faase009/Ha12coins.html
  about a different version of the problem, in which you have to state in advance what coins you are going to weigh against each other in each step, before you even start the weighings.