Olympiad Maths Prep

Library / /27 of 55

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.

Looking for a route rather than 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 and solution reproduced as published; topic and difficulty added by this site.