### Sidebar

pow:problem3f23

Problem 3 (due Monday, October 9)

Given a sequence $a_1, a_2,\ldots, a_n$ of $n$ real numbers we construct a new sequence of $n-1$ numbers as follows: first we set $b_i=\max(a_i,a_{i+1})$ for $i=1,\ldots,n-1$. Then we choose randomly one index $i$ and add $1$ to $b_i$. This is our new sequence. After repeating this operation $n-1$ times we arrive at a single number $A$. Prove that if $a_1+\ldots +a_n=0$, then $A\geq \log_2 n$.

Here $\max(a,b)$ denotes the larger of the numbers $a,b$.

We did not receive any solutions. The key idea for our solution is to observe that the quantity $2^{a_1}+\ldots + 2^{a_n}$ is a monovariant for our operation on sequences, i.e. that this quantity computed for the new sequence is larger or equal than the quantity for the original sequence. It follows that $2^A\geq 2^{a_1} +\ldots + 2^{a_n}$. By the AMGM inequality (the arithmetic mean is always greater or equal than the geometric mean), we have $2^{a_1} +\ldots + 2^{a_n}\geq n$, hence $A\geq \log_2n$. For a detailed solution and some additional discussion see the following link Solution.