You are given 12 identical-looking coins, one of which is counterfeit and weighs slightly more or less (you don't know which) than the others. You are given a beam balance which lets you put the same number of coins on each side and observe which side (if either) is heavier. How can you identify the counterfeit and tell whether it is heavy or light, in 3 weighings?

More generally, you are given N coins, one of which is heavy or light. How many weighings do you need? What if you only want to know which is the counterfeit, and don't care if it is lighter or heavier? What if you have one coin that you know to be good? What if you already know that the counterfeit is lighter or heavier? What if you are being lied to about one of the weighing results?