1983 USAMO Problems/Problem 5
Problem
Consider an open interval of length on the real number line, where is a positive integer. Prove that the number of irreducible fractions , with , contained in the given interval is at most .
Solution
This problem references the Farey Sequence of order . We wish to show that no open interval of length contains more than consecutive terms of the th Farey sequence. To do this, we provide a construction of the Farey Sequences of order at most , prove that this construction yields the desired sequences, and then use properties exhibited from the construction to prove the result.
Lemma 1: Let the sequence be the sequence of integers: . Then for defined , define as follows: we first include every number in in in order, and then for every pair of adjacent, reduced elements and in , we include in in between the two fractions if . Then is the Farey sequence of order . In addition, if and are adjacent terms in any Farey sequence, then .
Proof: We go about this using strong induction on . If , then it is clear that is the Farey sequence of order 1. In addition, the invariant is clear here. Now say that for through , is the Farey sequence of order , and each Farey sequence has the invariant. Then consider . First, we know that is strictly increasing, because the elements that are in are increasing, while any new fractions are strictly between and . In addition, the invariant is preserved: if we insert a new fraction in between two fractions and , we calculate the invariants: , and . And also, contains every fraction that can be expressed as with , and it only contains fractions that can be expressed as with . It only remains to be shown that contains every such fraction. Now consider any fraction that can be expressed as . Note that if this fraction can be reduced, then we have already shown that it is in .
This problem needs a solution. If you have a solution for it, please help us out by adding it.
See Also
1983 USAMO (Problems • Resources) | ||
Preceded by Problem 4 |
Followed by Last Question | |
1 • 2 • 3 • 4 • 5 | ||
All USAMO Problems and Solutions |
The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions.