Problem of the Week

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$.

Overview

Every other Monday (starting 08/28/23), we will post a problem to engage our mathematical community in the problem solving activity and to enjoy mathematics outside of the classroom. Students (both undergraduate and graduate) are particularly encouraged to participate as there is no better way to practice math than working on challenging problems. If you have a solution and want to be a part of it, e-mail your solution to Marcin Mazur (mazur@math.binghamton.edu) by the due date. We will post our solutions as well as novel solutions from the participants and record the names of those who've got the most number of solutions throughout each semester.

When you submit your solutions, please provide a detailed reasoning rather than just an answer. Also, please include some short info about yourself for our records.