AoPSWiki

Do you have what it takes to be the next brilliant trader, researcher, or developer at Jane Street Capital? Find out in the Careers in Mathematics Forum.

Personal tools

Search

Toolbox

2002 USAMO Problems/Problem 5

From AoPSWiki

Contents

1 Problem
2 Solutions
3 Resources

Problem

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

Solutions

We may say that two integers $\displaystyle a$ and $\displaystyle 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 $\displaystyle d$ of some $\displaystyle n$ , $\displaystyle 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 $\displaystyle 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 $\displaystyle c < d$ .

For all integers $\displaystyle a > b > 2$ , there exists some integer $\displaystyle \lambda$ such that $\displaystyle (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...$ .

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) \leftrighta...$ .

Thus all integers greater than 2 are connected.

Solution 3

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

We say a positive integer $\displaystyle 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 $\displaystyle f(n)$ ( $\displaystyle n>2$ ) to be the smallest divisor of $\displaystyle n$ that is greater than 2. We will prove that 2 is safe, by strong induction on $\displaystyle f(n)$ . For the case $\displaystyle f(n) = 3$ , we have $n \leftrightarrow (3-1)n = 2n$ . If $\displaystyle f(n) > 3$ , we note that $\displaystyle f[n(f(n) - 1)] < f(n)$ , since $\displaystyle f(n) - 1$ must be less than all the divisors of $\displaystyle 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 $\displaystyle n \leftrightarrow 2n$ .

We will now prove that every prime $\displaystyle p$ is safe, by strong induction. We have already proven the base case $\displaystyle p = 2$ . Now, for odd $\displaystyle p$ , $\displaystyle p+1$ is the product of odd primes less than $\displaystyle p$ , so $\displaystyle 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, $\displaystyle a$ and $\displaystyle b$ are safe, and $a \leftrightarrow ab \leftrightarrow b$ .

Solution 5

Similarly to the first solution, we observe that for any integer $\displaystyle 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 $\displaystyle k$ , $ka \leftrightarrow kb$ , for $\displaystyle (a+b) \mid (ab)$ implies $\displaystyle k(a+b) \mid k^2(ab)$ .

It is sufficient to prove that for any $\displaystyle a > 3$ , $a \leftrightarrow (a-1)$ . If $\displaystyle a$ is composite, then there exist $m \ge n > 0$ such that $\displaystyle (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, $\displaystyle a$ is prime, then we use strong induction. For the base case, $\displaystyle a = 5$ , we note $4 \leftrightarrow 3 \leftrightarrow 3(3-1) = 6 \leftrightarrow 5$ . Now, assuming that $\displaystyle a>5$ and that this holds for all primes less than $\displaystyle a$ (we know it holds for all composites), it is sufficient to show that $(a+1) \leftrightarrow (a-1)$ , since $\displaystyle (a+1)$ is composite and therefore $(a+1) \leftrightarrow a$ . But since $\displaystyle (a+1)$ and $\displaystyle (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 $\displaystyle a$ , and it is greater than 3, since $\displaystyle a > 5$ . Thus the induction is complete.

Resources

Retrieved from "http://www.artofproblemsolving.com/Wiki/index.php/2002_USAMO_Problems/Problem_5"

Category: Olympiad Number Theory Problems

Add a glimpse of the Art of Problem Solving Forum to your own site!
Click here for details!

© Copyright 2008 AoPS Incorporated. All Rights Reserved. • Foundation • Privacy • Contact Us