# Disjoint Sets with the Same Sum

I'm reading through a combinatorics book and I got stuck on this problem.

Let $v_1=(x_1,y_1),..., v_n=(x_n,y_n)$ be $n$ two dimensional vectors such that each $x_i$ and $y_i$ is an integer whose absolute value does not exceed $\frac{2^{n/2}}{100\sqrt{n}}$. Prove there are two disjoint sets $I,J$ in $\{1,2,...,n\}$ such that $$\sum_{i\in I}v_i=\sum_{j\in J}v_j.$$

I am not sure how to prove this. I was thinking that it has something to do with distinct sums: A set $w_i,,,w_k$ of positive integers has distinct sums if all sums $$\sum_{i\in S}w_i,$$ $S\subset \{1,...,k\}$ are distinct, but I am not sure if this is even the right direction since the thing we want to prove would mean we don't have distinct sums. Any help would be greatly appreciated.

Let $$\{\alpha_i\}_{i=1}^n$$ be a sequence of random variables each picked uniformly and independently from $$\{0,1\}$$. Then define $$X = \sum_{i=1}^n \alpha_i x_i$$ and $$Y = \sum_{i=1}^n \alpha_i y_i$$. Ler $$\mu_X :=\mathbb{E} X$$ and $$\mu_Y:=\mathbb{E} Y$$. By the independence of the $$\alpha_i$$ we have that $$$$\operatorname{Var}(X) = \sum\limits_{i=1}^n \mathbb{P}(\alpha_i \neq 0)^2 x_i^2 \leq \frac{1}{4}\cdot \frac{ 2^{n}}{100^2}.$$$$ Then, by Chebyshev's inequality we have that $$$$\mathbb{P}\left( |X-\mu_X| \geq \lambda \frac{2^{n/2}}{200} \right) \leq \frac{1}{\lambda^2}$$$$ so that by taking complements and setting $$\lambda = 2$$ we obtain $$$$\mathbb{P}\left(|X-\mu_X| < \frac{2^{n/2}}{100}\right)\geq \frac34.$$$$ A completely equivalent computation shows the above bound with $$X$$ replaced by $$Y$$. Now, two events $$A$$ and $$B$$ with $$\mathbb{P}(A) \geq 3/4$$ and $$\mathbb{P}(B) \geq 3/4$$ must satisfy $$\mathbb{P}(A \cap B) \geq 1/2$$. This follows from $$1 \geq \mathbb{P}(A \cup B) = \mathbb{P}(A) + \mathbb{P}(B) - \mathbb{P}(A\cap B)$$. That is, for at least half of the $$2^n$$ possible outcomes of $$\alpha_1,\ldots, \alpha_n$$ we have that $$(X,Y)$$ takes its value somewhere in a $$2\cdot 2^{n/2}/100$$ by $$2\cdot 2^{n/2}/100$$ rectangle $$\mathcal{R}$$ centered around $$(\mu_X,\mu_Y)$$.
Thus, as $$2^{n-1} > 2^n/2500$$, we conclude by the pigeonhole principle that there are two index sets $$I,J \subset \{1,\ldots, n\}$$ such that $$\sum_{i\in I}v_i = \sum_{j\in J}v_j$$. These $$I$$ and $$J$$ need not be distinct of course, so define $$I' = I \setminus (I\cap J)$$ and $$J' = J \setminus (I\cap J)$$. For these sets we have $$$$\sum\limits_{i\in I'} v_i = \sum\limits_{i\in I}v_i -\sum\limits_{i \in I\cap J} v_i = \sum\limits_{j\in J}v_i - \sum\limits_{j\in I\cap J} v_j = \sum\limits_{j\in J'}v_j.$$$$ As $$I'$$ and $$J'$$ are disjoint, we are done.
• +1 very nice use of Variance. question: so the $100$ in the denominator could have been a much smaller number? i.e. the upper bound on $|x_i|, |y_i|$ could have been much looser? – antkam Apr 23 at 1:25
• I believe so indeed. I guess they do this to show that in the asymptotic sense we may apply the physicists rule that $1=\pi =10=100$. – Slugger Apr 23 at 12:32