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)
m (→‎Solution)
Line 7: Line 7:
 
'''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>.
 
'''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>.
  
−
'''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>.
+
'''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, the <math>bc-ad=1</math> invariant is preserved: if we insert a new fraction <math>(a+a_1)/(b+b_1)</math> in between two fractions <math>a/b</math> and <math>a_1/b_1</math>, we calculate the invariants: <math>b(a+a_1)-a(b+b_1)=ba_1-ab_1=1</math>, and <math>(b+b_1)a_1-(a+a_1)b_1=ba_1-ab_1=1</math>. And also, <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. Now consider any fraction that can be expressed as <math>m/k</math>. Note that if this fraction can be reduced, then we have already shown that it is in <math>F_k</math>.
  
 
{{solution}}
 
{{solution}}

Revision as of 11:59, 19 July 2016

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, the $bc-ad=1$ invariant is preserved: if we insert a new fraction $(a+a_1)/(b+b_1)$ in between two fractions $a/b$ and $a_1/b_1$, we calculate the invariants: $b(a+a_1)-a(b+b_1)=ba_1-ab_1=1$, and $(b+b_1)a_1-(a+a_1)b_1=ba_1-ab_1=1$. And also, $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. Now consider any fraction that can be expressed as $m/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=79591"