(8 points) Karlson has 1000 jars of candy. The jars are not necessarily the same, but each of them contains no more than of all the candy. For breakfast, Karlson can eat the same amount of candy from any 100 jars. Prove that Karlson can have breakfast in such a way that he will eat all the candy in a few days.
Problem 1216
Official solution
Solution: We will prove the statement by induction.
Let's assume that Karlson can eat all the sweets if instead of 100 and in the condition, we have 99 and (the total number of jars is not important, the main thing is that they are sufficiently many, not less than 100). (We will call these problems "Problem-100" and "Problem-99" respectively.) We will explain how he acts in the case of Problem-100.
Karlson mentally divides the jars of sweets into two parts: the largest (by the amount of sweets) and "all the others." Let's note that for "all the others" jars, the condition of Problem-99 is satisfied (in "all the others" jars, the sweets are not less than of the total sweets, and in each of "all the others" jars, there is not more than of the total sweets, i.e., not more than of the amount of sweets in "all the others" jars).
Therefore, Karlson can act as follows: eat all the sweets from "all the others" jars according to the algorithm of "Problem-99," taking 99 jars from "all the others" at each step and adding the hundredth jar - "the largest one." To finish the sweets in "the largest" jar and "all the others" simultaneously, it is necessary for it to have exactly 99 times less sweets than in "all the others" taken together (since from it, each time 99 times less will be eaten than from "all the others"). That is, it is necessary for the largest jar to initially have exactly of the total amount of sweets.
If the largest jar has less than of the total amount of sweets, Karlson selects 100 non-empty jars from "all the others" and eats some amount of sweets from them. In this way, the part of the sweets in the largest jar increases. We will show how he should act to make this part exactly . If the amount of sweets in the smallest jar (from the selected hundred) allows him to eat a part of the sweets so that the part in the largest jar becomes equal to , he does so. Otherwise, he eats all the sweets from the smallest jar, reducing the number of non-empty jars. Karlson stops either when he achieves the goal or when the number of non-empty jars among "all the others" becomes less than 100. But the latter case is impossible, since the part of the largest jar is not less than , i.e., Karlson should have stopped earlier.
To complete the solution, it remains to note that we have learned how to reduce "Problem-100" to "Problem-99," but in the same way, we can now reduce it to "Problem-98," then to "Problem-97," and so on. And "Problem-1" is obvious.