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 $.

No comments:

Post a Comment