# 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$.