Given a set of positive values $v_1, v_2, ..., v_n$ and a set positive of factors $\alpha_1, \alpha_2, ..., \alpha_n$, both ordered increasingly, show the maximum linear combination you can get is
$$\sum_{i=1}^{n}\alpha_i \cdot v_i$$
Asked
Active
Viewed 730 times
0
-
Have you tried induction on $n$? – ajotatxe Apr 26 '15 at 18:12
-
Maximum in what sense? Perhaps you are looking for the http://en.wikipedia.org/wiki/Rearrangement_inequality ? – Martin R Apr 26 '15 at 18:15
-
@MartinR I can't imagine another sense of "maximum" in this case but the usual. Yup, that's what I was looking for, thank you! – cronos2 Apr 28 '15 at 10:39
1 Answers
0
By contradiction, suppose the maximum is not obtained in this way. Then the maximum contains two products $a_iv_j+a_kv_l$ with $a_i<a_k$ and $v_j>v_l$. We prove that $a_iv_l+a_kv_k>a_iv_j+a_kv_l$:
Let $v_j=v+d$ and $v_l=v-d$ and let $a_k=a+c$ and $a_i=a-c$. with $c,d> 0$
In this way $a_iv_j+a_kv_l=(a-c)(v+d)+(a+c)(v-d)=(av+ad-cv-dc)+(av-ad+cv-cd)$
$a_iv_l+a_kv_j=(a-c)(v-d)+(a+c)(v+d)=(av-ad-cv+cd)+(av+ad+cv+cd)$
And so when we substract everything cancels except for $-4dc$ and so the difference is negative as desired.
This would yield a contradiction because when you take the linear combination that is equal to the "maximum linear combination" and switch the $a_iv_j+a_kv_l$ for $a_iv_l+a_kv_j$ you get a larger linear combination.
This inequality is sometimes called the rearrangement inequality or "Desigualdad del reacomodo" in spanish.
Asinomás
- 105,651