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 20:49, 6 April 2013
Contents
[hide]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 |