# 2002 USAMO Problems/Problem 5

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

## 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=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 $\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.