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"

(→‎Alternative Solution)
(→‎Alternative Solution)
Line 19: Line 19:
 
==Alternative Solution==
 
==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</math> the inequalities can be rewritten in terms of <math>d_i</math> as  
+
It is somewhat 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</math> the inequalities can be rewritten in terms of <math>d_i</math> as  
 
<cmath> 0 < V_n \le nd_{n+1}</cmath>  
 
<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>
 
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>

Revision as of 09:49, 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 somewhat 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$ 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<nd_{n+1}$for breaking the left inequality at some step $n+1$ is exactly the condition for satisfying 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 at some point 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. That is the left inequality is satisfied initially and as soon as the right inequality is satisfied, which will happen at some point, the left inequality will break at the 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=195410"