Aladim has ten bags of coins, each containing only real coins or only fake coins. Each real coin weighs $10 \mathrm{~g}$ and each fake coin weighs $1 \mathrm{~g}$.

![](https://cdn.mathpix.com/cropped/2024_05_01_30c9a294a58a6e4b8190g-035.jpg?height=268&width=277&top_left_y=1228&top_left_x=1598)

(a) Suppose that each bag contains exactly ten coins and that only one of the bags contains fake coins. Using a scale and performing only one weighing, how should Aladim proceed to determine which bag contains the fake coins?

(b) Suppose that the bags are full of coins and that Aladim does not know how many of these bags contain fake coins. How can he identify, with only one weighing, the bags that have fake coins?
(a) Aladim must withdraw a different number of coins from each bag, as follows. First, he withdraws one coin from the first bag, then two from the second, then three from the third, and so on, until the last bag, from which he withdraws ten coins. In total, \(1+2+3+4+5+6+7+8+9+10=55\) coins are withdrawn and placed on the scale. If all these coins were genuine, they would weigh a total of \(55 \times 10=550\) grams. However, since some are fake, the weight will be less. If one gram is missing, it means there is only one fake coin, and therefore the first bag is the one being sought. If two grams are missing, it means there are two fake coins, and therefore the second bag is the one being sought, and so on.

(b) Let's see that, in general, a solution attempt like the previous one does not allow the identification of the bags with fake coins. Suppose Aladim had withdrawn one coin from the first bag, two coins from the second, and so on, until the last bag, from which he withdrew ten coins. If there were two or more bags with fake coins, the procedure of weighing these 55 coins could be inconclusive. For example, if in the weighing of the 55 coins, 7 grams were missing, that is, 7 fake coins were weighed. In this case, there could be fake coins in bags 1 and 6, or fake coins in bags 2 and 5, or fake coins in bags 1, 2, and 4, etc. That is, proceeding in this manner, it is not possible to identify which are the bags of fake coins.

To solve this problem, he can proceed in another way, as follows. First, he withdraws one coin from the first bag, then two coins from the second, then four from the third, eight from the fourth, sixteen from the fifth bag, and so on, always doubling the number of coins withdrawn from each bag. In this way, a total of

$$
1+2+4+8+16+32+64+128+256+512=1023
$$

coins are withdrawn, which together would weigh \(10230 \text{ grams}\) if all the coins withdrawn were genuine. The difference between the actual weight obtained from the weighing of these 1,023 coins and their ideal weight of \(10230 \text{ grams}\) indicates the number of fake coins weighed and in which bags they are. Let's see this through a numerical example. Imagine that \(10125 \text{ grams}\) were obtained in the weighing, that is, \(10230-10125=105 \text{ grams}\) were missing, which correspond to the number of fake coins. Subtracting, successively, the numbers corresponding to the coins withdrawn from each bag, always starting from the largest number less than 105, we have \(105-64=41, 41-32=9, 9-8=1\), that is, \(105=1+8+32+64\). From this result, Aladim can conclude that 1, 8, 32, and 64 fake coins were withdrawn from the first, fourth, sixth, and seventh bags.

Now, let's justify, in a more formal way, the reasoning developed in the numerical example. Let \(p\) be the weight obtained from the weighing of the 1023 coins withdrawn. The difference \(10230-p\) is the number of fake coins withdrawn from the bags. By performing successive divisions by 2, it can be proven that any positive integer can be written, in a unique way, as a sum of distinct powers of 2. Indeed, this is what provides the theoretical justification for the binary expansion, or base 2 expansion, of natural numbers. In our case, this implies that

$$
10230-p=1 \times a_{0}+2 \times a_{1}+2^{2} \times a_{2}+2^{3} \times a_{3}+\cdots+2^{9} \times a_{9}
$$

where each of the numbers \(a_{0}, a_{1}, a_{2}, a_{3}, \ldots, a_{9}\) is 0 or 1.

From each bag, quantities of coins that are powers of 2 were withdrawn, and each bag either contains only fake coins or contains only genuine coins, that is, in the same bag, there do not exist both types of coins. Therefore, if any of these numbers, say \(a_{j}\), is 1, then \(2^{j}\) fake coins were withdrawn from bag \(j+1\); on the other hand, if the number \(a_{j}\) is 0, then \(2^{j}\) genuine coins were withdrawn from bag \(j+1\).