Art of Problem Solving
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: Difference between revisions

1=2 (talk | contribs)
4,129 edits
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.
 
Gobo (talk | contribs)
2 edits
 
(3 intermediate revisions by 2 users not shown)
Line 3: Line 3:


== Solution ==
== Solution ==
This problem references the [[Farey Sequence]] of order <math>n</math>. We wish to show that no open interval of length <math>1/n</math> contains more than <math>(n+1)/2</math> consecutive terms of the <math>n</math>th Farey sequence.
Let <math>I</math> be an open interval of length <math>1/n</math> and <math>F_n</math> the set of fractions <math>p/q\in I</math> with <math>p,q\in\mathbb{Z}</math>, <math>\gcd(p,q)=1</math> and <math>1\leq q\leq n</math>.  


'''Lemma:''' If <math>a/b</math> and <math>c/d</math> are consecutive terms of the <math>n</math>th Farey sequence and <math>c/d>a/b</math>, then <math>(c/d)-(a/b)=1/bd</math>.
Assume that <math>\frac{p}{q}\in F_n</math>. If <math>k\in\mathbb{Z}</math> is such that <math>1\leq kq\leq n</math>, and <math>p'\in\mathbb{Z}</math> is such that <math>\gcd(p',kq)=1</math>, then
<cmath>\left|\frac{p}{q}-\frac{p'}{kq}\right|\geq\frac{1}{kq}\geq \frac{1}{n}</cmath>
Therefore <math>\frac{p'}{kq}\notin I\supset F_n</math>. This means that <math>\frac{p}{q}</math> is the only fraction in <math>F_n</math> with denominator <math>q</math> or multiple of <math>q</math>.


'''Proof:''' It suffices to show that, for any reduced fraction <math>a/b</math> with <math>1\leq b\leq n</math>, we can find an ordered pair of integers <math>(c,d)</math> with <math>1\leq d\leq n</math> such that <math>bc-ad=1</math>. Then <math>(c/d)-(a/b)=1/bd</math>.
Therefore, from each of the pairs in <math>P=\left\{(k,2k):\ 1\leq k\leq \left\lfloor\frac{n+1}{2}\right\rfloor\right\}</math> at most one element from each can be a denominator of a fraction in <math>F_n</math>.


{{solution}}
Hence <math>|F_n|\leq |P|\leq\frac{n+1}{2}</math>


== See Also ==
== See Also ==

Latest revision as of 10:23, 7 December 2022

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

Let $I$ be an open interval of length $1/n$ and $F_n$ the set of fractions $p/q\in I$ with $p,q\in\mathbb{Z}$, $\gcd(p,q)=1$ and $1\leq q\leq n$.

Assume that $\frac{p}{q}\in F_n$. If $k\in\mathbb{Z}$ is such that $1\leq kq\leq n$, and $p'\in\mathbb{Z}$ is such that $\gcd(p',kq)=1$, then \[\left|\frac{p}{q}-\frac{p'}{kq}\right|\geq\frac{1}{kq}\geq \frac{1}{n}\] Therefore $\frac{p'}{kq}\notin I\supset F_n$. This means that $\frac{p}{q}$ is the only fraction in $F_n$ with denominator $q$ or multiple of $q$.

Therefore, from each of the pairs in $P=\left\{(k,2k):\ 1\leq k\leq \left\lfloor\frac{n+1}{2}\right\rfloor\right\}$ at most one element from each can be a denominator of a fraction in $F_n$.

Hence $|F_n|\leq |P|\leq\frac{n+1}{2}$

See Also

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

These problems are copyrighted © by the Mathematical Association of America, as part of the American Mathematics Competitions. Error creating thumbnail: File missing

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