Dividir pares de números reales no negativos

Question

Deja$N=\{1,2,\dots,n\}$ con$n\geq 2$, y pares dados$(a_1,b_1),\dots,(a_n,b_n)$ con$a_i,b_i\geq 0$. ¿Podemos siempre dividir$N$ en conjuntos no vacíos$A$ y$B$ para que:

$\sum_{i\in A} a_i\geq \sum_{i\in B} a_i - \min_{i\in B} a_i$ Y$\sum_{i\in B} b_i\geq \sum_{i\in A} b_i - \min_{i\in A}b_i$?

Por ejemplo, si los pares son$(10,7),(3,1),(2,2),(1,3)$, entonces podemos poner$(10,7)$ en un conjunto (cualquiera de los conjuntos) y los tres pares restantes en el otro conjunto.

Answer 1

La respuesta es sí. Partición de $N$ en dos conjuntos de $C,D$, de modo que $\sum_{i\in C} a_i$ $\sum_{i\in D}a_i$ están tan cerca el uno del otro como sea posible. Si las dos cantidades no son iguales y hay índices de $i$$a_i=0$, a continuación, poner todos los indices en conjunto con la suma menor.

Si $\sum_{i\in C}b_i\geq \sum_{i\in D}b_i$, luego deje $B=C$$A=D$. De lo contrario vamos a $A=C$$B=D$.

Pretendemos que esta división satisface la condición dada. Por definición de $A$$B$, de inmediato nos han $$\sum_{i\in B}b_i\geq \sum_{i\in A}b_i\geq \sum_{i\in A}b_i-\min_{i\in A}b_i.$$ Ahora, supongamos por contradicción que $\sum_{i\in A}a_i<\sum_{i\in B}a_i-\min_{i\in B}a_i$. Supongamos que $j\in B$ es tal que $a_j=\min_{i\in B}a_i$. Tenga en cuenta que $a_j> 0$. Considere la posibilidad de mover $j$$B$$A$. Si $\sum_{i\in A}a_i+a_j\leq \sum_{i\in B}a_i-a_j$, entonces tenemos una partición con más sumas de dinero, de una contradicción. Otra cosa, $\sum_{i\in A}a_i+a_j> \sum_{i\in B}a_i-a_j$. Para que la partición con $j$ movido de $B$ $A$a no ceder más de cerca suma, debemos tener $\sum_{i\in A}a_i+a_j\geq\sum_{i\in B}a_i$. Pero esto significa $\sum_{i\in A}a_i\geq\sum_{i\in B}a_i-\min_{i\in B}a_i$, una contradicción.