$a_0, a_1, \ldots, a_{100}$ and $b_1, b_2,\ldots, b_{100}$ are sequences of real numbers, for which the property holds: for all $n=0, 1, \ldots, 99$, either $$a_{n+1}=\frac{a_n}{2} \quad \text{and} \quad b_{n+1}=\frac{1}{2}-a_n,$$or $$a_{n+1}=2a_n^2 \quad \text{and} \quad b_{n+1}=a_n.$$Given $a_{100}\leq a_0$, what is the maximal value of $b_1+b_2+\cdots+b_{100}$?
Problem
Source: Turkey Team Selection Test 2018 P6
Tags: algebra, Sequence
27.03.2018 13:58
It's easy to see that if $a_0 < 0$, $a_{100}$ always more than $a_0$ So, it's sufficient to consider only case $a_0 \ge 0$ It's easy to see that $a_i \ge 0$ for all $i=1,2,...,100$ From $a_i \ge 0$, it's easy to show that $b_{i+1} \le \frac{1}{2}+a_{i+1}-a_{i}$ in both choices So, $b_1+...+b_{100} \le 50+a_{100}-a_{0} = 50$ Equality holds when $a_{i}=0$ and $b_{i}=\frac{1}{2}$ for all $i=0,1,...,100$
20.04.2018 14:44
Gems98 wrote: It's easy to see that if $a_0 < 0$, $a_{100}$ always more than $a_0$ So, it's sufficient to consider only case $a_0 \ge 0$ It's easy to see that $a_i \ge 0$ for all $i=1,2,...,100$ From $a_i \ge 0$, it's easy to show that $b_{i+1} \le \frac{1}{2}+a_{i+1}-a_{i}$ in both choices So, $b_1+...+b_{100} \le 50+a_{100}-a_{0} = 50$ Equality holds when $a_{i}=0$ and $b_{i}=\frac{1}{2}$ for all $i=0,1,...,100$ how did you come up with it??
21.04.2018 00:04
I'll provide a solution which, while using the same idea as Gems98's solution, provides motivation for such a result. Firstly, if $a_0$ is negative, then it is clear that $a_{100}$ is bigger than $a_0$, a contradiction. Now, let us presume that $a_{n+1}=2{a_n}^2$ and $b_{n+1}=a_n$. I used the inequality ${a_n}^2\ge {a_n}-\frac{1}{4}$, which is clear from AM-GM. Multiplying this by 2, we get that $a_{n+1}+\frac{1}{2}\ge 2{a_n}$, which is equivalent to $b_{n+1}\leq \frac{1}{2}+a_{n+1}-a_n$. Now, it is clear that this inequality is true for the other possible value of $b_{n+1}$. Adding all the $b_i$'s up, we get that $\sum b_i\leq 50+a_{100}-a_0$ and, since $a_{100}\leq a_0$, we get that $\sum b_i\leq 50$. An example for this is $a_i=\frac{1}{2}$ for every $i$. $Q.E.D$
03.02.2019 05:10
Quote: how did you come up with it?? Since the only condition we have is $0\geqslant a_{100}-a_0=\sum\limits _{i=0}^{99}(a_{i+1}-a_i)$, it is natural to suppose that $b_i\leqslant k+t(a_{i+1}-a_i)$ for some constant k,t under favourable circumstances,and equality holds when $a_{i+1}=a_i$. Plugging in some special cases(easy to guess $0\leqslant a_i\leqslant 0.5$)and combining the condition yields $k=\frac{1}{2}$ and $t=1$, which is true for positive $a_i$.
12.06.2024 15:48
atmargi wrote: I'll provide a solution which, while using the same idea as Gems98's solution, provides motivation for such a result. Firstly, if $a_0$ is negative, then it is clear that $a_{100}$ is bigger than $a_0$, a contradiction. Now, let us presume that $a_{n+1}=2{a_n}^2$ and $b_{n+1}=a_n$. I used the inequality ${a_n}^2\ge {a_n}-\frac{1}{4}$, which is clear from AM-GM. Multiplying this by 2, we get that $a_{n+1}+\frac{1}{2}\ge 2{a_n}$, which is equivalent to $b_{n+1}\leq \frac{1}{2}+a_{n+1}-a_n$. Now, it is clear that this inequality is true for the other possible value of $b_{n+1}$. Adding all the $b_i$'s up, we get that $\sum b_i\leq 50+a_{100}-a_0$ and, since $a_{100}\leq a_0$, we get that $\sum b_i\leq 50$. An example for this is $a_i=\frac{1}{2}$ for every $i$. $Q.E.D$ What is your motivation of your usage of ${a_n}^2\ge {a_n}-\frac{1}{4}$? Gems98 wrote: It's easy to see that if $a_0 < 0$, $a_{100}$ always more than $a_0$ So, it's sufficient to consider only case $a_0 \ge 0$ It's easy to see that $a_i \ge 0$ for all $i=1,2,...,100$ From $a_i \ge 0$, it's easy to show that $b_{i+1} \le \frac{1}{2}+a_{i+1}-a_{i}$ in both choices So, $b_1+...+b_{100} \le 50+a_{100}-a_{0} = 50$ Equality holds when $a_{i}=0$ and $b_{i}=\frac{1}{2}$ for all $i=0,1,...,100$ on your line $5$,shouldn't it be $b_1+...+b_{100} \le 50+a_{100}-a_{0} \le 50$ as in the statement it says $a_{100}\leq a_0$?
23.08.2024 17:54
$$\sum_{n=1}^{100}(a_n-a_{n-1}/2)(a_n-2a_{n-1}^2)=0$$$$\sum_{n=1}^{100}\frac{a_n}{a_{n-1}}+\sum_{n=1}^{100}\frac{a_{n-1}^2}{a_n}=2\sum_{n=1}^{100}a_{n-1}+50.$$By Cauchy $$\sum_{n=1}^{100}\frac{a_n}{a_{n-1}}-\sum_{n=1}^{100}a_{n-1}=\sum_{n=1}^{100}a_{n-1}-\sum_{n=1}^{100}\frac{a_{n-1}^2}{a_n}+50\le 50.$$Since $b_n=\frac{a_n}{a_{n-1}}-a_{n-1},$ $\sum b_n\le 50.$ Equality holds when $a_i=b_i=1/2.\Box$