Suddenly a stern knock on Dr Eccos door and in walked Michae

Suddenly a stern knock on Dr. Ecco\'s door, and in walked Michael Monetary. The man worked inside the government and was in charge of a coin factory. He stated his problem: \"one of my coin making machines is not working properly. It produces coins in batches of 15, exactly one out of every batch has an incorrect weight. The first coin from a batch is always perfect, the second coin, if of incorrect weight, is too heavy, and otherwise the bad coin could end up being heavier or lighter than it\'s supposed to be. I would like my workers to quickly find and remove the bad coin from each batch using a regular pan balance in 3 weighings. Anymore weighings and I will surely lose my job over production losses. Finally, Iwould like to keep track of the bad coins being too heavy or to light, this statistic could help fix the machine. After a few minutes Ecco handed Mr. Monetary a scrap of paper and said there is your solution in three weighings, it\'s a good thing the first coin from each batch is always perfect. ?O How did Ecco solve Mr. Monetary\'s problem? Your solution must be non-adaptive and comectly identify the bad coin as too light or too heavy. Also Label G as the (first coin that is always perfect. Label Has the (second) coin that could be too heavy but not too light. Label the other coins: 1,2,3 13 Counterfeit How the Scale Responds 10 11 12 13

Solution

Number the coins from 1 to 15 and assume that coin 1 is marked as genuine. Now divide them into 3 groups [1 - 5], [6 -10] and [11 - 15].

First, weight [1 - 5] against [6 - 10]. If they have the same weight, all of the coins from 1 to 10 are genuine. Figuring out the fake coin among balls 11 to 15 is not hard. (weighing [1 - 3] against [11 - 13] in the second trial this case.)

Now, consider the case [1 - 5] and [6 - 10] do not have the same weight. Then coins 11 to 15 are genuine. Without loss of generality, assume that [1 - 5] is heavier than [6 - 10]. For the second trial, weight [3, 4, 5, 6, 7, 8] against [1, 11, 12, 13, 14, 15]. Note that the second group contains all genuine coins here.

If the scale is balanced, coins 3 to 8 are also genuine and we are left with coins 2, 9, 10. Now weight [2, 9] against [1, 3]. If the scale is balanced against,coin 10 is fake and is lighter than normal. If [2, 9] is heavier than [1, 3], 2 is fake and is heavier than normal. If [2, 9] is lighter than [1, 2], 9 is fake and is lighter than normal.

If [3 - 8] is heavier than [1, 11 - 15], the fake coin must be among 3, 4, 5 and is heavier than normal. It\'s easy to figure out which one is fake with the last trial. Similarly, if [3 - 8] is lighter than [1, 11 -15], the fake ball must be among 6, 7, 8 and is lighter than normal. Again, it\'s easy to figure out which one is fake with the last trial.