Two groups of numbers with close sums

Question

Let $n$ be a positive integer, and independently randomize numbers $x_1,\dots,x_n,y_1,\dots,y_n$ from $(0,1)$ uniformly. Fix a real number $r>0$. Let $p_n$ be the probability that the indices $\{1,\dots,n\}$ can be divided into two groups $A,B$ so that $$\left|\sum_{i\in A}x_i-\sum_{i\in B} x_i\right|<r \text{ and } \left|\sum_{i\in A}y_i-\sum_{i\in B} y_i\right|<r.$$ Is it true that $p_n$ approaches $1$ as $n\rightarrow\infty$?

If we only have the $x_i$'s, then this is true by the following method. We can let $n$ be large enough so that there are likely more than $2/r$ numbers that are in $I=[r/2, r]$. We put the numbers one by one into the two groups, starting with those outside $I$, keeping the difference between the two groups less than $1$. Then we put in the numbers in $I$ so that the difference between the two groups is less than $r$.

Answer 1

Let me try to describe an idea similar to yours(it look like it's basically the same) for the case when we have only $x_{i}$'s and then try to discuss how the same approach could be eventually applied when we add $y_{i}$'s(you might elaborate it, I don't have a solution yet):

• ['One dimensional case'] It's clear that it suffices to prove the fact for very small values of $r$. Let $n$ be big enough so we have at least $\frac{2}{r}$ different $x$'s in the interval $[\frac{r}{2}, r]$ (and having some other numbers as well) with probability greater than some $1-\epsilon$ (this $\epsilon$ could be chosen arbitrary small). Assume the contrary, i.e. there are no such $A$, $B$, or equivalently that there is no subset of indeces $A$, for which $$\frac{S_{0}}{2}-\frac{r}{2}\leq \sum_{i\in A}x_{i} \leq \frac{S_{0}}{2}+\frac{r}{2}$$. Here, $S_{0}$ is the sum of all the $n$ r.v. that were generated. Now, take one of those numbers $r_{1}\in [\frac{r}{2}, r]$. The existence of such number implies that after we remove $r_{1}$, we wouldn't be able to find a subset of indices $A'$, s.t. $$\frac{S_{0}}{2}-\frac{r}{2} - r_1\leq \sum_{i\in A'}x_{i} \leq \frac{S_{0}}{2}+\frac{r}{2}$$ Indeed, if we have such subset, either it's sum will be in $[\frac{S_{0}}{2}-\frac{r}{2},\frac{S_{0}}{2}+\frac{r}{2}]$, or we would be able to add $r_1$ to obtain subset in the same forbidden interval. Now, apply the same trick with another $r_2 \in [\frac{r}{2}, r]$ to extend the forbidden interval from below even more. After enough number of steps/extensions(we'll be able to make at least 2/r such steps), we'll get forbidden interval of lenght $\geq 1$ , but this is a contradiction since if we start with the empty set and add the remaining elements in arbitrary order, we'll be catched into this huge interval at some point($\forall i (x_i \leq 1)$).

• ['Two dimensional case'] Now, we have both $x_i$'s and $y_i$'s. Similarly, assume the contrary and let $n$ is big enough so that we have at least $\frac{2}{r}$ tuples $(x_i,y_i)$ s.t. $x_i\in [\frac{r}{2}, r]$ and $y_i\in [\frac{r}{2}, r]$. Apply the same 'extension' approach several times with numbers from $[\frac{r}{2}, r]$. At the end you will have that for some $S_1$ and $S_2$, which are going to be the sums of all x's and y's, there is no subset of indices A, s.t. $$\frac{S_1}{2} - 1\leq \sum_{A}x_i\leq \frac{S_1}{2}$$ and $$\frac{S_2}{2} - 1\leq \sum_{A}y_i\leq \frac{S_2}{2}$$ Can we continue somehow from here? By the CLT, we may bound the difference $S_1 - S_2 = \mathcal{O}(\sqrt{n})$ with high prob.