Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

1983 USAMO Problems/Problem 5

Revision as of 21:12, 18 July 2016 by 1=2 (talk | contribs) (Rewrite, will finish proof later)

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, $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, and the $bc-ad=1$ invariant still holds. Now consider any fraction that can be expressed as $c/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.

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. AMC logo.png

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=1983_USAMO_Problems/Problem_5&oldid=79470"