1983 USAMO Problems/Problem 5

Problem

Consider an open interval of length $1/n$ on the real number line, where $n$ is a positive integer. Prove that the number of irreducible fractions $p/q$ , with $1\le q\le n$ , contained in the given interval is at most $(n+1)/2$ .

Solution

This problem references the Farey Sequence of order $n$ . We wish to show that no open interval of length $1/n$ contains more than $(n+1)/2$ consecutive terms of the $n$ th Farey sequence. To do this, we provide a construction of the Farey Sequences of order at most $n$ , 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 $\{F_1(i)\}$ be the sequence of integers: $F_1(i)=i$ . Then for defined $F_k$ , define $F_{k+1}$ as follows: we first include every number in $F_k$ in $F_{k+1}$ in order, and then for every pair of adjacent, reduced elements $a/b$ and $a_1/b_1$ in $F_k$ , we include $(a+a_1)/(b+b_1)$ in $F_{k+1}$ in between the two fractions if $b+b_1=k+1$ . Then $F_k$ is the Farey sequence of order $k$ . In addition, if $a/b$ and $c/d$ are adjacent terms in any Farey sequence, then $bc-ad=1$ .

Proof: We go about this using strong induction on $k$ . If $k=1$ , then it is clear that $F_1$ is the Farey sequence of order 1. In addition, the $bc-ad=1$ invariant is clear here. Now say that for $i=1$ through $k-1$ , $F_i$ is the Farey sequence of order $i$ , and each Farey sequence has the $bc-ad=1$ invariant. Then consider $F_k$ . First, we know that $F_k$ is strictly increasing, because the elements that are in $F_{k-1}$ are increasing, while any new fractions $(a+a_1)/(b+b_1)$ are strictly between $a/b$ and $a_1/b_1$ . In addition, the $bc-ad=1$ invariant is preserved: if we insert a new fraction $(a+a_1)/(b+b_1)$ in between two fractions $a/b$ and $a_1/b_1$ , we calculate the invariants: $b(a+a_1)-a(b+b_1)=ba_1-ab_1=1$ , and $(b+b_1)a_1-(a+a_1)b_1=ba_1-ab_1=1$ . And also, $F_k$ contains every fraction that can be expressed as $a/b$ with $b\leq k-1$ , and it only contains fractions that can be expressed as $a/b$ with $b\leq k$ . It only remains to be shown that $F_k$ contains every such fraction. Now consider any fraction that can be expressed as $m/k$ . Note that if this fraction can be reduced, then we have already shown that it is in $F_k$ .

This problem needs a solution. If you have a solution for it, please help us out by adding it.

1983 USAMO (Problems • Resources)
Preceded by Problem 4	Followed by Last Question
1 • 2 • 3 • 4 • 5
All USAMO Problems and Solutions

Page

Toolbox

Search

1983 USAMO Problems/Problem 5

Problem

Solution

See Also