When replying to the problem, I ask that you make posts for solutions and submit comments, jokes, smilies, etc. separately. Furthermore, please do not "hide" any portion of the solution. Please use LaTeX for posting solutions. Thanks.

Call two integers $a$ and $b$ "linked" if there exists a sequence as described in the question. We wish to show that all integers $a,b > 2$ are linked. If we can show that $m$ and $m+1$ are linked for any integer $m > 2$ in a finite number of terms (links), the problem is solved. Consider the following sequence: $m$, $m(m-1)$, $m(m-1)(m-2)$, $2m(m-1)$, $2m(m+1)$, $m(m+1)(m-1)$, $m(m+1)$, $m+1$, which can easily be shown to satisfy the property in the question. Thus $m$ and $m+1$ are always linked for $m > 2$. Hence, by induction, any integers $a, b > 2$ are linked, as desired.

Like paladin8, I'll call the two integers $ a$ and $ b$ "linked" if there exists a sequence as described in the problem. Clearly, $ a$ is linked to $ b$ iff $ b$ is linked to $ a$, and if $ a$ is linked to $ b$ and $ b$ is linked to $ c$, then $ a$ is linked to $ c$. I shall show that $ a$ is linked to the factorial of an even number greater than 2. We first note that $ x + y | xy$ iff $ x + y | x^2$. It follows that if $ d + 1 | a$, then $ a$ is linked to $ ad$, as $ a + ad = a(d + 1) | a^2$. $ (a-1)+1 | a$, so $ a$ is linked to $ a(a-1)$. $ (a-2)+1 | a - 1$, so $ a(a-1)$ is linked to $ a(a-1)(a-2)$. Repeating this process, we see that $ a$ is linked to $ a!$. If $ a$ is odd, then $ a + 1$ is even. Since $ 2 + 1 | a!$ and $ \frac{a+1}{2} + 1 | a!$ (because $ a \geq 3$), $ (a+1)a! = (a+1)!$ is linked to $ a!$. Hence, $ a$ is linked to the factorial of an even number. In addition, for any even number $ a \geq 4$, $ \frac{a+2}{2} + 1$ and $ 2 + 1 | a!$, so $ a!(a+2)$ is linked to $ a!$. Since $ (a+1) + 1 | a + 2$, we have that $ a!(a+1)(a+2) = (a+2)$ is linked to $ a!$. It follows that the factorials of any two even numbers greater than 2 are linked. But since every integer is linked to the factorial of an even number greater than 2, we are done by the transitive property.

I will use the word connected in the same manner as the posts above me used the word "linked". First of all, some things that we will use: Fact 1. If $ a,b$ are connected, then so are $ ka,kb$, for all positive integers $ k$. (Proof: Simply take the sequence that connects $ a$ and $ b$, then multiply all terms by $ k$.) Fact 2. $ a$ is connected to $ a(a-1)$. (Proof: Their sum is $ a^2$, which clearly divides $ a^2(a-1)$.) Fact 3. If $ x-1,x+1$ are connected, then $ x$ is connected to both these numbers. Proof: By Fact 1, if $ x-1,x+1$ are connected, then $ x(x-1), x(x+1)$ are connected. By Fact 2, $ x$ is connected to the first number and $ x+1$ is connected to the second number, so $ x$ is connected to these numbers. Now we prove that all integers are connected through induction. Assume that $ 3$ through $ 2n$ are all connected, for $ n \ge 3$. We can easily prove that 3 through 6 are connected: $ 3,6,12,4$ connects 3 and 4, and $ 3,6,30,20,5$ connects 3 and 5. This covers the base case $ n=3$. Now, as $ n,n+1$ are connected, Fact 1 tells us that $ 2n,2n+2$ are connected. By Fact 3, this implies that $ 2n+1$ is also connected, so all integers from $ 3$ through $ 2n+2$ are connected, completing our induction.

I shall show that for every integer $ n$, there exists a sequence from $ n$ to $ 3$. I use the same 'linked' term. From the sequence $ n,n(n - 1),n(n - 1)(n - 2)$ we have that $ n$ and $ n(n - 1)(n - 2) = N$ are linked. I will present an algorithm that leads this number to $ 3$. Note that, if a number $ k$ of the sequence is divisible by $ 3$, then the following term can be set $ 2k$ or $ k/2$. That is, the number obtained from multiplication or division of a number divisible by $ 3$ by a power of two (provided of course, that the result is an integer) is linked to the original number. Write $ N$ as $ 3.2^uv$ where $ v$ is odd. If $ v$ is $ 1$, then since $ 3.2^u$ and $ 3$ are linked, we are done. Assume $ v > 1$. I provide a means of decreasing this $ v$ (that is to say, to obtain a number $ 3.2^{u'}{v'}$ linked with $ 3.2^uv$ with odd $ v'$ and $ v' < v$). Let $ 2^m - 1 < v < 2^m$. Observe the following linked chain : $ 3.2^uv,3.2^mv,3.2^m(2^m - v)$. Since $ 0 < 2^m - v < v$ and $ 2^m - v$ is odd, going on like this, we eventually arrive at $ v = 1$.

Obviously, $a$ is linked to $a(a-1)$, $a(a-1)(a-2)$, ... $a!$. Similarly $b$ is linked to $b!$. If $a=b$, we are done; thus, WLOG $a>b$. We can link $b!$ to $a!/P$. Where P is the product of all primes (counting mulplicities) that are factors of $a!$ but not of $(b-1)!$. Consider the smallest of these primes $p$. Obviously $p+1$ is the product of two number that are smaller than $p$. Thus, we can link $a!/P$ to $a!(p^n)/P$ ($n$ is the number of times $p$ is a factor in $a!$). By induction, we can link $b!$ to $a!$. The only hole is if the $p+1$ factors into $(p-1)(2)$. In this case $p=3=b$. In this case, to get the extra factor of $3$, we link $b!=6$ to $12$ which we can then link to $36$. Since the smallest value of $a!$ that needs an extra factor of three is $6!=720$, we can easily still complete the linking.

Using the same terminology of "linked": All even numbers are linked, as $2x \rightarrow (2x^2-2x) \rightarrow (2x^2+2x) \rightarrow (2x+2)$ for $x \geq 2$. Also, each odd is linked to the even one above it, as $x \rightarrow (x^2-x) \rightarrow (x^2+x) \rightarrow (x+1)$ for odd $x \geq 3$. Thus, all numbers greater than $2$ are linked.

Consider a graph $G$ on the vertex set $\{3, \dots\}$ and with edges between $v$, $w$ if $v + w \mid vw$; the problem is equivalent to showing that $G$ is connected. First, note that $n$ is connected to $n(n-1)$, $n(n-1)(n-2)$, etc. up to $n!$. But for $n > 2$, $n!$ is connected to $(n+1)!$ by at most two steps: directly if $n$ is even, and otherwise letting $n+1=2k$, by $n! \to 2n! \to (n+1)!$. This concludes the problem.

It is obvious that if we find a sequence $n_1,...,n_k$ from $a$ to $b$ we can take the reversed sequence from $b$ to $a$. It is enough to prove that there is a sequence from $n$ to $n+1$ for all $n\ge 3$ as we can just adjoin the sequences. If we have found a sequence from $a$ to $b$ we'll write $a\leftrightarrow b$. We'll prove by strong induction that $n\leftrightarrow n+1$. For the base case, note that $3\leftrightarrow 6\leftrightarrow 12\leftrightarrow 4$ and $4\leftrightarrow 12\leftrightarrow 6\leftrightarrow 30\leftrightarrow 20\leftrightarrow 5$. For the induction step, if $n$ is odd $n\leftrightarrow n(n-1) \leftrightarrow n(n+1)\leftrightarrow n+1$. If $n$ is even, from the hypothesis of induction we have $\dfrac{n}{2}\leftrightarrow \dfrac{n}{2}+1$. Suppose that we can go from $\dfrac{n}{2}$ to $\dfrac{n}{2}+1$ by a sequence $\alpha_1,\alpha_2,..,\alpha_k$. Then we can go from $n$ to $n+2$ with the sequence $2\alpha_1,2\alpha_2,...,2\alpha_k$ , so $n\leftrightarrow n+2$. But $n+1$ is odd, so proceeding as earlier we infer that $n+1\leftrightarrow n+2$ and thus $n\leftrightarrow n+2\leftrightarrow n+1$.

Another solution: Note that a is linked to a(a-1). Repeating this gets that a is linked to a!. Likewise b is linked to b!. So it suffices to show that a! is linked to (a+1)!. There are two cases: a+1 is a prime, or it isn't a prime. If it isn't a prime, we can link a! to a!*($p_i$) for any prime factor $p_i$ of a+1. This is because any such prime factors are strictly less than a, and $p_i$ + 1 belongs in a!. Repeating this procedure links a! to (a+1)!. Otherwise, we link a! to a!(a+2) by considering each prime $q_i$ in a+2. Repeating this links to (a+2)!, which we then link to (a+1)! by considering $p_i$ + 1 for all $p_i$ in (a+2). Repeating the a! linking to (a+1)! step eventually links a! to b!, and we're done.

We say $a$ and $b$ are connected if they satisfy the problem condition. It suffices to show that both $a$ and $b$ are connected to some other number $c$, as we can then join the sequences to win. For convenience, if we see $3$, we immediately connect it to $6$, so we may assume that $a,b\ge 4$. Remark: This solution absolutely sucks, but it's also kind of nice for the following reason. Basically I was messing around and discovered the following lemma, at which point I knew the problem had to be true given this lemma. I simply closed my brain to everything else and bashed with this lemma, and viola, it worked. We have the following killer lemma. Lemma: Suppose we have a positive integer $n$, and $\ell\mid n$. Then, $n$ is connected to $(\ell-1)n$. Proof: Note that \[(\ell-1)n+n=\ell n\mid n^2(\ell-1),\]so in fact they are connected by one step. $\blacksquare$ We now have a claim that basically finishes. Recall that an integer $n$ is $k$-smooth if all of its prime factors are at most $k$. Claim: Suppose we have a positive integer $n\ge 4$ and $an!$ where $a$ is $(n-1)$-smooth. Then $an!$ is connected to $b(n+1)!$ where $b$ is some $n$-smooth positive integer. Proof: If $n+2$ is not prime, then we have $n+2\mid n!$, so $an!$ is connected to $a(n+2-1)n!=a(n+1)!$, so we're done. Now suppose that $n+2$ is prime. Then, $n+1$ is not prime so $n+1\mid n!$ (this assumes $n\ge 4$), so $an!$ is connected to $an\cdot n!$. We see that $n^2$ divides this, so this is connected to \[a(n^2-1)n\cdot n! = an(n-1)(n+1)!.\]Note that $an(n-1)$ is $n$-smooth since $a$ is $(n-1)$-smooth. This completes the proof of the claim. $\blacksquare$ The idea is that we can connect any $n$ to $n!$ by iteratively applying the lemma. Then, by iteratively applying the claim, we can connect it to $x\cdot N!$ where $N\gg n$ and $x$ is $(N-1)$-smooth. So we connect $a$ to $x\cdot N!$ and $b$ to $y\cdot N!$ where $N\gg x,y$, and $x$ and $y$ are $(N-1)$-smooth. The idea is that for any prime $p\le N-1$, we have $p+1\mid N!$, so $z\cdot N!$ is connected to $zp\cdot N!$. Since $x$ and $y$ are both $(N-1)$-smooth, this means we can connect both to $\mathrm{lcm}(x,y)\cdot N!$, so we're done.

This problem was on JBMO, not USAMO.

Consider the infinite graph $G$ with vertices all psoitive integers at least 3, and an edge $a\to b$ if $a+b\mid ab$. Note that there is an edge $a\to b$ iff there is an edge $b\to a$, so the graph is undirected. We want to show this graph is connected. Claim: There is an edge $a\to ka$ iff $k+1\mid a$, for any $k,a$. Proof. The edge exists iff $a+ka\mid a^2k \iff 1+k \mid ak \iff k+1\mid (k+1)a-ak = a$. $\square$ Fix some positive integer $n\ge 3$. By the lemma, there is an edge from $n(n-1)\cdots (n-k) $ to $n(n-1)\cdots (n-k-1)$ for any $0\le k\le n-1$. Therefore, $n$ is connected to $n!$. Similarly, $n+1$ is connected to $(n+1)!$ by a path. If we can show, therefore, that $n!$ and $(n+1)!$ by a path, we would get a path from $n$ to $n+1$, which clearly finishes. Case 1: $n+1$ is prime. Then, in fact, we claim $n!$ is connected to $(n+1)!$ by an edge. By the lemma, this is true iff $n+2\mid n!$, which is true since $n+2$ is composite. Case 2: $n+1$ is composite. Suppose $n+1=p_1p_2\cdots p_k$, where the $p_i$'s are not neccesarily distinct. Then, $n!\cdot p_1\cdots p_\ell$ is connected to $n!\cdot p_1\cdots p_{\ell+1}$ by the lemma, since $p_{\ell+1} + 1\mid n!$, so we are done. Therefore, $n!$ is connected to $(n+1)!$, so we're done.

I don't think anyone has posted this solution, so here's the solution I came up with: First, using the terminology of linking, we define $a\sim b$ is there exists an integer $c$ such that $\frac1{a}+\frac1{b}=\frac1{c}$ (equivalent to the above condition) and $a\approx b$ if there exist $x_i$ such that $a\sim x_0\sim x_1\dots \sim b$. We see trivially see that $ka\sim kb$ if and only if $a\sim b$ and also easily derive that if $a>b$, $ab\sim a(a-b)$. For the special case of $b=1$ it follows that if $p|a$ then $a\sim a(p-1)$. Now we proceed to prove that $n\approx 3$ for all integer $n>2$. We may assume $n$ is even, otherwise we can multiply by $n$ by $p-1$, where $p$ is a factor of $n$, odd by assumption, thus making $p-1$ even. Now let us assume that $n$ is not a power of $2$, let $p>2$ be the largest prime factor of $n$ and let us write $n=2ps$. We obtain: $$n=2ps\sim 2(p-1)ps \sim 2(p-1)(2(p-1)-p)s=2(p-1)(p-2)s.$$Note that the new number is now divisible by $4$. We keep eliminating the largest prime until we obtain $n\approx 2^k$ for $k\geq 2$. If $n$ is a degree of $2$ we have this form right away, since by the condition of the problem $a>2$. Now we write: $$n\approx 2^k=2^{k-2}\cdot 4\cdot 1\sim 2^{k-2}\cdot 4\cdot (4-1)=3\cdot2^k\sim 3\cdot2^{k-1}\sim\dots\sim 3.$$Thus, $n\approx 3$ for all $n$ and since the relation is transitive $a\approx b$ for all integers $a$ and $b$ larger than $2$.

Solution with awang11. Use $\to$ in the obvious way. We use induction but first resolve two mildly annoying base cases: we can connect $3$ and $4$ with a chain, and we can connect $4$ and $8$ with a chain. For the first part, observe the chain \[4\to 12\to 6\to 3.\]For the second part, observe the chain \[4\to 12\to 24\to 8.\]In the remainder of this proof, we avoid such computations. First, note that if one can form a chain $m\to r$, one can form a chain $nm\to nr$ by noting that for each $a\to b$ we have $n(a+b)\mid (na)(nb)$. This implies there is a chain $4\to 8=2(4)\to 2(8)=16$. Then, if for a set $M\ni 2$ of primes we know that each prime not equal to $2$ can be reached from $4$, for all products $\prod_i p_i^{e_i}$ with each $p_i\in M$, we can show there is a chain from this product to $4$ by taking each $p_i\ne 2$ to $4$ so the product becomes a power of $2$, then using the argument showing there is a chain $4\to 16$ to finish. Then we can induct upwards on primes to show they can be taken to $4$. The base case of $p=3$ has already been dealt with. Noting $p+1$ must divide $p!$ for $p\ge 5$, we observe the chain \[p\to p(p-1)\to p(p-1)(p-2)\to \cdots \to p!\to (p-1)!\to (p-1)(p-2)\cdots 3\to \cdots\to (p-1)(p-2)\to p-1.\]This finishes.

We show we can always transport $j$ to $j+1$ or vice versa. This solves the problem. We can go from $x$ to $(k-1)x$ for any $k >2$ as long as $k|x$ (Boils down to $\frac{(k-1)x}{k}$ being integral). Thus, $j!$ is achievable from $j$ and $(j+1)!$ is achievable from $j+1$. We see that we need $\frac{(j+1)!}{(j+2)}$ to be integral for a direct connection, which holds unless $j+2$ is either $4$ or prime. Because $j>2$, we are guaranteed $j+2$ is an odd prime. Now, we circumvent the situation entirely, by going $j \to \frac{j^2 -j}{2} \to \frac{j^2 +j}{2} \to j+1$, where the middle holds because $j$ is odd.

MithsApprentice wrote: Let $a,b$ be integers greater than 2. Prove that there exists a positive integer $k$ and a finite sequence $n_1, n_2, \dots, n_k$ of positive integers such that $n_1 = a$, $n_k = b$, and $n_i n_{i+1}$ is divisible by $n_i + n_{i+1}$ for each $i$ ($1 \leq i < k$). Two integers are linked by arrows if $$n_i + n_{i+1}|n_i n_{i+1}$$. FTSOC,the condition doesnt hold. Notice that $$n \to n(n-1) \to n(n-1)(n-2) ........................ \to n!$$and $n! \to n!(n!-1)$ implying $n \to n!(n!-1)$ which is a contradiction since this implies $$1+(n!+1)(n-1)!|(n-1)!$$which is impossible.$\blacksquare.$

Clearly we only need to consider when $a<b$. Now, if we can show this for $b=a+1$, we are done. When $a$ is odd, we can do: $$a\rightarrow a(a-1)\rightarrow a(a+1)\rightarrow a+1.$$ When $a$ is $4$, we can do: $$4\rightarrow 12\rightarrow 60\rightarrow 20\rightarrow 5.$$ When $a$ is an even greater than $4$ notice that if we can go from $a$ to $a+2$ then we can get to $a+1$. So we need to get from $a$ to $a+2$ which is equivalent to taking the sequence formed by going from $\frac{a}{2}$ to $\frac{a}{2}+1$ and multiplying by $2$. But eventually it becomes odd (or $4$ when $a$ is a power of $2$) so we are done. Here is an example for $20\rightarrow 21$: $$20\rightarrow 80\rightarrow 120\rightarrow 24\rightarrow 264\rightarrow 220\rightarrow 22\rightarrow 462\rightarrow 420\rightarrow 21.$$

we say $x \to y$ if $x+y$ divides $xy$. We have the following identity \[ k \to k(k-1) \to k(k-1)(k-2) \to \cdots \to k! \to (k+1)! \to \cdots \to (k)(k+1) \to k+1.\]Applying this result inductively yields $a \to b$.

@above I am a little bit confused on the k!->(k+1)! step. What if k+2 is prime? Call a sequence with the given property a "linked" sequence. Note that going from one term (t) of the sequence to the next you can do both of the following: -multiplying by x-1 where x|t -dividing by x-1 where x-1|t and x|t Note that if you multiply every term of a linked sequence by the same amount you will still get a linked sequence. Let a>b WLOG. There is a linked sequence from a to a!, so it suffices to show that there is a linked sequence from a! to b. We claim that for every prime p>2, there is a linked sequence from p to (p-1)!. There must be a linked sequence from p to p!. Because p+1 is not prime, p+1|p!. Thus, you can divide by p to get the next term, which is (p-1)!. Let x=a!/b. Assume x is not a power of 2. Let p be the greatest prime factor of x. Because of the property above, there is a linked sequence from x to another number whose prime factors are all less than p. By induction, there is a linked sequence between x and $2^n$ for some integer n. Therefore, there is a linked sequence between a! and $2^nb$ for some integer n. If n=1, then do the following: 2b-->(b-2)b-->b(b-1)(b-2)-->b(b-1)-->b. If n=2, then do the following: 4b-->(b-4)b-->-->-->(b-4)(b-3)(b-2)(b-1)b-->-->-->b. Otherwise, we will show there is a linked sequence from $2^nb$ to 4b. To do this it is sufficient to show that there is a linked sequence from $2^nb$ to $2^{n-1}b$. Do the following: $2^nb$ --> $3\cdot 2^nb$ --> $3\cdot 2^{n-1}b$ --> $2^{n-1}b$.

我们可以对素数归纳。

Call two numbers $x$ and $y$ reachable if they satisfy the conditions of the problem when $x=a$ and $y=b.$ The relation of reachable is an equivalence relation. First, we claim that if $x,y$ are reachable then $mx,my$ is also reachable. Suppose that $p_1, p_2, \dots, p_k$ is the sequence described in the problem statement, then we multiply each term by $m$. Since $p_ip_{i+1}$ is scaled by $m^2$ and $p_i+p_{i+1}$ is scaled by $m$, the condition is still satisfied. Next, note that if $x(x-1),y(y-1)$ are reachable then since $x,x(x-1)$ are reachable and $y,y(y-1)$ are reachable, so $x,y$ are reachable. We have $(3k+1)(3k), (3k+1)(6k)$ are reachable, $(3k+1)(6k), (6k)(3k-1)$ are reachable, and $(6k)(3k-1),(3k)(3k-1)$ are reachable. Thus, $3k+1,3k$ are reachable for all $k$. Note that $x$ and $x(x-1)$ are reachable, and that $x(x-1)$ and $x(x-1)(x-2)$ are also reachable. By simple induction, we find that $x$ and $x!$ are reachable. Now, since $(3x+2)!$ and $(3x+1)!$ are reachable, $3x+2$ and $3x+1$ are reachable. It follows that all pairs of integers are reachable.

Say that an ordered pair $(a,b)$ is very good if $a+b\mid ab$, or equivalently, $a+b\mid a^2$ or $a+b\mid b^2.$ Say that an ordered pair $(a,b)$ is good if there exists a sequence of real numbers $s_1,s_2\cdots s_m$ such that $(a,s_1),(s_1,s_2)\cdots (s_m,b)$ are all very good. The problem is equivalent to showing that $(a,b)$ is good for all $a,b\geq 3$. It then suffices to show that $(n,n+1)$ is good for all $n\geq3$, since goodness is both transitive and symmetric. Note that $(n,n(n-1))$ is always very good. Furthermore, $(n(n-1),n(n-1)(n-2))$ is always very good, and so on, so $(n,n!)$ is good. Similarly, $(n+1,(n+1)!)$ is good. Then, it suffices to show that $(n!,(n+1)!)$ is good. If $n+2$ is not prime, then $(n!,(n+1)!)$ is already very good. Otherwise, $(n!,2n!)$ is very good, and $(2n!,(n+1)!)$ is also very good since we know that $n+3$ is not prime, hence done.

Consider a graph $G$ whose vertices represent the numbers from set $\{3,4,5,\ldots\}$. Two vertices with numbers $a,b$ are connected if and only if $a+b\mid ab$. We show that the entire graph is connected. Note that for every $n$, $n$ and $n(n-1)$ are connected because $n(n-1)+n=n^2\mid n^2(n-1)$. For $n$ being odd, we also have $n(n-1)+n(n+1)=2n^2\mid n^2(n-1)(n+1)$. So, $n(n-1)$ and $n(n+1)$ are connected for odd $n$. Hence, if $n$ is odd and $n+1$ is even, then there is a path from $n$ to $n+1$. Note that $n(n-1)(n-2)+n(n-1)=n(n-1)^2\mid n^2(n-1)^2(n-2)$. Similarly, $n(n-1)(n-2)(n-3)$ and $n(n-1)(n-2)$ are connected. Hence, there is a path between $n(n-1)\cdots(n-i)$ for each $0\leq i\leq n-1$ for every $n$. Also, if $n$ is taken even, then $n+2$ cannot be prime as $n+2>2$, which means that $n!+(n+1)!=n!(n+2)\mid n!(n+1)!$. It follows that $n$ and $n+1$ have a path between them if $n$ is even. Combining the two results, we get that there is a path between any two vertices, which means that the graph is connected.