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 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 . Clearly since the second division has more than 200 groups. Hence there is an index such that . Assume to be minimal with this property, meaning that .
Consider a group with . Each coin in it is not special, so in the first division it was in a group of size . On the other hand , hence groups of size in the first division are among . Thus the entire group is contained in the union of . The conclusion holds for every , so the union of is contained in the union of . However this is false as and .
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.