Difference between revisions of "1983 USAMO Problems/Problem 5"
(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.) |
(Rewrite, will finish proof later) |
||
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. | + | 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. |
− | '''Lemma:''' | + | '''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:''' | + | '''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>. |
{{solution}} | {{solution}} |
Revision as of 22:12, 18 July 2016
Problem
Consider an open interval of length on the real number line, where
is a positive integer. Prove that the number of irreducible fractions
, with
, contained in the given interval is at most
.
Solution
This problem references the Farey Sequence of order . We wish to show that no open interval of length
contains more than
consecutive terms of the
th Farey sequence. To do this, we provide a construction of the Farey Sequences of order at most
, 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 be the sequence of integers:
. Then for defined
, define
as follows: we first include every number in
in
in order, and then for every pair of adjacent, reduced elements
and
in
, we include
in
in between the two fractions if
. Then
is the Farey sequence of order
. In addition, if
and
are adjacent terms in any Farey sequence, then
.
Proof: We go about this using strong induction on . If
, then it is clear that
is the Farey sequence of order 1. In addition, the
invariant is clear here. Now say that for
through
,
is the Farey sequence of order
, and each Farey sequence has the
invariant. Then consider
. First, we know that
is strictly increasing, because the elements that are in
are increasing, while any new fractions
are strictly between
and
. In addition,
contains every fraction that can be expressed as
with
, and it only contains fractions that can be expressed as
with
. It only remains to be shown that
contains every such fraction, and the
invariant still holds. Now consider any fraction that can be expressed as
. Note that if this fraction can be reduced, then we have already shown that it is in
.
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.