25
$\begingroup$

I'm looking for an elegant proof of the following identity: for $w_1,w_2,z_1,z_2\ge 0$,

$w_1w_2+z_1z_2\le \max\{z_1,w_1\}\max\{z_2,w_2\}+\min\{z_1,w_1\}\min\{z_2,w_2\}$

The proof I currently have involves checking by cases, which is what I'd like to avoid. If there's some linear algebraic, combinatorial, or geometric way to explain this inequality intuitively, I'd love to hear it.

Thanks in advance for your time.

$\endgroup$
20
$\begingroup$

enter image description here

Consider the min-max case (blue) compared to the "mixed" case (red). We can match out the red to blue as shown and we are left with the excess shown for the min-max case.

$\endgroup$
  • $\begingroup$ How did you make those pictures? $\endgroup$ – Jorge Fernández Hidalgo Feb 24 '15 at 18:42
  • $\begingroup$ I used Powerpoint 2010, it has a nice "Save as picture" option. $\endgroup$ – Joffan Feb 24 '15 at 19:16
13
$\begingroup$

There are a couple of nice non-algebraic approaches; here's an algebraic approach that isn't too bad. Without loss of generality $w_1\ge z_1$; the question is whether we can increase the value of the expression $w_1w_2+z_1z_2$ by interchanging $w_2$ and $z_2$. We have

$$\begin{align*} (w_1z_2+w_2z_1)-(w_1w_2+z_1z_2)&=w_1(z_2-w_2)-z_1(z_2-w_2)\\ &=(w_1-z_1)(z_2-w_2)\;, \end{align*}$$

so switching $w_2$ and $z_2$ increases the value if and only if $w_1>z_1$ and $z_2>w_2$. (Recall the assumption that $w_1\ge z_1$.) And this is exactly what we wanted to show.

(It's essentially a proof that the greedy algorithm works.)

$\endgroup$
8
$\begingroup$

Here's another approach:

You have a bag full of two type of coins; one type has value $z_1$ and the other $w_1$. You are allowed to pick $w_2$ coins of one type, and $z_2$ coins of another. If you want to get the maximum possible amount, how should you go about picking the coins? (Greedy algorithm)

$\endgroup$
  • 10
    $\begingroup$ That's not a proof: it's a question. You can't just assert the answer "Oh, I pick $\max\{w_2,z_2\}$ of the larger denomination and $\min\{w_2,z_2\}$ of the smaller denomination" because the optimality of that choice is precisely the thing you were trying to prove! $\endgroup$ – David Richerby Feb 22 '15 at 8:25
  • 3
    $\begingroup$ This is convincing to me, at least - it sort of makes me see that we get $z_1+w_1$ coins of value at least $\min(z_2,w_2)$. Then, we choose to increase the value of $z_1$ or $w_1$ of the coins by $\max(z_2,w_2)-\min(z_1,w_1)$ - and obviously, as the gain in value is fixed, we should choose whichever of $z_1$ or $w_1$ is greater. $\endgroup$ – Milo Brandt Feb 22 '15 at 19:26
  • 1
    $\begingroup$ I also agree that Saibal's question makes the inequality blisteringly obvious. Let's make it concrete: you have a bag full of quarters and a bag full of dimes. You get to pick 9 coins from one bag and 3 from the other. Which bag should you pick 9 from? (If this doesn't do it for you: you are going to get 3 quarters and 3 dimes plus 6 extra coins of one type. What type should that be?) $\endgroup$ – Will Orrick Feb 23 '15 at 5:06
  • 5
    $\begingroup$ @DavidRicherby This is not a proof: it's a question, which connects the seemingly abstract problem to something the OP can probably immediately understand, and which then will help him understand the abstract problem. This fits perfectly to "some linear algebraic, combinatorial, or geometric way to explain this inequality intuitively", which is what the OP wanted instead of a proof. $\endgroup$ – JiK Feb 23 '15 at 8:23
2
$\begingroup$

Surely you can just attack the algebra head on? Using the identities $max(a,b) = \frac{1}{2}(a+b+|a-b|)$ and $min(a,b) = \frac{1}{2}(a+b-|a-b|)$ eliminates the need to check cases.

$\endgroup$
1
$\begingroup$

The sum of the sizes of two sets is the size of their union plus the size of their intersection. Let one set be the rectangle with diagonally opposite vertices $(0,0)$ and $(w_1,w_2).$ Let the other be the rectangle with diagonally opposite vertices $(0,0)$ and $(z_1,z_2).$ Let size be area. The product $\max\{w_1,z_1\}\max\{w_2,z_2\}$ is the area of the bounding rectangle, and therefore greater than or equal to the area of the union. The product $\min\{w_1,z_1\}\min\{w_2,z_2\}$ is the area of the intersection.

$\endgroup$
1
$\begingroup$

This is a special case of what's sometimes called the "rearrangement inequality." A simple, intuitive inductive proof can be found on the Art of Problem Solving wiki.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.