The 12-coin problem

Remember the 12 – coin problem? Here’s the solution to the problem (click). The solution looks random as though a lot of trial and error is involved in it. Let me discuss something about the solution. All this, I admit, came to my mind only AFTER I found the solution although I should’ve thought of this before. There were 12 coins. Given: one and only one of them is defective. What is the possible number of situations in the problem? Any one of the 12 coins could be defective. It could be either heavier or lighter. (Since all the coins have the same weight and it is known that only one coin is defective, ‘heavier’ and ‘lighter’ can be uniquely defined as possible situations). So, there are total 12X2 = 24 possible situations.

Each measurement on the balance may give us 3 possible outcomes. (‘Left’ heavy, ‘Right’ heavy, both equal). Three rounds of measurements, thus give 3X3X3 = 27 possible sets of outcomes. Thus the number of possible sets of outcomes is more than the possible number of situations. Hence, three sets of measurements are sufficient to solve the question. (Maybe, that’s a necessary condition and not a sufficient condition.)

How would we start measurements? For the first measurement we should have equal number of coins in both the pans. Some of the coins may be left aside. Let us say we have n coins on each pan for the first weighing, and m (=12-2n) coins are lying aside. What happens if the balance is level? It indicates that the faulty coin must lie among the m coins left aside. We have no other information. So the problem changes to m coins and two measurements. Each of the m coins can be faulty in two different ways. Hence there are 2m possible situations. From 2 rounds of measurements we can have 3X3 = 9 possible set of outcomes. And from the same logic: 2m<=9.Hence,m<=4.

What if one of the pans (say the right one) goes heavier in the first measurement? Then we know that the faulty coin is either in the left pan or in the right pan. If it’s in the left it must be light; and if it’s in the right it must be heavy. Hence, we again have 2n possible situations and 3X3 = 9 possible outcomes. Again, n<=4. These two conditions give the solution: m = n = 4. Hence, we must take 4 coins on each pan in the first measurement.

What for the second measurement? Let’s say the pans did not balance in the first measurement. Now, we have 8 suspect coins here. Suppose we take p suspect coins on the pans and q (=8-p) are left aside. Note that we may use some unsuspected coins too on the pan. If it balances, we would have only one measurement left to find out the faulty one among the q coins. q possible situations (why not 2q ?) and 3 outcomes. q<=3. If it does not balance, there is one faulty coin among p coins (nature of fault already known). But now we have some extra information about these p coins, so we can no longer apply this logic.

Let’s now say the pans balanced in the first measurement. We have four suspects. Suppose we take x suspect coins on pans and q are left aside. If it balances, any of the q coins may either be light of heavy. So, there are 2q possible situations and 3 outcomes. Hence, 2q<=3. It means q=0 or 1.

Further than that, the condition depends on the output of the second measurement. But we can still apply the logic of unknowns vs equations available for the next measurement.