Sunday, February 12, 2006

Weighted Bigness. Topic: Inequalities. Level: Olympiad.

Problem: Let $A = (a_1, a_2, \ldots, a_n)$ and $B = (b_1, b_2, \ldots, b_n)$ be sequences of reals such that for $k = 1, 2, \ldots, n$ we have

$\displaystyle \sum_{i=1}^k a_i \ge \sum_{i=1}^k b_i$.

Given a set of nonincreasing positive real weights $w = (w_1, w_2, \ldots, w_n)$, prove that for $k = 1,2, \ldots, n$ we have

$\displaystyle \sum_{i=1}^k a_iw_i \ge \sum_{i=1}^k b_iw_i$.

Solution: We will prove the result for an arbitrary value of $k$.

We know $\displaystyle \sum_{i=1}^k a_i \ge \sum_{i=1}^k b_i$. Multiply that inequality by $w_k$ to obtain

$\displaystyle \sum_{i=1}^k a_iw_k \ge \sum_{i=1}^k b_iw_k$, or

$\displaystyle \sum_{i=1}^{k-1} (a_i-b_i)w_k+(a_k-b_k)w_k \ge 0$.

But since $w_{k-1} \ge w_k$, we have

$\displaystyle \sum_{i=1}^{k-1} (a_i-b_i)w_{k-1} = \sum_{i=1}^{k-2} (a_i-b_i)w_{k-1}+(a_{k-1}-b_{k-1})w_{k-1} \ge \sum_{i=1}^{k-1} (a_i-b_i)w_k$, so

$\displaystyle \sum_{i=1}^{k-2} (a_i-b_i)w_{k-1}+(a_{k-1}-b_{k-1})w_{k-1}+(a_k-b_k)w_k \ge 0$ as well.

Repeating this process until we get to $1$, we obtain

$\displaystyle \sum_{i=1}^k (a_i-b_i)w_i \ge 0 \Rightarrow \sum_{i=1}^k a_iw_i \ge \sum_{i=1}^k b_iw_i$.

Since $k$ was arbitrarily chosen, it must hold for all values $1,2, \ldots, n$ and the result is proved. QED.

--------------------

Comment: Sort of an interesting result, though not particularly surprising. Just a little bit of algebra to work through and the proof is pretty straightforward.

--------------------

Practice Problem: Think up an inequality problem of your own! It's good practice.