Sunday, February 26, 2006

Linkage. Topic: NT/Sequences and Series. Level: Olympiad.

Problem: (2002 USAMO - #5) 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_i n_{i+1}$ is divisible by $n_i + n_{i+1}$ for each $i$ ($1 \leq i < k$).

Solution: Call two integers $a$ and $b$ "linked" if there exists a sequence as described in the question (note that two integers are always mutually linked; just reverse the sequence). 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 (assuming WLOG $a
--------------------

Comment: The proof of this, when presented, is very short. In actuality, this problem took quite a while to solve; first to figure out to try and link consecutive integers and then to actually find the link. Playing around with the numbers eventually gave the right sequence.

No comments:

Post a Comment