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.
 A: 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
    \begin{equation}
    \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}.
\end{equation}
    Then, by Chebyshev's inequality we have that
    \begin{equation}
    \mathbb{P}\left( |X-\mu_X| \geq  \lambda  \frac{2^{n/2}}{200} \right) \leq \frac{1}{\lambda^2} 
\end{equation}
    so that by taking complements and setting $\lambda = 2$ we obtain
    \begin{equation}
    \mathbb{P}\left(|X-\mu_X| <    \frac{2^{n/2}}{100}\right)\geq \frac34.
\end{equation}
    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
    \begin{equation}
    \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.
\end{equation}
    As $I'$ and $J'$ are disjoint, we are done. 
