Difference between revisions of "2002 USAMO Problems/Problem 5"
m |
|||
Line 1: | Line 1: | ||
== Problem == | == Problem == | ||
− | Let <math> | + | 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 1 \le k </math>). |
== Solutions == | == Solutions == | ||
− | We may say that two integers <math> | + | We may say that two integers <math>a </math> and <math>b </math> are ''connected'' (and write <math> a \leftrightarrow b </math>) if there exists such a sequence of integers as described in the problem. For reference, we note that <math> \leftrightarrow </math> is an [[equivalence relation]]: it is [[reflexive]] (<math> a \leftrightarrow a</math>), [[symmetric]] (<math> a \leftrightarrow b </math> implies <math> b \leftrightarrow a</math>), and [[transitive]] (<math> a \leftrightarrow b \leftrightarrow c </math> implies <math> a \leftrightarrow c </math> ). |
=== Solution 1 === | === Solution 1 === | ||
− | Note that for any divisor <math> | + | Note that for any divisor <math>d </math> of some <math>n </math>, <math>n(d-1) + n = nd \mid n^2(d-1) </math>, so <math> n \leftrightarrow n(d-1) </math>. It follows that in fact <math> n \leftrightarrow n(d-1)^k </math>, for any nonnegative integer <math>k </math>, and |
<center> | <center> | ||
<math> | <math> | ||
Line 15: | Line 15: | ||
</math> | </math> | ||
</center> | </center> | ||
− | for any positive integer <math> | + | for any positive integer <math>c < d </math>. |
− | For all integers <math> | + | For all integers <math>a > b > 2 </math>, there exists some integer <math>\lambda </math> such that <math>(b-1)^{\lambda} > a </math>. Let |
<center> | <center> | ||
<math> | <math> | ||
Line 59: | Line 59: | ||
=== Solution 3 === | === Solution 3 === | ||
− | We note that <math> | + | We note that <math>n_i + n_{i+1} \mid n_in_{i+1} </math> if and only if |
<center> | <center> | ||
<math> | <math> | ||
Line 65: | Line 65: | ||
</math>. | </math>. | ||
</center> | </center> | ||
− | Therefore for any divisor <math> | + | Therefore for any divisor <math>d > n_i </math> of <math>n_i^2 </math>, <math> d - n_i \leftrightarrow n_i </math>. |
Now, for <math> a \ge 2 </math>, | Now, for <math> a \ge 2 </math>, | ||
Line 95: | Line 95: | ||
</math>. | </math>. | ||
</center> | </center> | ||
− | Since <math> | + | Since <math>a(a-1) </math> 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. | Together, these imply that all integers greater than 2 are connected. | ||
Line 101: | Line 101: | ||
=== Solution 4 === | === Solution 4 === | ||
− | We note that if <math> | + | We note that if <math>d > 2 </math> is a divisor of <math>n </math>, then <math> n \leftrightarrow n(d-1) </math>. |
− | We say a positive integer <math> | + | We say a positive integer <math>k </math> is ''safe'' if for all integers <math> n \ge 3 </math>, <math> n \leftrightarrow kn </math>. Note that the product of two safe numbers is also a safe number. Define <math>f(n) </math> (<math>n>2 </math>) to be the smallest divisor of <math>n </math> that is greater than 2. We will prove that 2 is safe, by strong induction on <math>f(n) </math>. For the case <math>f(n) = 3 </math>, we have <math> n \leftrightarrow (3-1)n = 2n </math>. If <math>f(n) > 3 </math>, we note that <math>f[n(f(n) - 1)] < f(n) </math>, since <math>f(n) - 1 </math> must be less than all the divisors of <math>n </math>. Thus the inductive hypothesis gives us <math> [f(n) - 1]n \leftrightarrow 2[f(n) - 1]n </math>. Furthermore, we have <math> n \leftrightarrow [f(n)-1]n </math> and <math> 2n \leftrightarrow 2[f(n)-1]n </math>, both from our initial note. Thus <math>n \leftrightarrow 2n </math>. |
− | We will now prove that every prime <math> | + | We will now prove that every prime <math>p </math> is safe, by strong induction. We have already proven the base case <math>p = 2 </math>. Now, for odd <math>p </math>, <math>p+1 </math> is the product of odd primes less than <math>p </math>, so <math>p+1 </math> is safe. Then we have |
<center> | <center> | ||
<math> | <math> | ||
Line 113: | Line 113: | ||
Thus the induction is complete, and all primes are safe. | Thus the induction is complete, and all primes are safe. | ||
− | We have now shown that all integers greater than 1 are safe. Specifically, <math> | + | We have now shown that all integers greater than 1 are safe. Specifically, <math>a </math> and <math>b </math> are safe, and <math> a \leftrightarrow ab \leftrightarrow b </math>. |
=== Solution 5 === | === Solution 5 === | ||
− | Similarly to the first solution, we observe that for any integer <math> | + | Similarly to the first solution, we observe that for any integer <math>k < a </math> and any positive integers <math> e_1, \ldots, e_k </math>, |
<center> | <center> | ||
<math> | <math> | ||
Line 124: | Line 124: | ||
</center> | </center> | ||
− | We also note that if <math> a \leftrightarrow b </math>, then for any positive integer <math> | + | We also note that if <math> a \leftrightarrow b </math>, then for any positive integer <math>k </math>, <math> ka \leftrightarrow kb </math>, for <math>(a+b) \mid (ab) </math> implies <math>k(a+b) \mid k^2(ab) </math>. |
− | It is sufficient to prove that for any <math> | + | It is sufficient to prove that for any <math>a > 3 </math>, <math> a \leftrightarrow (a-1) </math>. If <math>a </math> is composite, then there exist <math> m \ge n > 0 </math> such that <math>(a-1-m)(a-1-n) = a </math>, and |
<center> | <center> | ||
<math> | <math> | ||
Line 133: | Line 133: | ||
</center> | </center> | ||
− | If, on the other hand, <math> | + | If, on the other hand, <math>a </math> is prime, then we use strong induction. For the base case, <math>a = 5 </math>, we note <math> 4 \leftrightarrow 3 \leftrightarrow 3(3-1) = 6 \leftrightarrow 5 </math>. Now, assuming that <math>a>5 </math> and that this holds for all primes less than <math>a </math> (we know it holds for all composites), it is sufficient to show that <math> (a+1) \leftrightarrow (a-1) </math>, since <math>(a+1) </math> is composite and therefore <math> (a+1) \leftrightarrow a </math>. But since <math>(a+1) </math> and <math>(a-1) </math> are both even, it suffices to show that <math> \frac{a+1}{2} \leftrightarrow \frac{a-1}{2} = \frac{a+1}{2} - 1 </math>. But this is true, since <math> \frac{a+1}{2} </math> either composite, or a prime less than <math>a </math>, and it is greater than 3, since <math>a > 5 </math>. Thus the induction is complete. |
− | == | + | == See also == |
− | + | {{USAMO newbox|year=2002|num-b=4|num-a=6}} | |
− | |||
− | |||
[[Category:Olympiad Number Theory Problems]] | [[Category:Olympiad Number Theory Problems]] |
Revision as of 21:49, 6 April 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 |