Problem
Source: IMO ShortList 2001, algebra problem 5
Tags: inequalities, algebra, recurrence relation, equation, Integer sequence, IMO Shortlist, imo shortlist 2001
30.09.2004 20:20
Please post your solutions. This is just a solution template to write up your solutions in a nice way and formatted in LaTeX. But maybe your solution is so well written that this is not required finally. For more information and instructions regarding the ISL/ILL problems please look here: introduction for the IMO ShortList/LongList project and regardingsolutions
10.09.2008 00:48
" wrote: let $ a_1,a_2,\ldots ,a_n$ be such numbers,we have $ a_{k - 1} < a_k$ hence for $ k = 2,3,\ldots ,n - 1$ we get that $ 2\leq k$. now we can rewrite the inequality $ (a_{k + 1} - 1)a_{k - 1}\geq a_k^2(a_k - 1)$ as: $ \frac {a_{k - 1}}{a_k} + \frac {a_k}{a_{k + 1} - 1}\leq\frac {a_{k - 1}}{a_k - 1}$ now if we write this inequality for $ k = i + 1,i + 2,\ldots ,n - 1$ and add them up,according to the obvious inequality $ \frac {a_{n - 1}}{a_n} < \frac {a_{n - 1}}{a_n - 1}$,we'll get that: $ \frac {a_i}{a_{i + 1}} + \frac {a_{i + 1}}{a_{i + 2}} + \ldots + \frac {a_{n - 1}}{a_n}\leq\frac {a_i}{a_{i + 1} - 1}$ now if we use the above inequality for $ i = 0$,according to the given equation,we would have: $ \frac 1{a_1}\leq\frac {99}{100} < \frac 1{a_1 - 1}$ hence $ a_1 = 2$. similarly for $ i = 1$ we get that: $ \frac 1{a_2}\leq\frac 1{a_1}\left(\frac {99}{100} - \frac 1{a_1}\right) < \frac 1{a_2 - 1}$ which yields $ a_2 = 5$. in a similar way we conclude that $ a_3 = 56$ and $ a_4 = 25\times 56^2 = 78400$. but for $ a_5$ we would end up with: $ \frac 1{a_5}\leq\frac 1{a_4}\left(\frac {99}{100} - \frac 12 - \frac 25 - \frac 5{56} - \frac {56}{25\times 56^2}\right) = 0$ which is impossible. also we can easily see that $ a_1 = 2,a_2 = 5,a_3 = 56,a_4 = 25\times 56^2$ is a solution,and also this solution shows that this set of numbers are the only valid answer.
01.08.2014 06:07
First, I shall show by reverse induction that $ \frac{99}{100} - \frac{a_0}{a_1} - \frac{a_1}{a_2} - \dots - \frac{a_{i - 1}}{a_i} \leq \frac{a_i}{a_{i + 1} - 1} $ for all nonnegative integers $ i < n $. For the base case, letting $ i = n - 1 $ it suffices to show that $ \frac{99}{100} - \frac{a_0}{a_1} - \frac{a_1}{a_2} - \dots - \frac{a_{n - 2}}{a_{n - 1}} = \frac{a_{n - 1}}{a_n} \leq \frac{a_{n - 1}}{a_n - 1} $ which is trivial. Now, assume that for some positive integer $ m < n $ we have that $ \frac{99}{100} - \frac{a_0}{a_1} - \frac{a_1}{a_2} - \dots - \frac{a_{m - 1}}{a_m} \leq \frac{a_m}{a_{m + 1} - 1} (*) $. I shall show that $ \frac{99}{100} - \frac{a_0}{a_1} - \frac{a_1}{a_2} - \dots - \frac{a_{m - 2}}{a_{m - 1}} \leq \frac{a_{m - 1}}{a_m - 1} $. It clearly suffices to show that $ \frac{a_{m - 1}}{a_m} \leq \frac{a_{m - 1}}{a_m - 1} - \frac{a_m}{a_{m + 1} - 1} $, because adding this to $ (*) $ then yields the desired result. But upon expansion this is equivalent to the following inequality: $ (a_{m + 1} - 1)a_{m - 1} \geq a_{m}^2(a_m - 1) $ which we know to be true. Therefore the induction hypothesis holds. Now, since $ \frac{99}{100} - \frac{a_0}{a_1} - \frac{a_1}{a_2} - \dots - \frac{a_{i - 1}}{a_i} = \frac{a_i}{a_{i + 1}} + \frac{a_{i + 1}}{a_{i + 2}} + \dots + \frac{a_{n - 1}}{a_n} \geq \frac{a_i}{a_{i + 1}} $ we have that $ \frac{a_i}{a_{i + 1}} \leq \frac{99}{100} - \frac{a_0}{a_1} - \frac{a_1}{a_2} - \dots - \frac{a_{i - 1}}{a_i} \leq \frac{a_i}{a_{i + 1} - 1} (**) $ for all nonnegative integers $ i < n $. This inequality clearly implies that all of the $ a_i $ are uniquely determined. Letting $ i = 0 $ in $ (**) $ we find that $ a_1 = 2 $. Plugging in $ i = 1 $ we find that $ a_2 = 5 $. Continuing in this fashion we find that the only solution is given by $ (a_0, a_1, a_2, a_3, a_4) = (1, 2, 5, 56, 25^2 \cdot 56) $. I want to provide some motivation for this solution. The idea for finding $ (**) $ comes from the greedy algorithm... by applying it to the problem we immediately get a solution, and then it is pretty likely that we want to show that this is the only solution. The greedy algorithm works by finding an $ a_i $ that satisfies $ (**) $ every time we plug in a new $ i $ so it is natural to try to prove that $ (**) $ must always hold, and then induction becomes apparent. Despite its similarity to the above solution posted by BaBaK Ghalebi, I wanted to post this because his solution seems to magically derive an identity from the given inequality that trivializes the problem seemingly without motivation.
31.03.2020 09:54
Sorry, ignore.
10.12.2023 17:01
Twoisaprime wrote: First, I shall show by reverse induction that $ \frac{99}{100} - \frac{a_0}{a_1} - \frac{a_1}{a_2} - \dots - \frac{a_{i - 1}}{a_i} \leq \frac{a_i}{a_{i + 1} - 1} $ for all nonnegative integers $ i < n $. For the base case, letting $ i = n - 1 $ it suffices to show that $ \frac{99}{100} - \frac{a_0}{a_1} - \frac{a_1}{a_2} - \dots - \frac{a_{n - 2}}{a_{n - 1}} = \frac{a_{n - 1}}{a_n} \leq \frac{a_{n - 1}}{a_n - 1} $ which is trivial. Now, assume that for some positive integer $ m < n $ we have that $ \frac{99}{100} - \frac{a_0}{a_1} - \frac{a_1}{a_2} - \dots - \frac{a_{m - 1}}{a_m} \leq \frac{a_m}{a_{m + 1} - 1} (*) $. I shall show that $ \frac{99}{100} - \frac{a_0}{a_1} - \frac{a_1}{a_2} - \dots - \frac{a_{m - 2}}{a_{m - 1}} \leq \frac{a_{m - 1}}{a_m - 1} $. It clearly suffices to show that $ \frac{a_{m - 1}}{a_m} \leq \frac{a_{m - 1}}{a_m - 1} - \frac{a_m}{a_{m + 1} - 1} $, because adding this to $ (*) $ then yields the desired result. But upon expansion this is equivalent to the following inequality: $ (a_{m + 1} - 1)a_{m - 1} \geq a_{m}^2(a_m - 1) $ which we know to be true. Therefore the induction hypothesis holds. Now, since $ \frac{99}{100} - \frac{a_0}{a_1} - \frac{a_1}{a_2} - \dots - \frac{a_{i - 1}}{a_i} = \frac{a_i}{a_{i + 1}} + \frac{a_{i + 1}}{a_{i + 2}} + \dots + \frac{a_{n - 1}}{a_n} \geq \frac{a_i}{a_{i + 1}} $ we have that $ \frac{a_i}{a_{i + 1}} \leq \frac{99}{100} - \frac{a_0}{a_1} - \frac{a_1}{a_2} - \dots - \frac{a_{i - 1}}{a_i} \leq \frac{a_i}{a_{i + 1} - 1} (**) $ for all nonnegative integers $ i < n $. This inequality clearly implies that all of the $ a_i $ are uniquely determined. Letting $ i = 0 $ in $ (**) $ we find that $ a_1 = 2 $. Plugging in $ i = 1 $ we find that $ a_2 = 5 $. Continuing in this fashion we find that the only solution is given by $ (a_0, a_1, a_2, a_3, a_4) = (1, 2, 5, 56, 25^2 \cdot 56) $. I want to provide some motivation for this solution. The idea for finding $ (**) $ comes from the greedy algorithm... by applying it to the problem we immediately get a solution, and then it is pretty likely that we want to show that this is the only solution. The greedy algorithm works by finding an $ a_i $ that satisfies $ (**) $ every time we plug in a new $ i $ so it is natural to try to prove that $ (**) $ must always hold, and then induction becomes apparent. Despite its similarity to the above solution posted by BaBaK Ghalebi, I wanted to post this because his solution seems to magically derive an identity from the given inequality that trivializes the problem seemingly without motivation.
23.07.2024 15:58
Answer: $n=4$ and $(a_0, a_1, a_2, a_3, a_4) = (1, 2, 5, 56, 25^2 \cdot 56)$. We begin by transforming our condition into something a bit nicer. Note that \[(a_{k+1}-1)a_{k-1} \geq a_k^2(a_k-1) \implies \frac{a_{k-1}}{a_k} \geq a_k \cdot \frac{a_k-1}{a_{k+1}-1} > a_k \cdot \frac{a_k}{a_{k + 1}}\]Since we can't have $\frac{a_{k-1}}{a_k} \geq 1 > \frac{99}{100}$, we can conclude that $a_{k+1} > a_k^2 \implies a_{k} > a_1^{2^{k-1}}$. Plugging this back into our condition and applying induction, we achieve \[\frac{a_{0}}{a_1} \geq a_1a_{2} \dots a_{k} \frac{a_{k}}{a_{k+1}} \geq a_i^{2^{k}-1}\frac{a_k}{a_{k+1}} \implies \frac{a_0}{a_1^{2^{k}}} > \frac{a_k}{a_{k+1}}\]Now, we show that our sequence $a_1, a_2, \dots, a_n$ is uniquely determined. Since we only use the fact that $\frac{99}{100} < 1$, by shifting, it suffices to show that $a_1$ is uniquely determined. Notice that \[\frac{99}{100} = \frac{a_0}{a_1} + \frac{a_1}{a_2} + \dots + \frac{a_{n-1}}{a_n} < \sum\limits_{i=0}^{\infty}\frac{a_0}{a_1^{2^i}} < \sum\limits_{i=1}^{\infty}\frac{a_0}{a_1^i}=\frac{a_0}{a_1-1}\]Now, we have $\frac{a_0}{a_1} \leq \frac{99}{100} < \frac{a_0}{a_1-1}$ which implies that $a_1$ is uniquely determined, as desired. We can easily find the answer by substituting the values into the inequality. $\blacksquare$