Prueba elegante de una simple desigualdad

Question

Estoy buscando una elegante prueba de la identidad siguiente: $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\}$

La prueba que actualmente tengo implica revisión de los casos, que es lo que me gustaría evitar. Si hay alguna manera algebraica y combinatoria geométrica lineal para explicar esta desigualdad intuitivamente, me encantaría oirlo.

Gracias de antemano por su tiempo.

Answer 1

Consideremos el caso de min-max (azul) en comparación con el caso "mixto" (rojo). Podemos emparejar al rojo al azul como se muestra y nos quedamos con el exceso que se muestra para el caso de min-max.

Answer 2

Hay un par de niza no algebraicas enfoques; he aquí una expresión algebraica enfoque que no es demasiado malo. Sin pérdida de generalidad $w_1\ge z_1$; la pregunta es si podemos aumentar el valor de la expresión $w_1w_2+z_1z_2$ intercambiando $w_2$ y $z_2$. Tenemos

$$\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)\\ y=(w_1-z_1)(z_2-w_2)\;, \end{align*}$$

para cambiar de $w_2$ y $z_2$ aumenta el valor si y sólo si $w_1>z_1$ y $z_2>w_2$. (Recordemos que la suposición de que $w_1\ge z_1$.) Y esto es exactamente lo que queríamos demostrar.

(Es esencialmente una prueba de que el algoritmo greedy).

Answer 3

Aquí le damos otro enfoque:

Tienes una bolsa llena de dos tipos de monedas; un tipo tiene valor de z_1 y el otro w_1. Puede escoger $w_2 monedas de un tipo de$ y $z_2$ monedas de otro. Si usted quiere conseguir la máxima cantidad posible, ¿qué debe usted hacer recogiendo las monedas? (Algoritmo voraz)

Answer 4

¿Seguramente solo puede atacar la cabeza de álgebra en? Usando la identidad $max(a,b) = \frac{1}{2}(a+b+|a-b|)$ y $min(a,b) = \frac{1}{2}(a+b-|a-b|)$ elimina la necesidad de revisar los casos.

Answer 5

La suma de los tamaños de los dos conjuntos es el tamaño de su unión más el tamaño de su intersección. Deje que uno será el rectángulo con vértices diagonalmente opuestos $(0,0)$ y $(w_1,w_2).$ Dejar que el otro sea el rectángulo con vértices diagonalmente opuestos $(0,0)$ y $(z_1,z_2).$ Vamos al tamaño de la zona. El producto de $\max\{w_1,z_1\}\max\{w_2,z_2\}$ es el área del rectángulo delimitador, y por lo tanto mayor que o igual a la superficie de la unión. El producto de $\min\{w_1,z_1\}\min\{w_2,z_2\}$ es el área de la intersección.