Difference between revisions of "2002 USAMO Problems/Problem 5"
m (→Problem) |
|||
Line 1: | Line 1: | ||
== Problem == | == Problem == | ||
− | Let <math>a, b </math> be integers greater than 2. Prove that there exists a positive integer <math>k </math> and a finite sequence <math>n_1, n_2, \ldots, n_k </math> of positive integers such that <math>n_1 = a</math>, <math>n_k = b </math>, and <math>n_1n_{i+1} </math> is divisible by <math>n_i + n_{i+1} </math> for each <math>i </math> (<math> 1 \le | + | Let <math>a, b </math> be integers greater than 2. Prove that there exists a positive integer <math>k </math> and a finite sequence <math>n_1, n_2, \ldots, n_k </math> of positive integers such that <math>n_1 = a</math>, <math>n_k = b </math>, and <math>n_1n_{i+1} </math> is divisible by <math>n_i + n_{i+1} </math> for each <math>i </math> (<math> 1 \le i \le k </math>). |
== Solutions == | == Solutions == |
Revision as of 21:06, 14 October 2013
Contents
Problem
Let be integers greater than 2. Prove that there exists a positive integer
and a finite sequence
of positive integers such that
,
, and
is divisible by
for each
(
).
Solutions
We may say that two integers and
are connected (and write
) if there exists such a sequence of integers as described in the problem. For reference, we note that
is an equivalence relation: it is reflexive (
), symmetric (
implies
), and transitive (
implies
).
Solution 1
Note that for any divisor of some
,
, so
. It follows that in fact
, for any nonnegative integer
, and
for any positive integer .
For all integers , there exists some integer
such that
. Let
.
We have
.
But we also have
.
Hence , so
, as desired.
Solution 2
We note that for any integer ,
, for
It follows that for ,
.
Thus all integers greater than 2 are connected.
Solution 3
We note that if and only if
.
Therefore for any divisor of
,
.
Now, for ,
.
Also,
.
This means that all positive multiples of 4 are connected.
Furthermore, for ,
,
which implies that every even number greater than 2 is connected to a multiple of 4.
Finally, for ,
.
Since is even, this means that all integers greater than or equal to 2 are connected to some even number.
Together, these imply that all integers greater than 2 are connected.
Solution 4
We note that if is a divisor of
, then
.
We say a positive integer is safe if for all integers
,
. Note that the product of two safe numbers is also a safe number. Define
(
) to be the smallest divisor of
that is greater than 2. We will prove that 2 is safe, by strong induction on
. For the case
, we have
. If
, we note that
, since
must be less than all the divisors of
. Thus the inductive hypothesis gives us
. Furthermore, we have
and
, both from our initial note. Thus
.
We will now prove that every prime is safe, by strong induction. We have already proven the base case
. Now, for odd
,
is the product of odd primes less than
, so
is safe. Then we have
.
Thus the induction is complete, and all primes are safe.
We have now shown that all integers greater than 1 are safe. Specifically, and
are safe, and
.
Solution 5
Similarly to the first solution, we observe that for any integer and any positive integers
,
.
We also note that if , then for any positive integer
,
, for
implies
.
It is sufficient to prove that for any ,
. If
is composite, then there exist
such that
, and
.
If, on the other hand, is prime, then we use strong induction. For the base case,
, we note
. Now, assuming that
and that this holds for all primes less than
(we know it holds for all composites), it is sufficient to show that
, since
is composite and therefore
. But since
and
are both even, it suffices to show that
. But this is true, since
either composite, or a prime less than
, and it is greater than 3, since
. Thus the induction is complete.
See also
2002 USAMO (Problems • Resources) | ||
Preceded by Problem 4 |
Followed by Problem 6 | |
1 • 2 • 3 • 4 • 5 • 6 | ||
All USAMO Problems and Solutions |
The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions.