AoPSWiki

Try our innovative online adaptive learning system, Alcumus.
Over 1100 problems and 60+ video lessons. FREE!

Personal tools

Search

Toolbox

1999 BMO Problems/Problem 4

From AoPSWiki

Problem

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

Solution

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}...$ 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) \\&...$ 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 \\&= (...$ 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.

Resources

Retrieved from "http://www.artofproblemsolving.com/Wiki/index.php/1999_BMO_Problems/Problem_4"

Category: Olympiad Algebra Problems

Try our innovative online adaptive learning system, Alcumus.
Over 1100 problems and 60+ video lessons. FREE!

© Copyright 2008 AoPS Incorporated. All Rights Reserved. • Foundation • Privacy • Contact Us