Partition of 4-tuples

Question

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$?

Answer 1

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.