IMO 2014 Problem 1

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

5452 posts

#1 h Jul 8, 2014, 12:17 PM • 36 Y

Y by gobathegreat, test20, Kunihiko_Chikaya, wiseman, quangminhltv99, Davi-8191, Tawan, SRKTK, Wizard_32, myh2910, donotoven, megarnie, math31415926535, son7, ImSh95, mathmax12, Stuart111, Anulick, Lamboreghini, Adventure10, Mango247, ProMaskedVictor, Aopamy, D_S, ItsBesi, cubres, and 10 other users

Let $a_0 < a_1 < a_2 < \dots$ be an infinite sequence of positive integers. Prove that there exists a unique integer $n\geq 1$ such that
$a_n < \frac{a_0+a_1+a_2+\cdots+a_n}{n} \leq a_{n+1}.$
Proposed by Gerhard Wöginger, Austria.

This post has been edited 1 time. Last edited by v_Enhance, Nov 5, 2023, 5:17 PM
Reason: missing < sign

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

manuel153

324 posts

manuel153

#2 h Jul 8, 2014, 12:20 PM • 12 Y

Y by Amir Hossein, TheMathLife, son7, ImSh95, Lamboreghini, Adventure10, Mango247, cubres, and 4 other users

There should be some fixed point theorem in the background...
And perhaps some contraction?

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Fedor Petrov

520 posts

Fedor Petrov

#3 h Jul 8, 2014, 12:24 PM • 141 Y

Y by Amir Hossein, manuel153, capttawish, chaotic_iak, alibez, Ygg, shaiephraim, CatalinBordea, test20, numbertheorist17, Mathematicalx, mgalushka, jakab922, lfetahu, professordad, MexicOMM, randomasdf97, Niosha, biomathematics, ssk9208, ZacPower123, cohesive-aggregate, mihaith, B101099, Popescu, v_Enhance, quangminhltv99, Kezer, anantmudgal09, TheDarkPrince, Tommy2000, A_Math_Lover, Swag00, xilias, hwl0304, jt314, JasperL, rocketscience, propali_mat, Tawan, tarzanjunior, InCtrl, futurestar, Wizard_32, Anar24, ThisIsASentence, sunfishho, samoha, Pluto1708, Arhaan, Kayak, richrow12, MelonGirl, TheMathLife, AlastorMoody, alijahan, mathleticguyyy, Reef334, Kanep, leilei80, TwilightZone, Illuzion, hellomath010118, Aryan-23, green_leaf, Limerent, OlympusHero, Pitagar, aops29, xymking, MathBoy23, kevinmathz, 554183, math31415926535, samrocksnature, hsiangshen, megarnie, Siddharth03, mo.s.k14142, ZHEKSHEN, asdf334, Tafi_ak, L567, myh2910, Wizard0001, ali3985, son7, chystudent1-_-, Aimingformygoal, ImSh95, Quidditch, 407420, hieuan682, skyguy88, Elyson, trying_to_solve_br, PERA2008, GeoMetrix, Danielzh, ihatemath123, melowmolly, Mogmog8, EpicBird08, Schur-Schwartz, OronSH, Lamboreghini, zhenghua, Adventure10, golue3120, khina, Mango247, bobthegod78, Aopamy, Stuffybear, DroneChaudhary, Deadline, vrondoS, sabkx, Springles, Sedro, Math_legendno12, Wild, akliu, aidan0626, alexanderhamilton124, NicoN9, ESAOPS, Scilyse, cubres, jason02, Funcshun840, MS_asdfgzxcvb, and 9 other users

Denote $b_n=(a_n-a_{n-1})+\dots+(a_n-a_1)$ . Then $b_1=0$ , $b_n$ increases and we are searching for $n$ such that $b_n<a_0\leq b_{n+1}$ . It clearly exists and is unique.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

mavropnevma

15142 posts

mavropnevma

#4 h Jul 8, 2014, 1:02 PM • 23 Y

Y by FlakeLCR, anantmudgal09, azmath333, DrMath, Tawan, HamstPan38825, son7, ImSh95, khina, Lamboreghini, Amir Hossein, Adventure10, Mango247, cubres, MS_asdfgzxcvb, and 8 other users

Of course, the fact the sequence $(a_n)_{n\geq 1}$ has integer terms is irrelevant; all that matters is that the sequence $(b_n)_{n\geq 1}$ is unbounded.

Notice that in fact the precise condition for the thesis to hold true is that for the sequence $(\delta_n)_{n\geq 1}$ , given by $\displaystyle \delta_n = a_{n+1}-a_n > 0$ for all $n\geq 1$ ,
to have $\displaystyle \sum_{k=1}^{\infty} k\delta_k > a_0$ ; then there will exist $m\geq 1$ so that $\displaystyle b_{m+1} = \sum_{k=1}^{m} k\delta_k > a_0$ .
If the sequence $(\delta_n)_{n\geq 1}$ is so that $\displaystyle \sum_{k=1}^{\infty} k\delta_k \leq a_0$ , then $\displaystyle b_{m+1} = \sum_{k=1}^{m} k\delta_k < a_0$ and the thesis holds no more; such exemple is $\delta_n = \dfrac {a_0}{n 2^n}$ .

This post has been edited 2 times. Last edited by mavropnevma, Jul 8, 2014, 2:21 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

ngv

251 posts

ngv

#5 h Jul 8, 2014, 1:24 PM • 16 Y

Y by Amir Hossein, rkm0959, Tawan, son7, ImSh95, Lamboreghini, Adventure10, cubres, and 8 other users

Amir Hossein wrote:

Let $a_0 < a_1 < a_2 \ldots$ be an infinite sequence of positive integers. Prove that there exists a unique integer $n\geq 1$ such that
$a_n < \frac{a_0+a_1+a_2+\cdots+a_n}{n} \leq a_{n+1}.$

Key Lemma:
If $S_i=S_{i-1}+u_i$ is a cumulative sequence with $S_0=0$ and $u_i>0$ for all $i$ , then for every positive integer $k$ , there is a unique positive integer $n$ so that, $S_n < k\leq S_{n+1}$ .
Proof:
Almost obvious. But if you still need one, take $n$ to be the smallest positive integer so that $S_{n+1}\geq k$ . Then, we must have $S_{n}<k$ . If not, it would contradict the minimality of $n$ .
Now, all we have to do is find an appropriate $\{u\}$ and $\{S\}$ . Take, $S_n=\sum_{i=1}^na_i$ , which is clearly increasing. We need, $S_n+a_0>na_n$ and $S_{n}+a_0\leq na_{n+1}$ . Clearly this want us to consider the sequence $T_n=na_{n+1}-S_{n}$ . It can be written as $T_n=\sum_{i=1}^nc_i=T_{i-1}+c_i$ where $c_i=a_{n+1}-a_i$ . Obviously, $c_i>0$ for all $i$ . Thus, $\{T\}$ is a cumulative sequence, and therefore, such a $n$ always exists no matter what the choice of $a_0$ is as long as it is a positive integer.

Remark: Something similar can not be said if it is replaced by non-negative integers. Because then the sequence $\{S\}$ would not be strictly increasing. Also, the crucial idea seems kind of trivial to me if someone has ever done "Binary Search" or something like that in an algorithm course/in CSE, whatever.

This post has been edited 1 time. Last edited by ngv, Jul 8, 2014, 1:28 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Davi Medeiros

118 posts

Davi Medeiros

#6 h Jul 8, 2014, 1:27 PM • 27 Y

Y by Amir Hossein, CatalinBordea, Torus121, DominicanAOPSer, randomasdf97, InCtrl, Tawan, A_Math_Lover, Lukaluce, Illuzion, megarnie, son7, ImSh95, mathmax12, naonaoaz, Danielzh, Lamboreghini, ihatemath123, Adventure10, cubres, and 7 other users

The old $\Delta$ trick, again!

Let $a_n = a_0 + \Delta_1 + \Delta_2 + ... + \Delta_n$ for each $n \ge 1$ . Notice that $\Delta_n \ge 1$

Now, the condition $a_n < \frac{a_0 + ... +a_n}{n} \le a_{n+1}$ can be rewritten as:

$a_0 + \Delta_1 + \Delta_2 + ... + \Delta_n < \frac{(n+1)a_0 + n\Delta_1 +(n-1)\Delta_2+ ... + \Delta_n}{n} \le$
$\le a_0+\Delta_1 + ... +\Delta_n + \Delta_{n+1}$

After a little calculation, one can have that $\Delta_2 +2\Delta_3 +...+(n-1)\Delta_n < a_0 \le \Delta_2 +2\Delta_3 +...+(n-1)\Delta_n +n\Delta_{n+1}$

Now, defining $f: \mathbb{N} \rightarrow \mathbb{Z}$ by $f(1) = 0$ and $f(n)=\Delta_2 + 2\Delta_3 +.. +(n-1)\Delta_n$ , for all $n \ge 2$ , we see that $f$ is increasing and unbounded ( $f(n+1)-f(n)=n\Delta_{n+1} \ge n$ ).

Now, it remains to prove that exists a unique $n\in \mathbb{N}$ such that $f(n)<a_0<f(n+1)$ This is clear, since $f(1)=0<a_0$ and $f$ is estrictely increasing and unbounded. Problem Solved!

This post has been edited 2 times. Last edited by Davi Medeiros, Jul 8, 2014, 1:51 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

andreiromania

52 posts

andreiromania

#7 h Jul 8, 2014, 1:32 PM • 17 Y

Y by Amir Hossein, InCtrl, Tawan, A_Math_Lover, megarnie, son7, ImSh95, Lamboreghini, Adventure10, sabkx, cubres, and 6 other users

Fedor Petrov wrote:

Denote $b_n=(a_n-a_{n-1})+\dots+(a_n-a_1)$ . Then $b_1=0$ , $b_n$ increases and we are searching for $n$ such that $b_n<a_0\leq b_{n+1}$ . It clearly exists and is unique.

Very ingenuous approach.However not all students may find such an idea so I decided to give a few ideas that one can find from trial and error in order to build a solution.
I will refer to $a_n <\frac{a_0+a_1+a_2+\cdots+a_n}{n}$ as "the LHS for n" and to $\frac{a_0+a_1+a_2+\cdots+a_n}{n}\leq a_{n+1}$ as "the RHS for n".

1)First,we prove that at most one n can satisfy the given inequality.If we suppose there are more than 1 n's,we choose the minimal one,and find out that the RHS for n turns into the opposite of the LHS for n+1,which by induction turns into the opposite of the LHS for every m>n.
2)Then,we prove that,given a particular n,one cannot have the opposite of the RHS for n,and then the opposite for the LHS for n+1.
3)This being proven,we then assume that for n=1 we have the opposite of the RHS(the LHS being obviously true,if the RHS were to be true too we would have found our n).If there would be an n for which the opposite for the LHS for n would be true,then there would have been an m<n for which both the LHS for m AND the RHS for m would be true,otherwise there would be an m for which the opposite of the RHS for m is true and then the opposite of the LHS for m+1 is true,which contradicts 2).
4)From 3) we conjecture that if there would not exist an n for which both the LHS and the RHS are true,the RHS must be false for all n,however with a bit of manipulation this turns into $a_0+a_1>a_n$ for all n,which is obviously false.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Matija

53 posts

Matija

#8 h Jul 8, 2014, 1:46 PM • 14 Y

Y by Amir Hossein, Tawan, A_Math_Lover, son7, ImSh95, Adventure10, Mango247, cubres, and 6 other users

The same idea written differently. Let $S_n$ be the statement $a_n <\frac{a_0+a_1+a_2+\cdots+a_{n-1}}{n-1}$ for $n\geq 2$ . Then the statement of the problem is equivalent to existence of a unique $n$ such that $S_n$ and not $S_{n+1}$ .

$S_1$ should be phrased as $0<a_0$ which obviously holds. $S_2, ..., S_n$ imply together that $a_n < a_0+a_1$ , so there must be $n$ for which $S_{n+1}$ does not hold. But if $S_m$ does not hold, then $S_{m+1}$ also does not hold, so there can be only one integer with the sought property.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

colinhy

751 posts

colinhy

#9 h Jul 8, 2014, 2:04 PM • 24 Y

Y by Ygg, Amir Hossein, Stefan4024, DominicanAOPSer, Kezer, Tawan, strategos21, megarnie, JG666, son7, ImSh95, hellnish, Adventure10, ike.chen, cubres, and 9 other users

Hmm another pretty similar proof, just worded differently:

Proof

Rather straightforward, even for a #1.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

gavrilos

233 posts

gavrilos

#10 h Jul 8, 2014, 2:23 PM • 12 Y

Y by Amir Hossein, Tawan, son7, ImSh95, Adventure10, Mango247, cubres, and 5 other users

If colinhy's proof is correct,mine is correct too (it's the same).A rather easy problem I have to say.In my opinion easier than last year's one.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

dibyo_99

487 posts

dibyo_99

#11 h Jul 8, 2014, 2:37 PM • 14 Y

Y by Tawan, Amir Hossein, son7, ImSh95, Adventure10, Mango247, cubres, and 7 other users

We are required to show the existence of a unique intger $n \ge 1$ such that $na_n < \sum_{i=0}^n a_i \le na_{n+1} \Longleftrightarrow \sum_{i=1}^{n-1} (a_n - a_i) < a_0 \le \sum_{i=1}^n (a_{n+1}-a_i)$ Note that the sequence $\left( \sum_{i=1}^{n-1} (a_n - a_i) \right)_n$ is strictly increasing (since $a_n$ is strictly increasing, each of the differences also increase), has the first term $0$ and is also obviously unbounded. Therefore, there must exist some term of the sequence strictly smaller than $a_0$ such that the next term is greater (weakly) than $a_0$ .

This post has been edited 1 time. Last edited by dibyo_99, Jul 8, 2014, 2:38 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

tchebytchev

584 posts

tchebytchev

#12 h Jul 8, 2014, 2:37 PM • 15 Y

Y by Tawan, Amir Hossein, Rustem-E303, son7, ImSh95, rstenetbg, Adventure10, Mango247, cubres, and 6 other users

Suppose that for every $n$ we have $a_{n+1} < \frac{a_0+...+a_n}{n}$
for $n=1$ , $a_2 < a_0+a_1$ . For $n=2$ , $2a_3 <a_0+a_1+a_2<2(a_0+a_1)$ so $a_3<a_0+a_1$ and by induction $a_n<a_0+a_1$ which it is a contradiction because we have an infinite sequence of positive integer and bounded !

Let $n_0$ be an integer such that $a_{n_0+1} \geq \frac{a_0+...+a_{n_0}}{n_0}$
we have $a_1<a_0+a_1$ if $a_0+a_1 \leq a_2$ we get the existence, if not then $a_2 <\frac{a_0+a_1+a_2}{2}$ and again if $\frac{a_0+a_1+a_2}{2} \leq a_3$ we have done and if not we have $a_3 <\frac{a_0+a_1+a_2+a_3}{3}$ and we continue until reaching the integer $n_0$ for which we have
$a_{n_0} < \frac{a_0+...+a_{n_0}}{n_0} \leq a_{n_0+1}$

The uniqueness is obvious because if $\frac{a_0+...+a_n}{n} \leq a_{n+1}$ then $\frac{a_0+...+a_n+a_{n+1}}{n+1} \leq a_{n+1}$ and since the sequence is strictly increasing we show easily that for any $m>n+1$ we have $\frac{a_0+...+a_m}{m} < a_m$ so the property can't be satisfied for $m> n_0$

This post has been edited 1 time. Last edited by tchebytchev, Jul 8, 2014, 4:58 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Matematika

139 posts

Matematika

#13 h Jul 8, 2014, 3:57 PM • 14 Y

Y by Tawan, Amir Hossein, son7, ImSh95, Lamboreghini, Adventure10, Mango247, cubres, and 6 other users

As the problem is already solved in quite a few ways I would like to comment on the possible generalizations.

First question is necessity of the weird integer condition.

The answer if I am not mistaken is that we can't remove it altogether as if we choose:

$a_0=\frac{\pi^2}{6}$

and $a_{n+1}=a_n+\frac{1}{(n+1)^3}$ for $n\geq 0$ should provide a counterexample for the problem without the "integer" condition.

Of course the uniqueness proof as shown above works regardless but the problem breaks at existence condition.

If we denote by $b_n=a_{n+1}-a_n$ as someone already did above if $a_0>nb_n+\cdots +2b_2+b_1$ there is no $n$ as described in the problem.

About the problem.
I believe it is a good problem for problem 1 which should really be as easy as possible while still requiring some thought. I personally dislike it due to a weird imposing of integer numbers on an obviously algebraic problem.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

AnonymousBunny

339 posts

AnonymousBunny

#14 h Jul 8, 2014, 4:00 PM • 15 Y

Y by Tawan, Amir Hossein, son7, ImSh95, Adventure10, Mango247, cubres, and 8 other users

We rewrite the condition as
$na_n < \displaystyle \sum_{i=0}^{n} a_i < na_{n+1} \implies \begin{cases} \displaystyle \sum_{i=1}^{n} (a_n - a_i) < a_0 \\ \sum_{i=1}^{n+1} (a_{n+1} - a_i) \geq a_0 \end{cases}.$
Note that for all $n,$
$\left( \displaystyle \sum_{i=1}^{n+1} (a_{n+1} - a_i) \right) - \left( \displaystyle \sum_{i=1}^{n} (a_n - a_i) \right) = n a_{n+1} - na_n > 0,$
which implies $\displaystyle \sum_{i=1}^{n} \left( a_n - a_i \right)$ is monotonically increasing. Obviously $\displaystyle \sum_{i=1}^{n} (a_n-a_i)$ is unbounded from above. At $n=1,$ it equals zero. Now let $n$ be the largest integer such that $\displaystyle \sum_{i=1}^{n} \left( a_n - a_i \right) <a_0.$ We have that $a_{n+1} \geq a_0$ by our hypothesis, so this is our desired $n$ which is clearly unique. $\blacksquare$

This post has been edited 2 times. Last edited by AnonymousBunny, Jul 8, 2014, 5:04 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

MathD

204 posts

MathD

#15 h Jul 8, 2014, 4:46 PM • 14 Y

Y by tim9099xxzz, Tawan, Amir Hossein, son7, ImSh95, Adventure10, Mango247, cubres, and 6 other users

Would someone be so kind and check my proof?

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

abeot

123 posts

abeot

#127 h Nov 5, 2023, 9:01 PM • 2 Y

Y by centslordm, cubres

Let $b_0 = a_0$ , and $b_i = a_i - a_{i-1}$ for $i \geq 1$ . Then it suffices to show that
$b_0 + b_1 + \dots + b_n < \frac{(n+1)b_0 + nb_1 + (n-1)b_2 + \dots + b_n}{n} \leq b_{n+1} + b_n + \dots + b_1 + b_0$ Or, multiplying by $n$ and subtracting, that
$-b_0 + 0b_1 + b_2 + 2b_3 + \dots + (n-1)b_n < 0 \leq -b_0 + 0b_1 + b_2 + 2b_3 + \dots + (n-1)b_n + nb_{n+1}$
But consider the sequence with $c_0 = -b_0$ and $c_i = c_{i-1} + (i-1)b_i$ for $i \geq 1$ . Clearly, it starts out negative, but we have $c_i > c_{i-1}$ for $i \geq 2$ . Thus, 0 must lie in a range $(c_i, c_{i+1}]$ . $\blacksquare$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

spectator01

58 posts

spectator01

#128 h Nov 24, 2023, 8:32 AM • 1 Y

Y by cubres

Let $b_{n} = a_{0}+a_{1}+\cdots+a_{n-1}-(n-1)a_{n}$ . Note that $b_{i}$ is strictly decreasing. Because it is strictly decreasing and it starts positive, there exists $n$ such that $b_{n} > 0$ and then $b_{n+1}\leq 0$ . Note this is unique because it is strictly decreasing.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Shreyasharma

666 posts

Shreyasharma

#129 h Dec 11, 2023, 12:11 AM • 1 Y

Y by cubres

Assume the contrary. Then for any $n$ we always either have,

$na_n \geq a_0+a_1+a_2+\cdots+a_n$
$a_0+a_1+a_2+\cdots+a_n > na_{n+1}$

It is easy to see however the first bullet can never hold due to the strictly increasing condition so we must always have the second bullet. Thus we find the following inequality chain:
$\begin{align*} a_0 + a_1 &> a_2\\ a_0 + a_1 + a_2 &> 2a_3\\ a_0 + a_1 + a_2 + a_3 &> 3a_4\\ &\vdots \end{align*}$ Note that the second bullet implies $a_0 + a_1 > a_3$ , the third implies $a_0 + a_1 > a_4$ and so on. Thus we find that we must always have,
$\begin{align*} n(a_0 + a_1) > a_0 + a_1 + \dots + a_n \end{align*}$ Then substituting this into the first bullet we find we always have,
$\begin{align*} a_0 + a_1 > a_{n+1} \end{align*}$ for all $n$ , which is clearly false.

Uniqueness simply follows from an inductive argument.

This post has been edited 2 times. Last edited by Shreyasharma, Dec 11, 2023, 12:13 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

eibc

595 posts

eibc

#130 h Dec 14, 2023, 2:57 AM • 1 Y

Y by cubres

For positive integers $n$ , let $b_n = a_0 + a_1 + \cdots + a_{n - 1} - (n - 1)a_n$ . Then we wish to show there exists a unique $n$ for which $b_n > 0$ and $b_{n + 1} \le 0$ . But $b_{n + 1} = b_n + na_n - na_{n + 1}$ , so the sequence $(b_i)_{i \ge 1}$ is strictly decreasing. Since it only takes on integer values, there is evidently only one $n$ satisfying this condition.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

legogubbe

18 posts

legogubbe

#131 h Dec 15, 2023, 10:21 PM • 1 Y

Y by cubres

Define the sequence $b_{0},b_{1},b_{2}, \ldots$ by
$b_{k}=-ka_{k+1}+\sum_{i=0}^{k} a_{i}, \quad \text{for every $k \geq 0$.}$ Then
$b_{k+1}-b_{k} = -(k+1)a_{k+2} + \sum_{i=0}^{k+1} a_{i} +ka_{k+1} - \sum_{i=0}^{k} a_{i} = (k+1)(a_{k}-a_{k+1})<0.$ Since $b_{k}$ is an integer for every $k$ (for obvious reasons) we find $b_{0},b_{1},b_{2}, \ldots$ to be a strictly decreasing sequence of integers. Hence, with $b_{0}=a_{0}>0$ , there must exist exactly one $n \geq 1$ for which $b_{n-1}>0$ and $b_{n} \leq 0$ . These two inequalities are equivalent to
$a_{n} < \frac{a_{1}+a_{2} + \ldots + a_{n}}{n},$ and
$a_{n+1} \geq \frac{a_{1}+a_{2} + \ldots + a_{n}}{n},$ respectively. $\blacksquare$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

smileapple

1009 posts

smileapple

#132 h Jan 2, 2024, 7:58 AM • 1 Y

Y by cubres

trivial.

For each nonnegative integer $n$ , define
$\begin{align*} b_n&=(n-1)a_n-a_0-a_1-\cdots-a_{n-1}\\ &=(a_n-a_1)+(a_n-a_2)+\cdots+(a_n-a_{n-1})-a_0. \end{align*}$ Since the $a_i$ form a strictly increasing sequence, we have for all nonnegative integers $n$ that
$\begin{align*} b_{n+1}&=(a_{n+1}-a_1)+(a_{n+1}-a_2)+\cdots+(a_{n+1}-a_n)-a_0\\ &>(a_n-a_1)+(a_n-a_2)+\cdots+(a_n-a_n)-a_0\\ &=(a_n-a_1)+(a_n-a_2)+\cdots+(a_n-a_{n-1})-a_0\\ &=b_n. \end{align*}$ As the $a_i$ are all integers, it thus follows that the $b_i$ form another strictly increasing sequence of integers.

We note that $b_0=b_1=-a_0<0$ , so by monotonicity there must exist some unique positive integer $n$ such that $b_n<0\le b_{n+1}$ . In particular, having $b_n<0$ is equivalent to having $(n-1)a_n<a_0+a_1+\cdots+a_{n-1}$ and thus $a_n<\frac{a_0+a_1+\cdots+a_n}n,$ while having $b_{n+1}\ge 0$ is equivalent to having $na_{n+1}\ge a_0+a_1+\cdots+a_n$ and thus $\frac{a_0+a_1+\cdots+a_n}n\le a_{n+1}.$ Hence this value of $n$ works and is unique, as desired. $\blacksquare$

- Jörg

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

trk08

614 posts

trk08

#133 h Jan 9, 2024, 3:42 AM • 1 Y

Y by cubres

Denote:
$b_n=a_0+a_1+\dots+a_n,$ $c_n=a_n(n-1).$ We can develop the recursive formulas:
$\begin{align} b_{n+1}&=b_n+a_n+1\\ c_{n+1}&=c_n+(a_{n+1}-a_n)\cdot n+a_n \end{align}$ We will prove both uniqueness and existence.

Uniqueness:
Assume such an $n$ exists, so:
$b_{n-1}>c_n,$ $b_n\leq c_{n+1}.$ We will proceed with induction (the base case is above).

By our recursive formula for $b_n$ , we can say:
$\begin{align*} b_{n+1}&=b_n+a_n+1\\ &\leq c_{n+1}+a_n+1\\ &=a_{n+1}\cdot n+a_n+1\\ &\leq a_{n+2}\cdot (n+1)\\ &=c_{n+2}.\\ \end{align*}$
Therefore, using induction, we can say that:
$b_i\leq c_{i+1},\text{ }\forall i\geq n,$ implying uniqueness $\square$

Existence:
Using the recursive formulas, we can say:
$c_{n+1}-b_{n+1}=c_n-b_n+(a_{n+1}-a_n)\cdot n-1.$

Note that:
$(a_{n+1}-a_n)\cdot n-1\geq 0,\text{ }\forall n\geq 1,$ $(a_{n+1}-a_n)\cdot n-1> 0,\text{ }\forall n\geq 2.$ Therefore, $c_{n+1}-b_{n+1}$ is strictly increasing when $n\geq 2$ . By IVT, this means that if $\exists$ and $i$ such that $b_i>c_{i+1}$ , $\exists$ a $j>i$ such that $b_j\leq c_{j+1}$ . However, note that:
$b_0=a_0>0=c_1,$ so the existence is proven $\blacksquare$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

pie854

243 posts

pie854

#135 h Jun 6, 2024, 8:40 AM • 1 Y

Y by cubres

Define $s_n:=\frac{a_0+\dots+a_n}n$ .

Claim: There exists $m$ such that $s_m\leq a_{m+1}$ .
Proof. Note that we have $a_k\leq a_{m+1}+k-m-1$ for all $k\leq m+1$ . So, $s_m\leq \frac 1m \left (a_0+\sum_{k=1}^m (a_{m+1}+k-m-1)\right )=\frac 1m \left (a_0-\frac {m(m+1)}2\right)+a_{m+1}\leq a_{m+1}$ where the last step follows taking a sufficiently large $m$ .

Let $n$ be the smallest number such that $s_n\leq a_{n+1}$ . Then we have $s_{n-1}>a_n$ and so $s_n=\frac{(n-1)s_{n-1}+a_n}{n}>\frac{(n-1)a_n+a_n}n=a_n.$ So this $n$ satisfies $a_n<s_n\leq a_{n+1}$ .

Now for the uniqueness part note that $s_k>a_{k+1}$ for all $k<n$ and also $s_{n+1}=\frac{ns_n+a_{n+1}}{n+1}\leq \frac{na_{n+1}+a_{n+1}}{n+1}=a_{n+1}$ from which by induction it follows that $s_k\leq a_k$ for all $k>n$ .

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

ryanbear

1055 posts

ryanbear

#136 h Jun 6, 2024, 3:06 PM • 1 Y

Y by cubres

Let $b_n=a_{n+1}-a_n$
Proof of uniqueness: Assume that $n$ works. Then, $na_n<a_0+a_1+a_2+...+a_n \le na_{n+1}$ .
Increasing $n$ by $1$ would increases the LHS by $nb_n+b_n+b_{n-1}+...+b_1+b_0+a_0$ , the middle by $a_0+b_0+b_1+b_2+...+b_n$ , and the RHS by $nb_{n+1}+b_{n+1}+b_n+...+b_1+b_0+a_0$ .
subtracting $a_0+b_0+...+b_n$ from this gives that the changes are $nb_n$ , $0$ , and $(n+1)b_{n+1}$ .
$na_n<a_0+a_1+a_2+...+a_n \le na_{n+1}$
$na_n+nb_n<a_0+a_1+a_2+...+a_n \le na_{n+1}+(n+1)b_{n+1}$
$na_{n+1}<a_0+a_1+a_2+...+a_n$
This is a contradition, so $n+1$ cannot work.

Proof of existance: Note that when $n=1$ , the values of the sides of the inequailty become $a_1, a_0+a_1, a_2$ .
Subtract by $a_1$ to get $0, a_0, b_1$
Note that increasing $n$ by $1$ increases the left number by $b_n$ and the right number by $b_{n+1}$
So it becomes $b_1, a_0, b_1+b_2$ and then $b_1+b_2, a_0, b_1+b_2+b_3$ and so on
Note that the range between the first and last value covers all positive numbers, so $a_0$ has to be in one of those ranges, so a value of $n$ has to work.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

ezpotd

1245 posts

ezpotd

#137 h Sep 15, 2024, 11:25 PM • 1 Y

Y by cubres

First we note that if $\frac{a_0 + a_1 + a_2 + \cdots a_n}{n} \le a_{n +1}$ , we have $a_0 + a_1 + a_2 + \cdots a_n + a_{n +1}\le (n + 1)a_{n + 1}$ , so $\frac{a_0 + a_1 + \cdots a_{n + 1}}{n + 1} \le a_{n + 1} < a_{n + 2}$ . Now define $b_n =\frac 1n ( a_0 + a_1 \cdots a_n)$ , we have then just shown that $b_n \le a_{n + 1}$ implies $b_{n + 1} \le a_{n + 2}$ , so if $b_n \le a_{n + 1}$ , we have $b_{n + i} \le a_{n + 1 + i}$ for all nonnegative $i$ . Furthermore, we have also shown that $b_n \le a_{n + 1}$ implies $b_{n + 1} \le a_{n + 1}$ , so we have shown that $b_{n + i} \le a_{n + i}$ for all positive $i$ .

Now we show that there are no more than $1$ integers that satisfy this inequality. Assume for the sake of contradiction that there are two numbers $x < y$ for which this condition holds. Then we have $b_{x} \le a_{x + 1}$ , but this implies $b_{x + i} \le a_{x + i}$ for all positive $i$ , setting $i = y - x$ forces a contradiction to the inequality.

Now we show at least one integer satisfies this inequality. Note that $b_{n} > a_{n + 1}$ implies $a_0 + \cdots a_n \le na_{n + 1}$ which implies $a_0 + \cdots a_n > (n + 1)a_{n + 1}$ which implies $b_{n + 1} > a_{n + 1}$ .

If $n = 1$ satisfies the inequality, we are done. Otherwise, we have $a_1 < b_1$ since $a_0 < a_0 + a_1$ , so we must have $b_1 > a_2$ . We can now separate further into two cases.

Case 1: There exists some integer where $b_{n} \le a_{n + 1}$ . Then there must exist a smallest integer $n$ of this type. Then we have $b_{n - 1} > a_{n}$ , so $b_{n} > a_{n}$ and $n$ satisfies the inequality.

Case 2: There exists no such integers. We show that this is in fact impossible. We show $na_{n + 1} - (a_0 + \cdots a_n)$ is monotonically increasing as a function of $n$ , thus at some point it must be positive and we have $b_n \le a_{n + 1}$ . In fact, this is trivial, just consider the marginal difference, $(n + 1)a_2 - (n + 1)a_1$ , which is guaranteed to be positive, so we are done.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Maximilian113

490 posts

Maximilian113

#138 h Dec 4, 2024, 11:04 PM • 1 Y

Y by cubres

We first show that $n$ exists. For the sake of a contradiction, suppose it didn't. Then clearly, we have that $a_1 < \frac{a_0+a_1}{1} \implies a_2 < \frac{a_0+a_1}{1} \implies a_2 < \frac{a_0+a_1+a_2}{2} \implies \cdots \implies a_k < \frac{a_0+a_1+\cdots+a_{k-1}}{k-1} \implies a_k < \frac{a_0+a_1+\cdots+a_k}{k} \implies \cdots.$ Now, we will show by induction that $a_k < a_0+a_1$ for all positive integers $k.$ The base case is trivial, so assume that our proposition holds for all $k \leq r$ for some positive integer $r \geq 1.$ Therefore, $a_{r+1} < \frac{a_0+a_1+a_2+\cdots+a_r}{r} < \frac{r(a_0+a_1)}{r} = a_0+a_1,$ so our induction is complete. However, since $\{a_k\}$ is unbounded this yields a contradiction. $\boxed{}$

Now, it suffices to show that our solution is unique. Suppose that $n$ was the smallest integer that satisfied the bounds. Then we have that $\frac{a_0+a_1+a_2+\cdots+a_n}{n} \leq a_{n+1} \implies \frac{a_0+a_1+a_2+\cdots+a_{n+1}}{n+1} \leq a_{n+1} \leq a_{n+2}$ so inductively we can show that $\frac{a_0+a_1+a_2+\cdots+a_{n+m}}{n+m} \leq a_{n+m}$ for positive integers $m,$ therefore no $k > n$ would satisfy the bounds, meaning that $n$ is the unique solution. QED

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

peppapig_

278 posts

peppapig_

#139 h Jan 13, 2025, 11:02 PM • 1 Y

Y by cubres

Define the sequence $(b_n)$ so that
$b_n=a_0+a_1+\dots+a_{n-1}-(n-1)a_n.$ Our problem is equivalent to proving there exists a unique $n\ge 1$ such that $b_n>0$ and $b_{n+1}\le 0$ . However,
$b_{n+1}-b_n=-n(a_{n+1}-a_n)\le -n.$ Therefore $(b_n)$ is strictly decreasing (and will go below $0$ ). Since $b_1=a_0>0$ , this means there exists an unique $n$ satisfying the conditions, as desired.

This post has been edited 2 times. Last edited by peppapig_, Jan 13, 2025, 11:03 PM
Reason: Flipped signs

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

de-Kirschbaum

184 posts

de-Kirschbaum

#140 h Feb 6, 2025, 5:33 PM • 1 Y

Y by cubres

We will consider the sequence $b_n=na_{n+1}-S_n$ where $S_n=a_0+a_1+\ldots +a_n$ . Note that the condition we want to prove is equivalent to proving that there exists a unique $n$ such that $b_n<0 \leq b_{n+1}$ . Note that $b_0=-S_0<0$ and that $b_{n+1}-b_n=(n+1)a_{n+2}-S_{n+1}-na_{n+1}+S_n=(n+1)(a_{n+2}-a_{n+1})>0$ so $\{b_n\}$ is a monotonically increasing sequence of integers and starts below 0. Thus there is a unique $n$ where it crosses from below 0 to positive.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

math-olympiad-clown

14 posts

math-olympiad-clown

#141 h Mar 12, 2025, 6:49 AM

Y by

is this ok?
Lemma1: if there is a solution n=k ,then k is the only solution.

define g(n)=a(n)-a(n-1) ,then we can rewrite the restriction into :
g2+2g3+...+(n-1)g(n) < a0 <= g2+2g3+...+(n-1)g(n)+ng(n+1) , if n=k satisfies the inequality then
: g2+2g3+...+(k-1)g(k) < a0 <= g2+2g3+...+(k-1)g(k)+kg(k+1) FTSOC suppose there is a solution that n>k.
then we can get a0> g2+2g3+...+kg(k+1) , contradiction! analogously there's no sloution for n<k.

Now we define X(n)=g2+2g3+...+(n-1)g(n) , then the inequality can be change into X(n)< a0 <=X(n)+ng(n+1).
and then n=1,2,3,4 .... plug in we will get a lot of interval .and because a0>g2+2g3+...+(n-1)g(n)>=n(n-1)/2
we get an upper bound of n so that means there must be a unique interval that a0 is in. ??

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

eg4334

601 posts

eg4334

#142 h Today at 2:09 AM

Y by

define the sequence $b_n$ which is like $\sum_{i=0}^{n-1} a_i - (n-1)a_n$ so we need to prove that $b_n$ changes signs from strictly pos to neg exactly once. but $b_{n+1}-b_n = -n(a_{n+1}-a_n)$ which makes this obvious

This post has been edited 1 time. Last edited by eg4334, Today at 2:10 AM

Z K Y