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

Difference between revisions of "1983 USAMO Problems/Problem 5"

(Rewrite, will finish proof later)
(→‎Solution)
 
(2 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. To do this, we provide a construction of the Farey Sequences of order at most <math>n</math>, prove that this construction yields the desired sequences, and then use properties exhibited from the construction to prove the result.
+
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 1:''' Let the sequence <math>\{F_1(i)\}</math> be the sequence of integers: <math>F_1(i)=i</math>. Then for defined <math>F_k</math>, define <math>F_{k+1}</math> as follows: we first include every number in <math>F_k</math> in <math>F_{k+1}</math> in order, and then for every pair of adjacent, reduced elements <math>a/b</math> and <math>a_1/b_1</math> in <math>F_k</math>, we include <math>(a+a_1)/(b+b_1)</math> in <math>F_{k+1}</math> in between the two fractions if <math>b+b_1=k+1</math>. Then <math>F_k</math> is the Farey sequence of order <math>k</math>. In addition, if <math>a/b</math> and <math>c/d</math> are adjacent terms in any Farey sequence, then <math>bc-ad=1</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:''' We go about this using strong induction on <math>k</math>. If <math>k=1</math>, then it is clear that <math>F_1</math> is the Farey sequence of order 1. In addition, the <math>bc-ad=1</math> invariant is clear here. Now say that for <math>i=1</math> through <math>k-1</math>, <math>F_i</math> is the Farey sequence of order <math>i</math>, and each Farey sequence has the <math>bc-ad=1</math> invariant. Then consider <math>F_k</math>. First, we know that <math>F_k</math> is strictly increasing, because the elements that are in <math>F_{k-1}</math> are increasing, while any new fractions <math>(a+a_1)/(b+b_1)</math> are strictly between <math>a/b</math> and <math>a_1/b_1</math>. In addition, <math>F_k</math> contains every fraction that can be expressed as <math>a/b</math> with <math>b\leq k-1</math>, and it only contains fractions that can be expressed as <math>a/b</math> with <math>b\leq k</math>. It only remains to be shown that <math>F_k</math> contains ''every'' such fraction, and the <math>bc-ad=1</math> invariant still holds. Now consider any fraction that can be expressed as <math>c/k</math>. Note that if this fraction can be reduced, then we have already shown that it is in <math>F_k</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

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=183700"