## Solutions to the coin weighing problems

In an earlier post, we posed two problems to do with weighing coins. Here are the solutions…

1. In this problem the key is that the weighing machine tells exactly the weight of the object it is weighing; 363 is a a red herring though neither red nor a fish: the important thing is to have more at least one hundred coins in each bag. So put on the weighing machine one coin from the first bag, two coins from the second bag, and so on, till you put a hundred coins from the hundredth bag. If the coins are all genuine, the weighing machine will tell you that the total weight is

$10\times (1+ 2 + \cdots+100) = 50500 \hbox{ grams}.$

But since one bag contains coins that are lighter, the weight the machine shows is $x<50500$, and the bag that contains the counterfeit coins is the $(50500-x)$-th one.

2. Here please note that we have a scale balance and so can only know whether what is in the right pan is heavier, lighter, or equal in weight to what is in the left one. It seems obvious that the first weighing should be of three coins against another three: if we do two against two, and they all weigh the same, we seem to be sunk, and doing four against four does not seem promising if the weights in the two pans are different.

Weighing three against three raises two possibilities: either (a) they all weigh the same or, without loss of generality, (b) the right pan is heavier than the left. Case (b) is harder, so let us first deal with (a).

(a) Here, clearly, the fake coin is one of the four we have not yet weighed. So let us put two of those in the right pan and weigh them against two of the necessarily genuine coins we weighed at the first weighing. If the right pan goes down, it means that the fake coin is heavier than the genuine ones. So for the third weighing just weigh one of the coins in the right pan against a genuine coin and we are done. Similarly, if the right pan goes up. Note that in this case we know whether the fake coin is heavier or lighter than the genuine one. Something interesting happens if in the second weighing the pans are of equal weight. This means that the fake coin is one of the remaining two that have never been weighed. In that case, we just take one of them and weigh it against a genuine coin. It it is heavier or lighter than a genuine coin, we know that it is a fake one. On the other hand, if it weighs the same as a genuine coin, we know that the single remaining unweighed coin is the fake one but we do not know if it is heavier or lighter!

(b) Let us call the three coins in the right pan $H_1, H_2, H_3$ and the three coins in the left one, $L_1, L_2, L_3$. The tricky weighing is the second one, and by trial and error (i.e. by seeing that you run out of weighings to test all the coins), one eventually sees that the way to proceed is to weigh, say, $H_1, H_2, L_1, L_2$ against the remaining four yet unweighed coins which are necessarily genuine. Clearly, if the pans are level, the only possibility is that the fake coin is either $H_3$ or $L_3$, and we simply weigh one of them against a genuine coin. Note that again we will know whether the fake one is heavier or lighter than the genuine ones. If the pan of $H_1, H_2, L_1, L_2$ goes up, it means that the fake coin is either $L_1$ or $L_2$ and again we clinch the issue by weighing one of them against a genuine coin, and similarly, if the pan goes down, which narrows the identity of the fake coin to $H_1$ or $H_2$.

Two remarks. In case (b) we always knew whether the fake coin was heavier or lighter than a genuine one, but this is not the case in one of the sub-cases of (a). Is there a solution for (a) that also supplies this information? Another question is this: what is the largest number of coins we can test for genuineness in 3 weighings?

(MG)