pow:problem3f23 [Department of Mathematics and Statistics, Binghamton University]

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.

User Tools

Site Tools

−Sidebar

Page Tools