Two groups with close sums in two coordinates Let $n$ be a positive integer and $x_1,\dots,x_n,y_1,\dots,y_n\in[0,1]$. What is the smallest $r$ (in terms of $n$) such that the indices $1,2,\dots,n$ can always be divided into two groups $A,B$ such that $$\left|\sum_{i\in A}x_i-\sum_{i\in B} x_i\right|\le r \text{ and } \left|\sum_{i\in A}y_i-\sum_{i\in B} y_i\right|\le r?$$
If the $y_i$'s were not there, we would have $r=1$ because we can add numbers to $A$ and $B$ while keeping the difference between their sums at most $1$. But with both $x_i$'s and $y_i$'s, should $r$ be growing with $n$?
 A: This is a partial answer, one can show $r \le 3$ for all $n$.  
Before we start, we need to establish some facts.


*

*Let $\| (x,y) \| = \max\{|x|,|y|\}$ be the max-norm on $\mathbb{R}^2$.  

*Let $I_0 = [0,\frac12]$, $I_1 = [\frac12,1]$, $J_0 = [-\frac12,0]$, $J_1 = [-1,-\frac12]$.

*For all $p_{10} \in I_1 \times I_0$, $p_{01} \in I_0 \times I_1$ and $p_{11} \in I_1 \times I_1$, 
$$\|p_{10}\|, \|p_{01}\|, \|p_{11}\|, \|p_{10} - p_{01}\|, \|p_{10} - p_{11}\|, \|p_{01} - p_{11}\|, \|p_{10} + p_{01} - p_{11}\| \le 1\tag{*1a}$$

*For all $q_{10} \in I_1 \times J_0$, $q_{01} \in I_0 \times J_1$ and $q_{11} \in I_1 \times J_1$, 
$$\|q_{10}\|, \|q_{01}\|, \|q_{11}\|, \|q_{10} - q_{01}\|, \|q_{10} - q_{11}\|, \|q_{01} - q_{11}\|, \|q_{10} + q_{01} - q_{11}\| \le 1\tag{*1b}$$


To derive the bound $r \le 3$, let us look at an auxiliary problem with larger bound.
For any $n > 0$, let $S_n$ be following statement:

For any points $p_1, \ldots, p_n$ with $\| p_i \| \le 1$, there exists a partition of the indices into two groups $A,B$ such that
  $$\left\|\sum_{i \in A} p_i - \sum_{i\in B}p_j\right\| \le 4$$



*

*For $n \le 4$, $S_n$ is trivially true.

*For $n > 4$, assume $S_k$ is true for all $k < n$.
Let $p_1, \ldots, p_n$ be any $n$ points with $\| p_i \| \le 1$. Since the truth value of $S_n$ remains unchange when we replace some $p_k$ by $-p_k$, we can assume all $p_k \in [0,1] \times [-1,1]$.
Split $[0,1] \times [-1,1]$ into 8 squares of side $\frac12$ and arrange them
into 3 groups:
$$\begin{cases}
  A :& I_0 \times I_0, I_0 \times J_0\\
  B :& I_1 \times I_0, I_0 \times I_1, I_1 \times I_1\\
  C :& I_1 \times J_0, I_0 \times J_1, I_1 \times J_1
\end{cases}$$
If one pick two points from same square, their difference has max-norm $\le \frac12$. Together with points from squares in group $A$ already have max-norm $\le \frac12$, we find with up to $6$ exceptions (one from each squares in either group $B$ or $C$), we can group the remaining points into at most  $\frac{n}{2} + 2 < n$ vectors with max-norm $\frac12$. 
By induction assumption, we can find a partition of the vectors to
make their sum/difference has max-norm $\le \frac12 \cdot 4 = 2$. Expand the
vectors back into their constituent points, this given us a partition of the $n$ points (excluding the exceptions) with a sum/difference whose max-norm $\le 2$.
Using $(*1a)$/$(*1b)$, we can combine the exceptions (if any) coming from squares in group $B$/group $C$ into two vectors with max-norm $\le 1$. This implies the original $n$ points can be combined into one with max-norm $\le 2 + 1 + 1 = 4$. In short,
$$S_1 \land S_2 \land \ldots \land S_{n-1}\quad\implies\quad S_n$$
By principle of introduction, $S_n$ is true for all $n$. 
The original problem can be viewed as a special case of this auxiliary problem. The difference is in the original problem, all $p_k \in [0,1]^2$. This means there will not be any exception coming from squares in group $C$. Repeating
above arguments, we can combine all these $p_k \in [0,1]^2$ into a vector with max-norm $\le 2 + 1 = 3$ instead.
