Problem:
Let a,b be integers greater than 2. Prove that there exists a positive integer k and a finite sequence n1​,n2​,…,nk​ of positive integers such that n1​=a,nk​=b, and ni​ni+1​ is divisible by ni​+ni+1​ for each i(1≤i<k).
Solution:
First Solution: We write a↔b if the desired sequence exists. Note that for positive integer n with n≥3,n↔2n as the sequence
n1​=n⋅n2​=n(n−1)⋅n3​=n(n−1)(n−2),n4​=n(n−2)⋅n5​=2n
satisfies the conditions of the problem. For positive integer n≥4,n′=(n−1)(n−2)≥ 3. hence n′↔2n′ by the above argument. It follows that n↔n−1 for n≥4 by n′↔2n′ and by the sequences
​n1​=n,n2​=n(n−1),n3​=n(n−1)(n−2),n4​=n(n−1)(n−2)(n−3)n5​=2(n−1)(n−2)=2n′​
and n1′​=n′=(n−1)(n−2),n2′​=n−1. Iterating this, we connect all integers larges than 2 .
Second Solution: We write a↔b if the desired sequence exists. Jote that this relation is symmetric (a↔b implies b↔a) and transitive (a↔b,b↔c imply a↔a. Our crucial observation will be the following: If d>2 and n is a multiple of d. then n↔(d−1)n. Indeed, n+(d−1)n=dn∣∣∣​n2∣∣∣​(d−1)n2=n⋅(d−1)n.
Let us call a positive integer k safe if n↔kn for all n>2. Notice by transitivity that any product of safe numbers is safe. Now, we claim that 2 is safe. To prove this. define f(n), for n>2, to be the smallest divisor of n which is greater than 2 . We show that n↔2n by strong induction on f(n). In case f(n)=3, we immediately have n→2 " by our earlier observation. Otherwise, notice that f(n)−1 is a divisor of (∫(n)−1 m which is greater than 2 and less than f(n) : thus f((f(n)−1)n)<f(n). and the induction hypothesis gives (f(n)−1)n↔2(f(n)−1)n. We also have n↔(f(n)−1m (by our earlier observation) and 2(f(n)−1)n↔2n (by the same observation. since f(n)∣n∣2n). Thus, by transitivity, n↔2n. This completes the induction step and proves the claim.
Next, we show that any prime p is safe, again by strong induction. The base case p=2 has already been done. If p is an odd prime, then p+1 is a product of primes strictly less than p. which are safe by the induction hypothesis; hence, p+1 is safe. Thms. For any n>.
n↔(p+1)n↔p(p+1)n↔pn
This completes the induction step. Thus, all primes are safe, and hence every integr ≥2 is safe. In particular, our given numbers a,b are safe, so we have a↔ab↔b. as needed.
The problems on this page are the property of the MAA's American Mathematics Competitions