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

  • $\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
  • $\begingroup$ Since nobody seems to have mentioned it yet, let me say that this problem is practically equivalent to determine the highest possible (combinatorial) discrepancy that 4 sets ($\{a_1,\ldots,a_n\}$,$\{b_1,\ldots,b_n\}$,$\{c_1,\ldots,c_n\}$,$\{d_1,\ldots,d_n\}$) can have. The fact that this is some constant is obvious and the value of the constant is usually studied as a function of the number of sets (here 4). See this seminal paper by Spencer: ams.org/journals/tran/1985-289-02/S0002-9947-1985-0784009-0/… $\endgroup$ – domotorp May 20 '19 at 11:40

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.

| cite | improve this answer | |

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.