From natural numbers one constructs 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:
For the sake of contradiction, let's suppose that the smaller value of the maximum fraction can be obtained in some other way. Clearly, cannot be a numerator, hence we can consider the fraction with denominator . Its numerator should be smaller than . Let's denote it as .
There are at least numbers in the set
From the pigeonhole principle it follows that some of these numbers form one of the rest (excluding ) fractions. If we denote them then we will have , 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.