## Wednesday, January 25, 2006

### Lots of Terms. Topic: Number Theory. Level: Olympiad.

Problem: (1975 IMO - #2) Let $a_{1}, \ldots, a_{n}$ be an infinite sequence of strictly positive integers, so that $a_{k} < a_{k+1}$ for any $k$. Prove that there exists an infinity of terms $a_{m}$, which can be written like $a_m = x \cdot a_p + y \cdot a_q$ with $x,y$ strictly positive integers and $p \neq q$.

Solution: Let's take two cases - there exist $a_i, a_j$ that are relatively prime and there don't exist such members of the sequence.

Well if $(a_i, a_j) = 1$, we can just use the Chicken McNugget Theorem and we can find $x,y > 0$ such that $a_ix+a_jy = a_m$ for all $a_m > a_ia_j-a_i-a_j$. There are an infinite number of such $a_m$ because the sequence is strictly increasing.

Now suppose there don't exist such $a_i,a_j$. Since $a_1$ is not relatively to any of the infinite other terms and it only has a finite number of divisors, at least one divisor $d$ of $a_1$ divides an infinite number of other terms in the sequence by the Infinite Pigeonhole Principle. Then consider the sequence $\left\{\frac{a_i}{d}\right\}_{d|a_i}$. We can then apply the same two cases on this sequence and keep going until the first condition holds true (this process terminates because $a_1$ only has a finite number of divisors - at some point it will either be relatively prime to another member of the sequence or equal $1$ and be relatively prime anyway).

Therefore there always exist infinitely many $a_m$ satisfying the condition. QED.

--------------------

Comment: An interesting problem, more so the second case, though. Sort of like a recursive function with a terminating condition. In any case, in the recursion it's important to specify that it will eventually terminate, or it won't be a valid justification.

--------------------

Practice Problem: Prove the Chicken McNugget Theorem - given two positive integers $a,b$ such that $(a,b) = 1$, the largest value of $n$ such that there do not exist positive integers $x,y$ with $ax+by = n$ is $n = ab-a-b$.