Difference between revisions of "2014 IMO Problems/Problem 1"
(→Alternative Solution) |
(→Alternative Solution) |
||
(5 intermediate revisions by the same user not shown) | |||
Line 19: | Line 19: | ||
==Alternative Solution== | ==Alternative Solution== | ||
− | It is | + | 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> | <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> | ||
<cmath> 0< V_n-nd_{n+1}\le (n+1)d_{n+2}</cmath> | <cmath> 0< V_n-nd_{n+1}\le (n+1)d_{n+2}</cmath> | ||
− | The condition <math>V_n | + | 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) | --[[User:alexander_skabelin|alexander_skabelin]] 9:24, 7 July 2023 (EST) |
Latest revision as of 10:16, 8 July 2023
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)
Alternative Solution
It is more convenient to work with differences , . . Instead of using the inequalities can be rewritten in terms of as where . is strictly monotonically decreasing. . That is the left inequality is satisfied for . Lets take a look at the time step which is right after : The condition for breaking the left inequality at some step is exactly the condition for satisfying the right inequality at step . Once left inequality is broken at step it will remain broken for future steps as is strictly decreasing. The right inequality will be satisfied for some as is strictly decreasing integer sequence and the right hand side of the right inequality is bounded by from below. In summary, the left inequality is satisfied initially and as soon as the right inequality is satisfied, which will happen for some , the left inequality will break at the very next step and will remain broken for all future steps. That is 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 |