3
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ +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? $\endgroup$ – antkam Apr 23 at 1:25
  • 1
    $\begingroup$ 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$. $\endgroup$ – Slugger Apr 23 at 12:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.