1999 BMO Problems/Problem 4


Let $\{a_n \}_{n\ge 0}$ be a non-decreasing, unbounded sequence of non-negative integers with $a_0=0$. Let the number of members of the sequence not exceeding $n$ be $b_n$. Prove that for all positive integers $m$ and $n$, we have \[a_0 + a_1 + \dotsb + a_m + b_0 + b_1 + \dotsb + b_n \ge (m+1)(n+1) .\]


Note that for arbitrary nonnegative integers $i,j$, the relation $j \le a_i$ is equivalent to the relation $i \ge b_{j-1}$. It then follows that \[\sum_{i=0}^m a_i = \sum_{i=0}^m \sum_{j=1}^{a_i} 1 = \sum_{j=1}^{a_m} \sum_{i=b_{j-1}}^m 1 = \sum_{j=1}^{a_m} ( m+1 - b_{j-1} ) = \sum_{j=0}^{a_m-1} (m+1 - b_j ) .\] Note that if $j \le a_m-1$, then there are at most $m$ terms of $\{ a_k\}_{k\ge 0}$ which do not exceed $j$, i.e., $b_j \le m$; it follows that every term of the last summation is positive.

Now, if $a_m \ge n+1$, then we have \begin{align*} \sum_{i=0}^m a_i + \sum_{j=0}^n b_j &= \sum_{j=n+1}^{a_m-1}(m+1 - b_j) + \sum_{j=0}^n (m+1 - b_j + b_j) \\ &= \sum_{j=n+1}^{a_m-1}(m+1-b_j) + (n+1)(m+1) \ge (n+1)(m+1), \end{align*} as desired. On the other hand, if $a_m < n+1$, then for all $j\ge a_m$, $b_j \ge m+1$. It then follows that \begin{align*}  \sum_{i=0}^m a_j + \sum_{j=0}^n b_j &= \sum_{j=0}^{a_m-1}(m+1 - b_j + b_j) + \sum_{j=a_m}^n b_j \\ &= (a_m)(m+1) + \sum_{j=a_m}^n b_j \\ &\ge (a_m)(m+1) + (n+1-a_m)(m+1) = (n+1)(m+1), \end{align*} as desired. Therefore the problem statement is true in all cases. $\blacksquare$

Alternate solutions are always welcome. If you have a different, elegant solution to this problem, please add it to this page.