Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

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...")
 
(→‎Alternative Solution)
 
(16 intermediate revisions by 3 users not shown)
Line 1: Line 1:
 
==Problem==
 
==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  
+
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)
 +
 +
==Alternative Solution==
 +
 +
It is more convenient to work with differences <math>d_i=a_i-a_{i-1}</math>, <math>i\ge 1</math>. <math>d_i\ge 1</math>. Instead of using <math>a_i=a_0+d_1+\ldots+d_i</math> the inequalities can be rewritten in terms of <math>d_i</math> as
 +
<cmath> 0 < V_n \le nd_{n+1}</cmath>
 +
where <math>V_n=a_0-d_2-2d_3-3d_4-\ldots - (n-1)d_n</math>. <math>V_n</math> is strictly monotonically decreasing. <math>V_1=a_0 >0</math>. That is the left inequality is satisfied for <math>n=1</math>. Lets take a look at the time step <math>(n+1)</math> which is right after <math>n</math>:  <math>n \rightarrow n+1</math>
 +
<cmath> 0< V_n-nd_{n+1}\le  (n+1)d_{n+2}</cmath>
 +
The condition <math>V_n \le nd_{n+1} </math>for breaking the left inequality at some step <math>n+1</math> is exactly the condition for satisfying the right inequality at step <math>n</math>. Once left inequality is broken at step <math>(n+1)</math> it will remain broken for future steps as <math>V_n</math> is strictly decreasing. The right inequality will be satisfied for some <math>n</math> as <math>V_n</math> is strictly decreasing integer sequence and the right hand side <math>nd_{n+1}</math> of the right inequality is bounded by <math>1</math> from below. In summary, the left inequality is satisfied initially and as soon as the right inequality is satisfied, which will happen for some <math>n</math>, the left inequality will break at the very next step and will remain broken for all future steps. That is <math>n</math> when both inequalities are satisfied exists and unique.
 +
 +
--[[User:alexander_skabelin|alexander_skabelin]] 9:24, 7 July 2023 (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 10:16, 8 July 2023

Problem

Let $a_0<a_1<a_2<\cdots \quad$ be an infinite sequence of positive integers, Prove that there exists a unique integer $n\ge1$ such that \[a_n<\frac{a_0+a_1+\cdots + a_n}{n}\le a_{n+1}.\]

Solution

Define $f(n) = a_0 + a_1 + \dots + a_n - n a_{n+1}$. (In particular, $f(0) = a_0.$) Notice that because $a_{n+2} \ge a_{n+1}$, we have \[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}.\] Thus, $f(n) > f(n+1)$; i.e., $f$ is monotonic decreasing. Therefore, because $f(0) > 0$, there exists a unique $N$ such that $f(N-1) > 0 \ge f(N)$. In other words, \[a_0 + a_1 + \dots + a_{N-1} - (N-1) a_N > 0\] \[a_0 + a_1 + \dots + a_N - n a_{N+1} \le 0.\] This rearranges to give \[a_N < \frac{a_0 + a_1 + \dots + a_N}{N} \le a_{N+1}.\] Define $g(n) = a_0 + a_1 + \dots + a_n - n a_n$. Then because $a_{n+1} > a_n$, we have \[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}.\] Therefore, $g$ is also monotonic decreasing. Note that $g(N+1) = a_0 + a_1 + \dots + a_{N+1} - (N+1) a_{N+1} \le 0$ from our inequality, and so $g(k) \le 0$ for all $k > N$. Thus, the given inequality, which requires that $g(n) > 0$, cannot be satisfied for $n > N$, and so $N$ is the unique solution to this inequality.

--Suli 22:38, 7 February 2015 (EST)

Alternative Solution

It is more convenient to work with differences $d_i=a_i-a_{i-1}$, $i\ge 1$. $d_i\ge 1$. Instead of using $a_i=a_0+d_1+\ldots+d_i$ the inequalities can be rewritten in terms of $d_i$ as \[0 < V_n \le nd_{n+1}\] where $V_n=a_0-d_2-2d_3-3d_4-\ldots - (n-1)d_n$. $V_n$ is strictly monotonically decreasing. $V_1=a_0 >0$. That is the left inequality is satisfied for $n=1$. Lets take a look at the time step $(n+1)$ which is right after $n$: $n \rightarrow n+1$ \[0< V_n-nd_{n+1}\le (n+1)d_{n+2}\] The condition $V_n \le nd_{n+1}$for breaking the left inequality at some step $n+1$ is exactly the condition for satisfying the right inequality at step $n$. Once left inequality is broken at step $(n+1)$ it will remain broken for future steps as $V_n$ is strictly decreasing. The right inequality will be satisfied for some $n$ as $V_n$ is strictly decreasing integer sequence and the right hand side $nd_{n+1}$ of the right inequality is bounded by $1$ from below. In summary, the left inequality is satisfied initially and as soon as the right inequality is satisfied, which will happen for some $n$, the left inequality will break at the very next step and will remain broken for all future steps. That is $n$ when both inequalities are satisfied exists and unique.

--alexander_skabelin 9:24, 7 July 2023 (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

Solution

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2014_IMO_Problems/Problem_1&oldid=195418"