Wednesday, March 23, 2011

The Counterfeit Coin You are given 12 golden coins, though you know that one of them is a counterfeit. The counterfeit coin can be detected because it does not weigh completely the same the others. But at the moment you don't know which coin it is, nor do you know whether it will be lighter or heavier.

Unfortunately, all you have is a scale of the classical type. It is the kind where there are two balanced dishes. By putting objects in, the scale will indicate that one side is heavier than the other (the dish will hang lower) or that each side weighs the same.

How can you find the counterfeit coin by only weighing three times? And is the coin lighter or heavier than the others?

Solution
Allright! The first step is not to put 6 coins on each side. Sure, then we'll know that the counterfeit coin is in one of those groups of 6, but err... we already knew that.

So what we are going to do here is number the coins 1 to 12, and create a ‘tree’ of the different weighings. See, the outcome of every weighing determines your next move. The full tree encompasses every scenario. Don't be put off by its length, just start at the top and reason through!

Weigh 1,2,3,4 against 5,6,7,8.
• They weigh the same.
Good! This is the easy scenario. The coin must be in 9,10,11,12. What you want to do now is weigh 9,10,11 against 1,2,3.
• They weigh the same.
Then 12 must be the counterfeit. You have one weighing left to determine whether it is lighter or heavier: weigh it against any other coin to find out.
• 9,10,11 is heavier.
So any of those must be the counterfeit, and it will always be heavier than the others. Weigh 9 against 10.
• They are the same.
11 must be the counterfeit.
• 9 is heavier.
Then 9 is the counterfeit.
• 10 is heavier.
Then 10 is the counterfeit.
• 9,10,11 is lighter.
So any of those must be the counterfeit, and it will always be lighter than the others. The procedure is the same as above! Weigh 9 against 10.
• They are the same.
11 must be the counterfeit.
• 9 is lighter.
Then 9 is the counterfeit.
• 10 is lighter.
Then 10 is the counterfeit.
• 5,6,7,8 is heavier.
The coin can be on either side. You must weigh 1,5,6 against 2,7,8.
• They are the same.
Then coin 3 and 4 are the only possibilities left. Weigh one of those, like 3, against a known valid coin, such as 9.
• They are the same.
Then the unweighed coin, number 4, is the counterfeit. From the first weighing you can tell whether it is heavier or lighter.
• 9 is heavier.
Coin 3 is the lighter counterfeit.
• 9 is lighter.
Coin 3 is the heavier counterfeit.
• 2,7,8 is heavier.
Argh, now it gets really complex. What this means is that either 7 or 8 is the heavier counterfeit, or 1 is the lighter counterfeit. Knowing that, just weigh 7 against 8.
• They are the same.
Then 1 is the counterfeit.
• 7 is heavier.
Then 7 is the counterfeit.
• 7 is lighter.
Then 8 is the counterfeit.
• 1,5,6 is heavier.
Either 5 or 6 is the heavier counterfeit, or 2 is the lighter counterfeit. In the same way as above, weigh 5 against 6.
• They are the same.
Then 2 is the counterfeit.
• 5 is heavier.
Then 5 is the counterfeit.
• 5 is lighter.
Then 6 is the counterfeit.
• 1,2,3,4 is heavier.
Weigh 1,2,5 against 3,4,6. In other words go through it similarly as above!