7
$\begingroup$

Some $4$-tuples of positive real numbers $(a_1,b_1,c_1,d_1),\dots,(a_n,b_n,c_n,d_n)$ are given, with all $a_i,b_i,c_i,d_i\leq 1$. Can we always partition $\{1,2,\dots,n\}$ into two subsets $X,Y$ so that $$1+\sum_Xa_i\geq \sum_Ya_i\text{ and } 1+\sum_Xb_i\geq \sum_Yb_i$$ and $$\sum_Xc_i\leq 1+\sum_Yc_i\text{ and } \sum_Xd_i\leq 1+\sum_Yd_i?$$

It is shown here that the partition is possible if we replace the $1$'s by $3$'s. What is the best possible value between $1$ and $3$?

$\endgroup$
  • $\begingroup$ Extreme cases may be useful here; one is $(1, 1, 1, 0), (1, 1, 0, 1), (1, 0, 1, 1), (0, 1, 1, 1), (1, 1, 1, 1)$. $\endgroup$ – user44191 Nov 10 '18 at 21:23
  • $\begingroup$ @user44191 Putting the first two vectors into $X$, you get the required inequalities even without `$1+$'. $\endgroup$ – Ilya Bogdanov Nov 13 '18 at 22:33
1
$\begingroup$

Mike Earnest's answer at MSE may be improved even more, in order to get the estimate of $2$ --- but this is also non-sharp. Indeed, in his last part, we may assume that $x_1\geq x_2\geq x_3\geq x_4$. Next, we may assume that $x_2\geq 0$.

Now, if $x_3+x_4\leq 0$, then we may set $x_3'=x_4'=-1$, $x_1'=x_2'=1$, changing each coordinate by at most 2.

Asusume now that $x_3+x_4\geq 0$ --- this is more delicate; then $x_3\geq 0$. Choose an index $i\in\{1,2,3\}$ such that $a_i$ is not the strict minimum among $a_1,a_2,a_3$, and $b_i$ is not the strict minimum among $b_1,b_2,b_3$. Then we set $x_i'=-1$ and $x_j'=1$ for all other $j$. Surely, the $c$- and $d$-coorditnates increased by at most 2 (this could happen due to $x_i'$ only!). Now let us show that $a$-coordinate did so as well. Let $a_k=\min(a_1,a_2,a_3)$ with $k\in\{1,2,3\}\setminus\{i\}$, and set $\ell=\{1,2,3\}\setminus\{i,k\}$. Then $$ \sum(x_j'a_j-x_ja_j)=(1-x_4)a_4+(1-x_\ell)a_\ell+(1-x_k)a_k+(-1-x_i)a_i \leq (1-x_4)+(1-x_\ell)+(1-x_k-1-x_i)a_k\leq (2-x_4-x_\ell)+0\leq 2, $$ as required. The $b$-coordinate argument is similar.

NB. It seems that such considerations (by making an argument more case distinctive) may lead to a constant of $3/2$. But this still would not give an optimal bound --- at least it seems so!

Notice also that this problem has much in common with the famous problem on sign sequences (see, e.g., Chapter 4 in this survey; the method there is more or less the same as in the MSE answer). The difference is that in your problem the coordinates have fixed signs.

$\endgroup$

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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