Question

Given 12 coins, with possibly (but not necessarily) one coin being counterfeit (heavy or light). You have a comparison scale and you want to determine the fairness of all with a minimum number of comparisons.

(a) Give the procedure to identify the false coin or to show all are fair.

Answer 1

This problem has more than one solution. To determine the fairness of all with a minimum number of comparisons make three groups of 4 coins each and then follow the below procedure(here we are performing for the heavier coin)

• Four coins are put on each side. There are two possibilities:

1. One side is heavier than the other. If this is the case, remove three coins from the heavier side, move three coins from the lighter side to the heavier side, and place three coins that were not weighed the first time on the lighter side. (Remember which coins are which.) There are three possibilities:

1.a) The same side that was heavier the first time is still heavier. This means that either the coin that stayed there is heavier or that the coin that stayed on the lighter side is lighter. Balancing one of these against one of the other ten coins reveals which of these is true, thus solving the puzzle.

1.b) The side that was heavier the first time is lighter the second time. This means that one of the three coins that went from the lighter side to the heavier side is the light coin. For the third attempt, weigh two of these coins against each other: if one is lighter, it is the unique coin; if they balance, the third coin is the light one.

1.c) Both sides are even. This means that one of the three coins that was removed from the heavier side is the heavy coin. For the third attempt, weigh two of these coins against each other: if one is heavier, it is the unique coin; if they balance, the third coin is the heavy one.

2. Both sides are even. If this is the case, all eight coins are identical and can be set aside. Take the four remaining coins and place three on one side of the balance. Place 3 of the 8 identical coins on the other side. There are three possibilities:

2.a) The three remaining coins are lighter. In this case you now know that one of those three coins is the odd one out and that it is lighter. Take two of those three coins and weigh them against each other. If the balance tips then the lighter coin is the odd one out. If the two coins balance then the third coin not on the balance is the odd one out and it is lighter.

2.b) The three remaining coins are heavier. In this case you now know that one of those three coins is the odd one out and that it is heavier. Take two of those three coins and weigh them against each other. If the balance tips then the heavier coin is the odd one out. If the two coins balance then the third coin not on the balance is the odd one out and it is heavier.

2.c) The three remaining coins balance. In this case you just need to weigh the remaining coin against any of the other 11 coins and this tells you whether it is heavier, lighter, or the same.

* If in both cases we find no coin is false implies all coins are fare.

* The procedure is same to find the false lighter coin (if any).

The following table gives the formula for different conditions :

Known	Goal	Maximum Coins for n weighings	Number of Weighings for c coins
1). Whether target coin is lighter or heavier than others	Identify coin
2). Target coin is different from others	Identify coin
3). Target coin is different from others, or all coins are the same	Identify if unique coin exists, and whether it is lighter or heavier

For this case our target is third one, therefore, no of weighings will be log₃(20 +3)= 2.85( Say 3).