Difference between revisions of "2002 USAMO Problems/Problem 5"

 
m
Line 1: Line 1:
 
== Problem ==
 
== Problem ==
  
Let <math> \displaystyle a, b </math> be integers greater than 2.  Prove that there exists a positive integer <math> \displaystyle k </math> and a finite sequence <math> \displaystyle n_1, n_2, \ldots, n_k </math> of positive integers such that <math> \displaystyle n_1 = a</math>, <math> \displaystyle n_k = b </math>, and <math> \displaystyle n_1n_{i+1} </math> is divisible by <math> \displaystyle n_i + n_{i+1} </math> for each <math> \displaystyle i </math> (<math> 1 \le 1 \le k </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> \displaystyle a </math> and <math> \displaystyle 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> ).
+
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> \displaystyle d </math> of some <math> \displaystyle n </math>, <math> \displaystyle 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> \displaystyle k </math>, and
+
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> \displaystyle c < d </math>.
+
for any positive integer <math>c < d </math>.
  
For all integers <math> \displaystyle a > b > 2 </math>, there exists some integer <math> \displaystyle \lambda </math> such that <math> \displaystyle (b-1)^{\lambda} > a </math>.  Let
+
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> \displaystyle n_i + n_{i+1} \mid n_in_{i+1} </math> if and only if
+
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> \displaystyle d > n_i </math> of <math> \displaystyle n_i^2 </math>, <math> d - n_i \leftrightarrow n_i </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> \displaystyle a(a-1) </math> is even, this means that all integers greater than or equal to 2 are connected to some even number.
+
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> \displaystyle d > 2 </math> is a divisor of <math> \displaystyle n </math>, then <math> n \leftrightarrow n(d-1) </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> \displaystyle 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> \displaystyle f(n) </math> (<math> \displaystyle n>2 </math>) to be the smallest divisor of <math> \displaystyle n </math> that is greater than 2.  We will prove that 2 is safe, by strong induction on <math> \displaystyle f(n) </math>.  For the case <math> \displaystyle f(n) = 3 </math>, we have <math> n \leftrightarrow (3-1)n = 2n </math>.  If <math> \displaystyle f(n) > 3 </math>, we note that <math> \displaystyle f[n(f(n) - 1)] < f(n) </math>, since <math> \displaystyle f(n) - 1 </math> must be less than all the divisors of <math> \displaystyle 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> \displaystyle n \leftrightarrow 2n </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> \displaystyle p </math> is safe, by strong induction.  We have already proven the base case <math> \displaystyle p = 2 </math>.  Now, for odd <math> \displaystyle p </math>, <math> \displaystyle p+1 </math> is the product of odd primes less than <math> \displaystyle p </math>, so <math> \displaystyle p+1 </math> is safe.  Then we have
+
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> \displaystyle a </math> and <math> \displaystyle b </math> are safe, and <math> a \leftrightarrow ab \leftrightarrow b </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> \displaystyle k < a </math> and any positive integers <math> e_1, \ldots, e_k </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> \displaystyle k </math>, <math> ka \leftrightarrow kb </math>, for <math> \displaystyle (a+b) \mid (ab) </math> implies <math> \displaystyle k(a+b) \mid k^2(ab) </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> \displaystyle a > 3 </math>, <math> a \leftrightarrow (a-1) </math>.  If <math> \displaystyle a </math> is composite, then there exist <math> m \ge n > 0 </math> such that <math> \displaystyle (a-1-m)(a-1-n) = a </math>, and
+
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> \displaystyle a </math> is prime, then we use strong induction.  For the base case, <math> \displaystyle a = 5 </math>, we note <math> 4 \leftrightarrow 3 \leftrightarrow 3(3-1) = 6 \leftrightarrow 5 </math>.  Now, assuming that <math> \displaystyle a>5 </math> and that this holds for all primes less than <math> \displaystyle a </math> (we know it holds for all composites), it is sufficient to show that <math> (a+1) \leftrightarrow (a-1) </math>, since <math> \displaystyle (a+1) </math> is composite and therefore <math> (a+1) \leftrightarrow a </math>.  But since <math> \displaystyle (a+1) </math> and <math> \displaystyle (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> \displaystyle a </math>, and it is greater than 3, since <math> \displaystyle a > 5 </math>.  Thus the induction is complete.
+
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.
  
== Resources ==
+
== See also ==
 
+
{{USAMO newbox|year=2002|num-b=4|num-a=6}}
* [[2002 USAMO Problems]]
 
* [http://www.artofproblemsolving.com/Forum/viewtopic.php?p=337862#p337862 Discussion on AoPS/MathLinks]
 
  
  
 
[[Category:Olympiad Number Theory Problems]]
 
[[Category:Olympiad Number Theory Problems]]

Revision as of 20:49, 6 April 2013

Problem

Let $a, b$ be integers greater than 2. Prove that there exists a positive integer $k$ and a finite sequence $n_1, n_2, \ldots, n_k$ of positive integers such that $n_1 = a$, $n_k = b$, and $n_1n_{i+1}$ is divisible by $n_i + n_{i+1}$ for each $i$ ($1 \le 1 \le k$).

Solutions

We may say that two integers $a$ and $b$ are connected (and write $a \leftrightarrow b$) if there exists such a sequence of integers as described in the problem. For reference, we note that $\leftrightarrow$ is an equivalence relation: it is reflexive ($a \leftrightarrow a$), symmetric ($a \leftrightarrow b$ implies $b \leftrightarrow a$), and transitive ($a \leftrightarrow b \leftrightarrow c$ implies $a \leftrightarrow c$ ).

Solution 1

Note that for any divisor $d$ of some $n$, $n(d-1) + n = nd \mid n^2(d-1)$, so $n \leftrightarrow n(d-1)$. It follows that in fact $n \leftrightarrow n(d-1)^k$, for any nonnegative integer $k$, and

$n \leftrightarrow n(d-1) \leftrightarrow n(d-1)(d-2) \leftrightarrow \cdots \leftrightarrow n \prod_{i=c}^{d-1}i$

for any positive integer $c < d$.

For all integers $a > b > 2$, there exists some integer $\lambda$ such that $(b-1)^{\lambda} > a$. Let

$X = \prod_{i=b}^{(b-1)^{\lambda}}i$.

We have

$a \leftrightarrow \prod_{i=b}^{a}i \leftrightarrow (b-1)^{\lambda} \prod_{i=b}^{a}i \leftrightarrow (b-1)^{\lambda}  \prod_{i=b}^{a}i \cdot \prod_{i=a+1}^{(b-1)^{\lambda}-1} i = X$.

But we also have

$b \leftrightarrow b(b-1)^{\lambda} \leftrightarrow b (b-1)^{\lambda} \prod_{i=b+1}^{(b-1)^{\lambda}-1}i = X$.

Hence $a \leftrightarrow X \leftrightarrow b$, so $a \leftrightarrow b$, as desired.

Solution 2

We note that for any integer $n \ge 3$, $n \leftrightarrow 2n$, for

$n \leftrightarrow n(n-1) \leftrightarrow n(n-1)(n-2) \leftrightarrow n(n-2) \leftrightarrow 2n$

It follows that for $n \ge 4$,

$n \leftrightarrow n(n-1) \leftrightarrow n(n-1)(n-2) \leftrightarrow n(n-1)(n-2)(n-3) \leftrightarrow 2(n-1)(n-2) \leftrightarrow (n-1)(n-2) \leftrightarrow (n-1)$.

Thus all integers greater than 2 are connected.

Solution 3

We note that $n_i + n_{i+1} \mid n_in_{i+1}$ if and only if

$(n_i + n_{i+1}) \mid [(n_i + n_{i+1})n_i - n_in_{i+1}] = n_i^2$.

Therefore for any divisor $d > n_i$ of $n_i^2$, $d - n_i \leftrightarrow n_i$.

Now, for $a \ge 2$,

$4a \leftrightarrow 4a^2 - 4a = 4a(a-1) \leftrightarrow 8a^2 - 4a(a-1) = 4a(a+1) \leftrightarrow 4(a+1)^2 - 4a(a+1) = 4(a+1)$.

Also,

$4 \leftrightarrow 4^2 - 4 = 12$.

This means that all positive multiples of 4 are connected.

Furthermore, for $a \ge 2$,

$2a \leftrightarrow 2a(a-1)$,

which implies that every even number greater than 2 is connected to a multiple of 4.

Finally, for $a \ge 3$,

$a \leftrightarrow a(a-1)$.

Since $a(a-1)$ 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 $d > 2$ is a divisor of $n$, then $n \leftrightarrow n(d-1)$.

We say a positive integer $k$ is safe if for all integers $n \ge 3$, $n \leftrightarrow kn$. Note that the product of two safe numbers is also a safe number. Define $f(n)$ ($n>2$) to be the smallest divisor of $n$ that is greater than 2. We will prove that 2 is safe, by strong induction on $f(n)$. For the case $f(n) = 3$, we have $n \leftrightarrow (3-1)n = 2n$. If $f(n) > 3$, we note that $f[n(f(n) - 1)] < f(n)$, since $f(n) - 1$ must be less than all the divisors of $n$. Thus the inductive hypothesis gives us $[f(n) - 1]n \leftrightarrow 2[f(n) - 1]n$. Furthermore, we have $n \leftrightarrow [f(n)-1]n$ and $2n \leftrightarrow 2[f(n)-1]n$, both from our initial note. Thus $n \leftrightarrow 2n$.

We will now prove that every prime $p$ is safe, by strong induction. We have already proven the base case $p = 2$. Now, for odd $p$, $p+1$ is the product of odd primes less than $p$, so $p+1$ is safe. Then we have

$n \leftrightarrow (p+1)n \leftrightarrow p(p+1)n \leftrightarrow pn$.

Thus the induction is complete, and all primes are safe.

We have now shown that all integers greater than 1 are safe. Specifically, $a$ and $b$ are safe, and $a \leftrightarrow ab \leftrightarrow b$.

Solution 5

Similarly to the first solution, we observe that for any integer $k < a$ and any positive integers $e_1, \ldots, e_k$,

$a \leftrightarrow a \prod_{i=1}^{k}(a-i)^{e_i}$.

We also note that if $a \leftrightarrow b$, then for any positive integer $k$, $ka \leftrightarrow kb$, for $(a+b) \mid (ab)$ implies $k(a+b) \mid k^2(ab)$.

It is sufficient to prove that for any $a > 3$, $a \leftrightarrow (a-1)$. If $a$ is composite, then there exist $m \ge n > 0$ such that $(a-1-m)(a-1-n) = a$, and

$(a-1) \leftrightarrow (a-1-m)(a-1-n) \prod_{i=0}^{m-1}(a-1-i) = a \prod_{i=0}^{m-1}(a-1-i) \leftrightarrow a$.

If, on the other hand, $a$ is prime, then we use strong induction. For the base case, $a = 5$, we note $4 \leftrightarrow 3 \leftrightarrow 3(3-1) = 6 \leftrightarrow 5$. Now, assuming that $a>5$ and that this holds for all primes less than $a$ (we know it holds for all composites), it is sufficient to show that $(a+1) \leftrightarrow (a-1)$, since $(a+1)$ is composite and therefore $(a+1) \leftrightarrow a$. But since $(a+1)$ and $(a-1)$ are both even, it suffices to show that $\frac{a+1}{2} \leftrightarrow \frac{a-1}{2} = \frac{a+1}{2} - 1$. But this is true, since $\frac{a+1}{2}$ either composite, or a prime less than $a$, and it is greater than 3, since $a > 5$. Thus the induction is complete.

See also

2002 USAMO (ProblemsResources)
Preceded by
Problem 4
Followed by
Problem 6
1 2 3 4 5 6
All USAMO Problems and Solutions
Invalid username
Login to AoPS