Maths Olympiad Prep

Library / /7 of 15

Combinatorics Difficulty 5.9 AIME, harder Prove it Argentina

Several coins are divided once into 200 groups, and then once again into 300 groups. Call a coin special if it is in a group of smaller size in the second division than in the first division. Find the minimum number of special coins.

Solution

The least number of special coins is 101. Example with exactly 101 special coins: The first division has 200 groups with 101 coins each; the second division is obtained by dividing one of these groups into 101 groups of 1 coin.
Let x1x2x200x_1 \le x_2 \le \dots \le x_{200} be the sizes of the 200 groups in the first division. Suppose that the second division has 200 groups without any special coin (there may be more such groups), and let their sizes be y1y2y200y_1 \le y_2 \le \dots \le y_{200}. Clearly x1+x2++x200>y1+y2++y200x_1 + x_2 + \dots + x_{200} > y_1 + y_2 + \dots + y_{200} since the second division has more than 200 groups. Hence there is an index j=1,,200j = 1, \dots, 200 such that xj>yjx_j > y_j. Assume jj to be minimal with this property, meaning that xiy1,,xj1yj1,xj>yjx_i \le y_1, \dots, x_{j-1} \le y_{j-1}, x_j > y_j.
Consider a group yiy_i with 1ij1 \le i \le j. Each coin in it is not special, so in the first division it was in a group of size yi\le y_i. On the other hand x200xj>yjyix_{200} \ge \dots \ge x_j > y_j \ge y_i, hence groups of size yi\le y_i in the first division are among x1,,xj1x_1, \dots, x_{j-1}. Thus the entire group yiy_i is contained in the union of x1,,xj1x_1, \dots, x_{j-1}. The conclusion holds for every i=1,,ji=1, \dots, j, so the union of y1,,yjy_1, \dots, y_j is contained in the union of x1,,xj1x_1, \dots, x_{j-1}. However this is false as xiy1,,xj1yj1x_i \le y_1, \dots, x_{j-1} \le y_{j-1} and yj>0y_j > 0.
Thus the second division has at most 199 groups without any special coin. Then there are at least 101 groups with a special coin in it, yielding at least 101 special coins in particular.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.