Difference between revisions of "2004 IMO Shortlist Problems/A2"
(+ solution, weaker result) |
|||
Line 4: | Line 4: | ||
An infinite sequence <math> a_0, a_1, a_2, \ldots </math> of real numbers satisfies the condition | An infinite sequence <math> a_0, a_1, a_2, \ldots </math> of real numbers satisfies the condition | ||
<center> | <center> | ||
− | <math> | + | <math>a_n = | a_{n+1} - a_{n+2} | \qquad </math> for every <math> n \ge 0 </math>, |
</center> | </center> | ||
− | with <math> | + | with <math>a_0 </math> and <math>a_1 </math> positive and distinct. Can this sequence be bounded? |
''This was also Problem 4 of the 2005 German Pre-[[TST]] and Problem 1 of the first 2005 black [[MOP]] test. It was Problem 3, Day 2 of the 2005 Romanian TST in the following form:'' | ''This was also Problem 4 of the 2005 German Pre-[[TST]] and Problem 1 of the first 2005 black [[MOP]] test. It was Problem 3, Day 2 of the 2005 Romanian TST in the following form:'' | ||
− | A sequence of real numbers <math> | + | A sequence of real numbers <math>\{a_n\}_n </math> is called a ''bs'' sequence if <math>a_n = |a_{n+1} - a_{n+2}| </math>, for all <math>n\geq 0 </math>. Prove that a bs sequence is bounded if and only if the function <math>f </math> given by <math>f(n,k)=a_na_k(a_n-a_k) </math>, for all <math>n,k\geq 0 </math> is the null function. |
+ | __TOC__ | ||
== Solution == | == Solution == | ||
− | + | === Solution 1 === | |
− | We note that each of the <math> | + | We note that each of the <math>a_i </math> must be nonnegative. |
'''Lemma 1.''' If the two initial terms of the sequence are nonzero and distinct, then every term of the sequence is nonzero and no two consecutive terms are equal. | '''Lemma 1.''' If the two initial terms of the sequence are nonzero and distinct, then every term of the sequence is nonzero and no two consecutive terms are equal. | ||
Line 21: | Line 22: | ||
Consider a sequence <math> \{b_i\}_{i=0}^{\infty} </math> of positive reals which obeys the recursive relation | Consider a sequence <math> \{b_i\}_{i=0}^{\infty} </math> of positive reals which obeys the recursive relation | ||
− | <center> <math> | + | <center> <math>b_{n+2} = |b_{n+1} - b_n | </math>. </center> |
'''Lemma 2.''' <math> \min (b_i, b_{i+1}, b_{i+2}) \ge \min (b_{i+3}, b_{i+4}, b_{i+5}) </math>. | '''Lemma 2.''' <math> \min (b_i, b_{i+1}, b_{i+2}) \ge \min (b_{i+3}, b_{i+4}, b_{i+5}) </math>. | ||
− | ''Proof.'' We note that if <math> | + | ''Proof.'' We note that if <math>b_k \le b_{k+1} </math>, then <math>b_{k+2} = b_{k+1} - b_k </math> and <math>b_{k+3} = b_k </math>. Thus if <math>b_{i+3}, b_{i+4}, b_{i+5} > \min(b_i, b_{i+1}, b_{i+2}) </math>, we must have <math>b_i, b_{i+1} > b_{i+2} > b_{i+3} </math>, a contradiction. |
'''Lemma 3.''' Let <math> r = \left\lfloor \frac{b_{k-1}}{b_k} \right\rfloor </math>, <math> j = \left\lceil \frac{3}{2}r \right\rceil </math>. Then <math> \min (b_{k+j},b_{k+j+1},b_{k+j+2}) \le \frac{1}{2}b_{k+1} </math>. | '''Lemma 3.''' Let <math> r = \left\lfloor \frac{b_{k-1}}{b_k} \right\rfloor </math>, <math> j = \left\lceil \frac{3}{2}r \right\rceil </math>. Then <math> \min (b_{k+j},b_{k+j+1},b_{k+j+2}) \le \frac{1}{2}b_{k+1} </math>. | ||
− | ''Proof.'' For <math> 2i+2 \le r </math>, easy induction yields <math> | + | ''Proof.'' For <math> 2i+2 \le r </math>, easy induction yields <math>b_{k+3i} = b_k </math>, <math>b_{k+3i+1} = b_{k-1} - (2i+1)b_k </math>, <math>b_{k+3i+2} = b_{k-1} - (2i+2)b_k </math>. |
+ | |||
+ | Now, if <math>r </math> is even, we have <math>b_{k+3r/2 - 1} = b_{k-1} - b_kr </math>, which is less than <math>b_k </math> by the definition of <math>r </math>, and <math>b_{k+3r/2} = b_k </math>, <math>b_{k+3r/2 +1} = b_{3r/2} - b_{k+3r/2-1} </math>, <math>b_{k+3r/2+2} = b_{k+3r/2} </math>. Since <math>b_{k+3r/2+1} </math> and <math>b_{k+3r/2+2} </math> add to <math>b_{3r/2} = b_k </math>, one of them must be at most <math> \frac{b_k}{2} </math>, and the lemma follows. | ||
+ | |||
+ | On the other hand, if <math>r </math> is odd, then set <math>s = r-1 </math> and we have <math>b_{k+3s/2+1} = b_{k-1} - b_kr < b_k </math>, <math>b_{k+3s/2 + 2} = b_k </math>, and <math>b_{k+3s/2+3} = b_{k+3s/2 + 2} - b_{k+3s/2+1} </math>, so as before, at least one of <math>b_{k+3s/2+1} </math>, <math>b_{k+3s/2+3} </math> must be at most <math> \frac{b_k}{2} </math>. In fact, we have <math>{} b_{k+3s/2+4}= b_{k+3s/2+1} </math>, so the minimum of <math>b_{k+3s/2+3}, b_{k+3s/2+4} </math> is at most <math>\frac{b_k}{2} </math>, upholding the lemma, since in this case <math> \left\lceil \frac{3}{2}r \right\rceil = \frac{3}{2}s+2 </math>. | ||
+ | |||
− | Now, | + | Now, suppose that <math>\{ a_i \}_{i=0}^{\infty} </math> is bounded, i.e., there exists some real <math>N </math> greater than each <math>a_i </math>. By setting <math>b_1, b_0 </math> equal to <math>a_{n-1}, a_n </math>, we generate the first <math>n </math> of the <math>a_i </math> in reverse, and from Lemma 2, we can see that <math>m = \min (a_1,a_2,a_3) </math> is a lower bound of the <math>a_i </math>. But by making <math>n </math> greater than <math> \lceil \log_2 (N/m) +1 \rceil \left\lceil \frac{3}{2} \left\lfloor \frac{N}{m} \right\rfloor \right\rceil </math>, by applying Lemma 3, we obtain the result <math>m \le \frac{1}{2} m </math>, which is a contradiction when <math>a_0, a_1 </math> are distinct and greater than 0, by Lemma 1. |
− | + | Now, if <math>a_na_k(a_n-a_k) = 0 </math> for all natural <math>n </math>, all the nonzero <math>a_i </math> must be equal and the sequence is bounded. On the other hand, if <math>a_{n+1}a_n(a_{n+1}-a_n) = 0 </math> always holds, then either <math>a_{n+1} = a_n </math> and <math> a_{n+2} = 0 </math>, or one of <math>a_{n+1}, a_{n} </math> is equal to zero and <math>a_{n+2} </math> is equal to the other one; hence by induction, all the nonzero terms of the sequence are equal, and <math>a_na_k(a_n-a_k) </math> is always equal to zero. Hence if for some <math>n, k </math>, <math>{} a_na_k(a_n-a_k) \neq 0 </math>, then there exist two distinct positive consecutive terms of sequence, which is then unbounded as proven above. | |
− | + | === Solution 2 === | |
+ | The given recursive condition is equivalent to <math>a_{n+2} = a_{n+1} + a_n</math> if <math>a_{n+1} < a_n</math>, and <math>a_{n+2} = a_{n+1} \pm a_n</math> otherwise. Note that if <math>a_{n+1} > a_n</math>, then <math>a_{n+1} = a_n + a_{n-1}</math>. | ||
− | + | '''Lemma 1: ''' Let <math>m > 0</math> be the minimal element of <math>\{a_n\}</math>. Then <math>m = \text{min}\,(a_0,a_1,a_2)</math>. | |
+ | ''Proof: '' Suppose <math>k \ge 3</math> is the minimal value of <math>k</math> such that <math>m = a_k</math>. Then <math>a_k = a_{k-1} - a_{k-2} \Longrightarrow a_{k-1} > a_{k-2}</math>, so <math>a_{k-1} = a_{k-2} + a_{k-3}</math>, and <math>a_k = a_{k-3}</math>. This contradicts our assumption of minimality. | ||
+ | |||
+ | Let <math>T_n = a_n + a_{n+1} + a_{n+2}</math>; we claim that <math>T_{n+2} > T_n + m</math>, which would imply that <math>T_n</math> is unbounded, in turn implying that <math>a_n</math> is unbounded. | ||
+ | |||
+ | *Suppose <math>a_{n+2} = a_n + a_{n+1}</math>; then <math>a_{n+3} = a_{n+2} - a_{n+1} = a_n</math> or <math>a_{n+3} = a_{n+2} + a_{n+1}</math>. In the former case, <math>a_{n+3} < a_{n+2}</math> so <math>a_{n+4} = a_{n+3} + a_{n+2} = a_n + a_{n+2}</math>, and <math>T_{n+2} = (a_{n+2}) + (a_{n}) + (a_{n} + a_{n+2}) = T_n + 2a_n > T_n + m</math>. In the latter case, <math>T_{n+2} > a_{n+2} + a_{n+3} + m > T_n + a_{n+1} + m</math>. | ||
+ | *Suppose <math>a_{n+1} > a_n</math>, <math>a_{n+2} = a_{n+1} - a_n</math>; then <math>a_{n+3} = a_{n+2} + a_{n+1}</math>, and <math>a_{n+4} \ge a_{n+3} - a_{n+2} = a_{n+1}</math>. Then <math>T_{n+2} = a_{n+4} + a_{n+3} + a_{n+2} \ge (a_{n+1}) + (a_{n+2} + a_{n+1}) + a_{n+2} > T_n + a_{n+2} \ge T_n + m</math>. | ||
+ | |||
+ | Then <math>T_{n+2k} > T_n + mk</math>, so <math>T_{n}</math> is unbounded, as desired. | ||
{{alternate solutions}} | {{alternate solutions}} | ||
− | + | == See also == | |
− | '''Comment by the proposer.''' The following statements are equivalent for a sequence <math> a_0, a_1, \ldots, a_n, \ldots </math> of real numbers satisfying <math> | + | '''Comment by the proposer.''' The following statements are equivalent for a sequence <math> a_0, a_1, \ldots, a_n, \ldots </math> of real numbers satisfying <math>a_n = |a_{n+1} - a_{n+2}| </math> for <math> n \ge 0 </math>: <br> |
i) the sequence is bounded; <br> | i) the sequence is bounded; <br> | ||
− | ii) the function <math> | + | ii) the function <math>f </math> defined by <math>f(n,k) = a_na_k(a_n-a_k) </math>, for <math> n,k \ge 0 </math>, is identically zero; <br> |
iii) the sequence is of the form <math> \ldots, 0,a,a,0,a,a,0,a,a, \ldots </math> with <math> a \ge 0 </math>. | iii) the sequence is of the form <math> \ldots, 0,a,a,0,a,a,0,a,a, \ldots </math> with <math> a \ge 0 </math>. | ||
− | |||
− | |||
− | |||
* [[2004 IMO Shortlist Problems]] | * [[2004 IMO Shortlist Problems]] | ||
Line 56: | Line 68: | ||
* [http://www.artofproblemsolving.com/Forum/viewtopic.php?p=152740#p152740 Discussion on AoPS/MathLinks] | * [http://www.artofproblemsolving.com/Forum/viewtopic.php?p=152740#p152740 Discussion on AoPS/MathLinks] | ||
* [http://www.artofproblemsolving.com/Forum/viewtopic.php?p=198930#198930 Further discussion on AoPS/MathLinks] | * [http://www.artofproblemsolving.com/Forum/viewtopic.php?p=198930#198930 Further discussion on AoPS/MathLinks] | ||
− | |||
[[Category:Olympiad Algebra Problems]] | [[Category:Olympiad Algebra Problems]] |
Latest revision as of 15:51, 28 November 2008
Problem
(Mihai Bălună, Romania) An infinite sequence of real numbers satisfies the condition
for every ,
with and positive and distinct. Can this sequence be bounded?
This was also Problem 4 of the 2005 German Pre-TST and Problem 1 of the first 2005 black MOP test. It was Problem 3, Day 2 of the 2005 Romanian TST in the following form:
A sequence of real numbers is called a bs sequence if , for all . Prove that a bs sequence is bounded if and only if the function given by , for all is the null function.
Solution
Solution 1
We note that each of the must be nonnegative.
Lemma 1. If the two initial terms of the sequence are nonzero and distinct, then every term of the sequence is nonzero and no two consecutive terms are equal.
Proof. We proceed by induction; we are given a base case. If , then , so . Furthermore, since , .
Consider a sequence of positive reals which obeys the recursive relation
Lemma 2. .
Proof. We note that if , then and . Thus if , we must have , a contradiction.
Lemma 3. Let , . Then .
Proof. For , easy induction yields , , .
Now, if is even, we have , which is less than by the definition of , and , , . Since and add to , one of them must be at most , and the lemma follows.
On the other hand, if is odd, then set and we have , , and , so as before, at least one of , must be at most . In fact, we have , so the minimum of is at most , upholding the lemma, since in this case .
Now, suppose that is bounded, i.e., there exists some real greater than each . By setting equal to , we generate the first of the in reverse, and from Lemma 2, we can see that is a lower bound of the . But by making greater than , by applying Lemma 3, we obtain the result , which is a contradiction when are distinct and greater than 0, by Lemma 1.
Now, if for all natural , all the nonzero must be equal and the sequence is bounded. On the other hand, if always holds, then either and , or one of is equal to zero and is equal to the other one; hence by induction, all the nonzero terms of the sequence are equal, and is always equal to zero. Hence if for some , , then there exist two distinct positive consecutive terms of sequence, which is then unbounded as proven above.
Solution 2
The given recursive condition is equivalent to if , and otherwise. Note that if , then .
Lemma 1: Let be the minimal element of . Then .
Proof: Suppose is the minimal value of such that . Then , so , and . This contradicts our assumption of minimality.
Let ; we claim that , which would imply that is unbounded, in turn implying that is unbounded.
- Suppose ; then or . In the former case, so , and . In the latter case, .
- Suppose , ; then , and . Then .
Then , so is unbounded, as desired.
Alternate solutions are always welcome. If you have a different, elegant solution to this problem, please add it to this page.
See also
Comment by the proposer. The following statements are equivalent for a sequence of real numbers satisfying for :
i) the sequence is bounded;
ii) the function defined by , for , is identically zero;
iii) the sequence is of the form with .