Maths Olympiad Prep

Track / Stage 6 / 216 of 400 #1216 of 1964

Problem 1216

National olympiad, first round
Combinatorics Difficulty 6.4 Prove it

(8 points) Karlson has 1000 jars of candy. The jars are not necessarily the same, but each of them contains no more than 1%1 \% 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.

This one wants a proof. Work it on paper, then read the official solution and mark yourself. Be honest about it: the record is only any use to you if it is.

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 1100\frac{1}{100} in the condition, we have 99 and 199\frac{1}{99} (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 99100\frac{99}{100} of the total sweets, and in each of "all the others" jars, there is not more than 1100\frac{1}{100} of the total sweets, i.e., not more than 1100:99100=199\frac{1}{100} : \frac{99}{100} = \frac{1}{99} 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 1100\frac{1}{100} of the total amount of sweets.

If the largest jar has less than 1100\frac{1}{100} 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 1100\frac{1}{100}. 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 1100\frac{1}{100}, 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 1100\frac{1}{100}, 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.

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic, difficulty and ordering added by this site.