Problem 15. Finding the Broken Machine
We have ten coin maker machines each of which produces 10 gram coins. One of the machines is broken and instead of 10 gram coins, it produces 9 gram coins. We have a digital scale and we want to find the broken machine by using it only once. At least how many coins should we produce for this purpose? What if we could use the scale twice?
Each time we use the scale, we can weigh any combination of coins produced by different machines. Each machine can make as many coins for us as desired. For example, we can put 10 coins from the first machine, 12 coins from the second machine, 1000 coins from the third machine, and so on. We can then put them on the scale and calculate the total weight of all coins produced.
Link to the problem on Twitter: https://twitter.com/Riazi_Cafe/status/1679741266786144257
. The answer to the first part is 45 and the answer to the second part is 13.
First part: If only one weighing is allowed, we should make an identical number of coins from each machine so that after the weighing we can realize which machine is broken. Thus the smallest number of coins we need is \(0+1+2+\ldots+9\) which is equal to 45.
Second part: If we can use the scale twice, the minimum number of coins required is 13. There are two strategies that make this possible for us. Below is how we put the coins on the scale in the first round of these strategies:
Strategy 1. Put no coin from 3 machines (subset \(A\)), one coin from 4 machines (subset \(B\)), and 2 coins from 3 machines (subset \(C\)).
Strategy 2. Put no coin from 4 machines (subset \(A\)), one coin from 5 machines (subset \(B\)), and 2 coins from 1 machine (subset \(C\)).
In each case, we narrow down the search to a subset of machines after the first weighting and then we use the exact same strategy of the first part to pinpoint the broken machine. The only difference is that we can reuse the already produced coins of the first step.
For example, in the first strategy, if we find out with the first weighting that the broken machine belongs to subset \(B\) (the machines that produced one coin), then in the second round there are 4 candidates left. We then need 0,1,2, and 3 coins from them for the second round and since we can reuse one coin for each of them from the previous round, we only need \(3\) extra coins. The rest of the cases are the same. Table below explains how we proceed in both strategies after the first weighing:
| broken machine in set \(A\) | broken machine in set \(B\) | broken machine in set \(C\) | |
|---|---|---|---|
| 0, 1, and 2 | 0, 1, 2, and 3 | 0, 1 , 2 | |
| Strategy 1 | coins for machines of set \(A\) | coins for machines of set \(B\) | coins for machines of set \(C\) |
| (3 new coins) | (3 new coins) | (no new coins) | |
| 0, 1, 2, and 3 | 0, 1, 2, 3, and 4 | ||
| Strategy 2 | coins for machines of set \(A\) | coins for machines of set \(B\) | no weighing required |
| (6 new coins) | (6 new coins) |
Link to the solution on Twitter: https://twitter.com/Riazi_Cafe/status/1681197786795220997