4. Zeus has scales that allow him to find out the weight of the load placed on them, and a bag with 100 coins, among which there are 10-gram and 9-gram coins. Zeus knows the total number $N$ of 10-gram coins in the bag, but it is unknown which ones weigh how much. He would like to make four weighings on the scales and as a result, guaranteed to find at least one 9-gram coin. For what largest $N$ is this possible? (K. Knop)
Answer. For $N=15$. Solution. First, let's outline Zeus's algorithm for $N=15$. By weighing a certain number of coins, he immediately determines the number of heavy coins among the weighed ones. Since he only needs to identify one light coin, he can weigh just 8 coins in the first weighing. If there are light coins among them, he continues to weigh these same coins (and forgets about all the others), otherwise, Zeus concludes that there are no more than seven heavy coins among the remaining coins, and he proceeds to weigh other coins. In any case, on the second weighing, he only needs to weigh four coins, on the third - two, and on the fourth - one.

Now let's prove that the task for Zeus is unsolvable when $N>15$. For this, consider Anti-Zeus, who, after Zeus places some coins on the scales during the first weighing, decides what the weight of these coins will be. Anti-Zeus tries to hinder Zeus, so his actions are as follows:

- if Zeus weighs no fewer than 8 and no more than $108-N$ coins, then Anti-Zeus makes exactly 8 of them heavy;
- if Zeus weighs fewer than 8 coins, then Anti-Zeus makes all these coins heavy,
- if Zeus weighs more than $108-N$ coins, then Anti-Zeus makes all the unweighed coins heavy.

Clearly, when $N>15$, Anti-Zeus achieves the following: no matter how Zeus divides the coins into two groups (weighed/unweighed), in each group consisting of at least 8 coins, there are at least 8 heavy coins.

On the second move, Anti-Zeus acts similarly: now each of the previous groups is divided into two parts (those that participated in the second weighing and those that did not), and Anti-Zeus ensures that in each of the four groups there are at least four heavy coins (or all are heavy if the group has fewer than 4 coins). After the third weighing, Anti-Zeus similarly tracks the 8 groups of coins that Zeus has, ensuring that in each group consisting of at least two coins, there are at least two heavy coins. Finally, on the fourth move, Anti-Zeus ensures that at least one heavy coin ends up in each non-empty group (of which there are no more than 16). Since Zeus knows nothing about each such group except its total weight, he cannot distinguish a heavy coin from a light one in this group, and therefore cannot reliably identify any light coin.