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.

No comments:

Post a Comment