1983 USAMO Problems/Problem 5

Revision as of 23:02, 17 July 2016 by 1=2 (talk | contribs) (I'll leave my progress up for anyone who wants to finish the problem. I have a solution sketch in mind, but I need sleep now.)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

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.

See Also

1983 USAMO (ProblemsResources)
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. AMC logo.png