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.

Lemma: If $a/b$ and $c/d$ are consecutive terms of the $n$ th Farey sequence and $c/d>a/b$ , then $(c/d)-(a/b)=1/bd$ .

Proof: It suffices to show that, for any reduced fraction $a/b$ with $1\leq b\leq n$ , we can find an ordered pair of integers $(c,d)$ with $1\leq d\leq n$ such that $bc-ad=1$ . Then $(c/d)-(a/b)=1/bd$ .

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