Maths Olympiad Prep

Library / /98 of 189

Combinatorics Difficulty 5.8 AIME, harder Prove it Ukraine

From natural numbers 2,3,4,,20192, 3, 4, \ldots, 2019 one constructs 10091009 fractions, and chooses the maximum of these. What is the minimum possible value of this maximum fraction?
(Bogdan Rublyov)

Solution

First of all, note that this value can be achieved with the following fractions choice:
11011,21012,31013,,10102019. \frac{1}{1011}, \frac{2}{1012}, \frac{3}{1013}, \dots, \frac{1010}{2019}.

For the sake of contradiction, let's suppose that the smaller value of the maximum fraction can be obtained in some other way. Clearly, 20192019 cannot be a numerator, hence we can consider the fraction with denominator 20192019. Its numerator should be smaller than 10101010. Let's denote it as a<1010a < 1010.
There are at least 10091009 numbers in the set
M={a,a+1,,1010,1011,,2018}. M = \{a, a+1, \dots, 1010, 1011, \dots, 2018\}.
From the pigeonhole principle it follows that some of these numbers form one of the rest 10081008 (excluding a2019\frac{a}{2019}) fractions. If we denote them b<cb < c then we will have 10102019<b2019<bc\frac{1010}{2019} < \frac{b}{2019} < \frac{b}{c}, a contradiction.

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.