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