8
$\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$
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$ Commented Nov 10, 2018 at 21:23
  • $\begingroup$ @user44191 Putting the first two vectors into $X$, you get the required inequalities even without `$1+$'. $\endgroup$ Commented Nov 13, 2018 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$ Commented May 20, 2019 at 11:40

1 Answer 1

2
$\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$

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.