Difference between revisions of "2014 IMO Problems/Problem 1"
m (Created page with "==Problem== Let <math>a__0<a_1<a_2<\cdots \quad </math> be an infinite sequence of positive integers, Prove that there exists a unique integer <math>n\ge1</math> such that <cmat...") |
(→Solution) |
||
(3 intermediate revisions by 2 users not shown) | |||
Line 1: | Line 1: | ||
==Problem== | ==Problem== | ||
− | Let <math> | + | Let <math>a_0<a_1<a_2<\cdots \quad </math> be an infinite sequence of positive integers, Prove that there exists a unique integer <math>n\ge1</math> such that |
<cmath>a_n<\frac{a_0+a_1+\cdots + a_n}{n}\le a_{n+1}.</cmath> | <cmath>a_n<\frac{a_0+a_1+\cdots + a_n}{n}\le a_{n+1}.</cmath> | ||
+ | |||
+ | ==Solution== | ||
+ | Define <math>f(n) = a_0 + a_1 + \dots + a_n - n a_{n+1}</math>. (In particular, <math>f(0) = a_0.</math>) Notice that because <math>a_{n+2} \ge a_{n+1}</math>, we have | ||
+ | <cmath>a_0 + a_1 + \dots + a_n - n a_{n+1} > a_0 + a_1 + \dots + a_n + a_{n+1} - (n+1) a_{n+2}.</cmath> | ||
+ | Thus, <math>f(n) > f(n+1)</math>; i.e., <math>f</math> is monotonic decreasing. Therefore, because <math>f(0) > 0</math>, there exists a unique <math>N</math> such that <math>f(N-1) > 0 \ge f(N)</math>. In other words, | ||
+ | <cmath>a_0 + a_1 + \dots + a_{N-1} - (N-1) a_N > 0</cmath> | ||
+ | <cmath>a_0 + a_1 + \dots + a_N - n a_{N+1} \le 0.</cmath> | ||
+ | This rearranges to give | ||
+ | <cmath>a_N < \frac{a_0 + a_1 + \dots + a_N}{N} \le a_{N+1}.</cmath> | ||
+ | Define <math>g(n) = a_0 + a_1 + \dots + a_n - n a_n</math>. Then because <math>a_{n+1} > a_n</math>, we have | ||
+ | <cmath>a_0 + a_1 + \dots + a_n - n a_n > a_0 + a_1 + \dots + a_n + a_{n+1} - (n+1) a_{n+1}.</cmath> | ||
+ | Therefore, <math>g</math> is also monotonic decreasing. Note that <math>g(N+1) = a_0 + a_1 + \dots + a_{N+1} - (N+1) a_{N+1} \le 0</math> from our inequality, and so <math>g(k) \le 0</math> for all <math>k > N</math>. Thus, the given inequality, which requires that <math>g(n) > 0</math>, cannot be satisfied for <math>n > N</math>, and so <math>N</math> is the unique solution to this inequality. | ||
+ | |||
+ | --[[User:Suli|Suli]] 22:38, 7 February 2015 (EST) | ||
+ | |||
+ | {{alternate solutions}} | ||
+ | |||
+ | ==See Also== | ||
+ | |||
+ | {{IMO box|year=2014|before=First Problem|num-a=2}} | ||
+ | |||
+ | [[Category:Olympiad Algebra Problems]] | ||
==Solution== | ==Solution== |
Latest revision as of 22:43, 7 February 2015
Contents
Problem
Let be an infinite sequence of positive integers, Prove that there exists a unique integer such that
Solution
Define . (In particular, ) Notice that because , we have Thus, ; i.e., is monotonic decreasing. Therefore, because , there exists a unique such that . In other words, This rearranges to give Define . Then because , we have Therefore, is also monotonic decreasing. Note that from our inequality, and so for all . Thus, the given inequality, which requires that , cannot be satisfied for , and so is the unique solution to this inequality.
--Suli 22:38, 7 February 2015 (EST)
Alternate solutions are always welcome. If you have a different, elegant solution to this problem, please add it to this page.
See Also
2014 IMO (Problems) • Resources | ||
Preceded by First Problem |
1 • 2 • 3 • 4 • 5 • 6 | Followed by Problem 2 |
All IMO Problems and Solutions |