Note that $$a_j\le |a_j|\le\sum_{k=1}^{j}|a_k-a_{k-1}|\le\sum_{k=1}^{j}b_k$$and $$a_j\le |a_j|\le\sum_{k=j}^{n-1}|a_k-a_{k+1}|\le\sum_{k=j}^{n-1}b_{k+1}$$for each $j.$ Take minimal $i$ such that $(b_1+...+b_i)-(b_{i+1}+...+b_n)\ge 0$ and denote $x=b_1+...+b_i,y=b_{i+1}+...b_{n}.$ By minimality of $i$, we know that $$x-y=(b_1+...+b_{i-1})-(b_i+...+b_n)+2b_i<2b_i.$$ Therefore, using the initial observation, we arrive at \begin{align*} \sum_{k=1}^{n}(a_k+a_{k-1})b_k &\le\sum_{k=1}^{i-1}\left[\left(\sum_{l=1}^{k-1}b_l\right)+\left(\sum_{l=1}^{k}b_l\right)\right]b_k+\left[\left(\sum_{l=1}^{i-1}b_l\right)+y\right]b_i+\sum_{k=i+1}^{n}\left[\left(\sum_{l=k}^{n}b_l\right)+\left(\sum_{l=k+1}^{n}b_l\right)\right]b_k \\ &= x^2-(x-y)b_i+y^2\le x^2-\frac{(x-y)^2}{2}+y^2=\frac{(x+y)^2}{2}=2. \end{align*}

The statement of the problem as given was Quote: Let $ b_1, b_2,\dots,b_n$ be real numbers with sum $2$ and $a_0,a_1,\dots, a_n $ be real numbers satisfying: $ a_0=a_n=0$ and $|a_i-a_{i-1}|\leq b_i, i=1,2,\dots,n.$ Prove that $$ \sum_{i=1}^n(a_i+a_{i-1})b_i\leq 2$$ It was proposed by Nikolay Nikolov. I commented it here along with some physics interpretations.

huricane wrote: Note that $$a_j\le |a_j|\le\sum_{k=1}^{j}|a_k-a_{k-1}|\le\sum_{k=1}^{j}b_k$$and $$a_j\le |a_j|\le\sum_{k=j}^{n-1}|a_k-a_{k+1}|\le\sum_{k=j}^{n-1}b_{k+1}$$for each $j.$ Take minimal $i$ such that $(b_1+...+b_i)-(b_{i+1}+...+b_n)\ge 0$ and denote $x=b_1+...+b_i,y=b_{i+1}+...b_{n}.$ By minimality of $i$, we know that $$x-y=(b_1+...+b_{i-1})-(b_i+...+b_n)+2b_i<2b_i.$$ Therefore, using the initial observation, we arrive at \begin{align*} \sum_{k=1}^{n}(a_k+a_{k-1})b_k &\le\sum_{k=1}^{i-1}\left[\left(\sum_{l=1}^{k-1}b_l\right)+\left(\sum_{l=1}^{k}b_l\right)\right]b_k+\left[\left(\sum_{l=1}^{i-1}b_l\right)+y\right]b_i+\sum_{k=i+1}^{n}\left[\left(\sum_{l=k}^{n}b_l\right)+\left(\sum_{l=k+1}^{n}b_l\right)\right]b_k \\ &= x^2-(x-y)b_i+y^2\le x^2-\frac{(x-y)^2}{2}+y^2=\frac{(x+y)^2}{2}=2. \end{align*} Unless I'm misunderstanding the problem, this solutions seems quite overly complicated for a simple problem. Clearly, all $b_i$ are zero except for one or two of them. We can either have $b_i, b_j = 1$ for some $i, j$ and $b_k=0$ for the rest or we can have $b_i = 2$ for some $i$ and $b_j = 0$ for the rest. Hence, the only possible values for the array $(a_n, a_{n-1}, \cdots , a_0)$ is either $(0, 0, \cdots, 0)$ or $(0, 0, \cdots, a, a, \cdots, a, a, 0, 0 \cdots, 0, 0)$ where $|a| \leq 1$, since the array must be constant except for at most 2 changes. From this it is clear that if $(a_n, a_{n-1}, \cdots , a_0) = (0, 0, \cdots, 0)$, then $\sum_{i=1}^n(a_i+a_{i-1})b_i = 0$, whereas if $(a_n, a_{n-1}, \cdots , a_0) = (0, 0, \cdots, a, a, \cdots, a, a, 0, 0 \cdots, 0, 0)$, then $\sum_{i=1}^n(a_i+a_{i-1})b_i \leq a + a \leq 2$.

green_leaf wrote: Unless I'm misunderstanding the problem, this solutions seems quite overly complicated ... They are not overcomplicated, you misunderstood the problem. See the right statement in the post just above yours!

dgrozev wrote: green_leaf wrote: Unless I'm misunderstanding the problem, this solutions seems quite overly complicated ... They are not overcomplicated, you misunderstood the problem. See the right statement in the post just above yours! I don't see where I misunderstood the problem. The problem says that all $b_i$s are nonnegative integers with sum 2 so that means either all are zero except for one of them, which is 2, or all are 0 except for 2 of them which are both 1. Where have I gone wrong?

"Let $ b_1, b_2,\dots,b_n$ be real numbers with sum $2$" see #3

Nice problem. Firstly, we will reduce to the case where $a_0,a_1,...,a_n$ are all nonnegative numbers. Let $c_i=|a_i|$ for each $1\leq i\leq n$, then we have $$|c_i-c_{i-1}|\leq |a_i-a_{i-1}|\leq b_i$$Moreover, $$\sum_{i=1}^n(a_i-a_{i-1})b_i\leq \sum_{i=1}^n(c_i-c_{i-1})b_i$$Therefore, it suffices to deal with the case where all the $a_0,a_1,...,a_n$ are nonnegative numbers. Define the sequences $$x_1=b_1,x_2=b_1+b_2,x_3=b_1+b_2+b_3,...,x_{n-1}=b_1+b_2+...+b_{n-1}$$$$y_1=b_2+...+b_n,y_2=b_3+...+b_n,...,y_{n-1}=b_n$$Then from the condition we have $$a_i\leq x_i\hspace{5pt}\text{and}\hspace{5pt}a_i\leq y_i$$Let $k$ be the smallest integer such that $x_k\geq y_k$, since $x_k=2-y_k$, this implies $$x_k\geq 1\hspace{5pt}\text{and}\hspace{5pt} x_{k-1}\leq 1$$Now, letting $$d_i=\begin{cases}x_i&\text{if }i\leq k-1\\y_i&\text{if }i\geq k\end{cases}$$Then we have \begin{align*} \sum_{i=1}^b(a_i+a_{i-1})b_i&\leq\sum_{i=1}^{k-1}(d_i+d_{i-1})b_i\\ &=\sum_{i=1}^{k-1}(b_i+2\sum_{j=1}^{i-1}b_j)b_i+(2-b_k)b_k+\sum_{i=1}^n(b_i+2\sum_{j=i+1}^nb_j)b_i\\ &=(x_{k-1}+y_{k+1})^2-2x_{k-1}y_{k+1}+b_k(x_{k-1}+y_{k+1})\\ &=2(x_{k-1}+y_{k+1})-2x_{k-1}y_{k+1} \end{align*}Hence it suffices to show $$x_{k-1}y_{k+1}+1\geq x_{k-1}+y_{k+1}$$which rearranges to $$(x_{k-1}-1)(y_{k+1}-1)\geq 0$$which is true so we are done.

Quite an easy problem in the sense that the simplest upper bound for $a_{i}$ does the job: Note the obvious fact that $b_{i}\geq |a_{i}-a_{i-1}|\geq 0$. Suppose there exists some integer $m$, such that $\sum\limits_{i=1}^{m}b_{i}=1$. Then $a_{1}\leq b_{1}+a_{0}=b_{1}$, $a_{2}\leq b_{2}+a_{1}\leq b_{2}+b_{1}$, $\dots$, $a_{m-1}\leq \sum\limits_{i=1}^{m-1} b_{i}$ and $a_{m}\leq \sum\limits_{i=1}^{m} b_{i}=1$. The bounds for $a_{m+1}$ , $a_{m+2}$, $\dots$, $a_{n-1}$ are somewhat analogical: $a_{m+k}\leq \sum\limits_{i=m+k+1}^{n} b_{i}$. Now let's focus on the actual inequality: $$\sum\limits_{i=1}^{n} (a_{i-1}+a_{i})b_{i}=\sum\limits_{i=1}^{m} (a_{i-1}+a_{i})b_{i}+\sum\limits_{i=m+1}^{n} (a_{i-1}+a_{i})b_{i}$$$$\sum\limits_{i=1}^{m} (a_{i-1}+a_{i})b_{i}\leq \sum\limits_{i=1}^{m} \left(\sum\limits_{j=1}^{i-1} b_{j}+\sum\limits_{j=1}^{i} b_{j}\right)b_{i}=\sum\limits_{i=1}^{m}\left[b_{i}^{2}+2\sum\limits_{j=1}^{i-1} b_{j}b_{i} \right]=$$$$=\sum\limits_{i=1}^{m} b_{i}^{2}+2\left(\sum\limits_{1\leq j<i\leq m} b_{j}b_{i}\right)=\left(\sum\limits_{i=1}^{m} b_{i}\right)^{2}=1$$Analogically if we look at the sequence $a_{n}, a_{n-1}, a_{n-2}, \dots , a_{m+1}$ the method we used could be used in the same way, but the indexes are just descending, so: $$\sum\limits_{i=m+1}^{n} (a_{i-1}+a_{i})b_{i}\leq \left(\sum\limits_{i=m+1}^{n} b_{i}\right)^{2}=1$$Therefore $\sum\limits_{i=1}^{n} (a_{i-1}+a_{i})b_{i}\leq 2$ and we proved the inequality. Let's now go to the more general case: Let $m$ be the biggest integer, such that $\sum\limits_{i=1}^{n} b_{i}<1$ (if $b_{1}>1$ we can just look at the sequence from the other end, meaning we set $b_{n}=b_{1}$, $b_{n-1}=b_{2}$, and so on and now $b_{1}<1$). Here $b_{i}\geq 0$, so this sum is always monotonically increasing as we raise $m$. Now let $b_{m+1}=x+y$, where $\sum\limits_{i=1}^{m} b_{i}=1-x$. Note that $x>0, y>0$ (this will be useful later on). Let's form the following sequence: $c_{1}=b_{1}, c_{2}=b_{2},\dots, c_{m}=b_{m}, c_{m+1}=x, c_{m+2}=y, c_{m+3}=b_{m+2}, \dots ,c_{m+2+k}=b_{m+k+1}, \dots c_{n+1}=b_{n}$.Also, let $d_{1}=c_{1}, d_{2}=c_{1}+c_{2}, \dots ,d_{m}=\sum\limits_{i=1}^{m} c_{i}, d_{m+1}=1, \dots ,d_{m+k+1}=\sum\limits_{i=m+k+2}^{n+1} c_{i}$. Now the sequences $\{c_{i}\}$ and $\{d_{i}\}$ satisfy the condition from the problem statement. We will prove the following inequality: $$\sum\limits_{i=1}^{n} (a_{i-1}+a_{i})b_{i}\leq \sum\limits_{i=1}^{n+1} (d_{i-1}+d_{i})c_{i}$$The inequality: $(a_{i-1}+a_{i})b_{i}\leq (d_{i-1}+d_{i})c_{i}$ is obviously true for all $1\leq i \leq m$ and the inequality $(a_{i-1}+a_{i})b_{i}\leq (d_{i}+d_{i+1})c_{i+1}$ is true for all $m+2\leq i\leq n$. It's enough to show that $(x+y)(a_{m}+a_{m+1})\leq x(2-x)+y(2-y)$. From the bound we established for $a_{i}$ in the first case of the proof we know that $a_{m}\leq 1-x$ and $a_{m+1}\leq 1-y$. Now we can achieve the inequality: $(x+y)(a_{m}+a_{m+1})\leq (x+y)((1-x)+(1-y))=(x+y)(2-x-y)=$ $=x(2-x)+y(2-y)-2xy<x(2-x)+y(2-y)=c_{m+1}(d_{m}+d_{m+1})+c_{m+2}(d_{m+1}+d_{m+2})$ Therefore $\sum\limits_{i=1}^{n} (a_{i-1}+a_{i})b_{i}\leq \sum\limits_{i=1}^{n+1} (d_{i-1}+d_{i})c_{i}$ and we have found a sequence, satisfying the wanted condition and with a higher sum. But now from the first case we know that: $\sum\limits_{i=1}^{n+1} (d_{i-1}+d_{i})c_{i}\leq 2$ and so the inequality is true for all sequences.

Since $a_1\in \left[ -b_1;b_1\right]$ and $a_k\in \left[ a_{k-1}-b_k;a_{k-1}+b_k \right]$ it follows by induction that $a_k\leq \sum_{i=1}^{k} b_i$ $(1)$. Since $a_{n-1}\in \left[ -b_n;b_n\right]$ we in the same manner obtain $a_k\leq \sum_{i=k+1}^n b_i$ $(2)$. Next, take the maximal $t,$ such that $\sum_{i=1}^t b_i<1,$ and put $\sum_{i=1}^t b_i=1-\alpha ,\quad b_{t+1}=\alpha+\beta,\quad \sum_{i=t+2}^n b_i=1-\beta,$ so $$ \sum_{i=1}^n(a_i+a_{i-1})b_i=\sum_{i=1}^t(a_i+a_{i-1})b_i+(a_{t+1}+a_t)b_{t+1}+\sum_{i=t+2}^n(a_i+a_{i-1})b_i\leq$$$$\leq \left( \sum_{i=1}^t b_i^2+\sum_{1\leq i<j\leq t} 2b_ib_j \right)_{(1)}+\left( \sum_{i=t+2}^n b_i+\sum_{i=1}^t b_i\right) b_{t+1}+\left( \sum_{i=t+2}^n b_i^2+\sum_{t+2\leq i<j\leq n} 2b_ib_j \right)_{(2)}=$$$$=(1-\alpha)^2+(2-\alpha- \beta)(\alpha +\beta)+(1-\beta)^2=2-2\alpha \beta\leq 2\quad \blacksquare$$

We begin with an optimization. Call an index $i$ bad if $a_{i-1}, a_{i+1}\geq a_i$. Note that if we have a bad index $i$, we may remove $a_i$ and consider the sequence with $n-1$ terms $a_1, \dots , a_{i-1}, a_{i+1}, …, a_n$ with corresponding $b_1, …, b_i+b_{i+1}, \dots, b_n$, since, by comparing terms, it holds that $$(a_{i+1}+a_i)b_{i+1}+(a_i+a_{i-1})b_i\leq (a_{i-1}+a_{i+1})(b_i+b_{i+1}),$$and furthermore the problem conditions are conserved: the sum of the $b$ sequence is still 2, and the inequality $|a_{i+1}-a_{i-1}|\leq |a_{i+1}-a_i|+|a_i-a_{i-1}|=b_{i+1}+b_i$ holds by the triangle inequality. Thus, we may assume that there is no bad index. However, it is then clear that the sequence must be of the form $a_0=0\leq a_1\leq \cdots \leq a_k =1 \geq \cdots \geq a_n=0$ for some $1\leq k \leq n$, so we may succesfully bound the sum telescopically $$S=\sum_{i=1}^n (a_i+a_{i-1})b_i\leq \sum_{i=1}^n (a_i+a_{i-1})|a_i-a_{i-1}|=\sum_{i=1}^n \max(a_i, a_{i-1})^2-\min(a_i, a_{i-1})^2=a_k^2-a_0^2+a_k^2-a_n^2=2a_k^2=2,$$as desired.