3

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

I tried to use the fact that $Pr[X>0] \leq \mathbb{E}[X] \ $ where $X$ is a non negative random variable. In particular I defined $X= \sum \limits_{j \in J} v_i - \sum \limits_{i \in I} v_i$. $\ \ $ But I am not sure about choosing $I,J$ in the right way. Any help on this would be much appreciate.

Clement C.
  • 67,323
sigma
  • 331
  • 1
    I have not solved the problem, but it seems like a pigeonhole principle problem. I'd try to count how many nonempty subsets like $I$ or $J$ there are (say $n$), how many possible values $\sum_{i\in I}v_i$ can have (say $m$). If $n>m$ there will be two different subsets with the same sum. Remove common elements and they will be disjoint. – ajotatxe Dec 30 '16 at 11:57
  • @ClementC. it's componentwise addition. Vector addition i.e $v_{i_1}+v_{i_2}=(x_{i_1}+x_{i_2},y_{i_1}+y_{i_2})$ ...from what i understood – sigma Jan 02 '17 at 13:42
  • Yes, I figured afterwards. (And deleted my comment accordingly) – Clement C. Jan 02 '17 at 13:43
  • 1
    @sigma I will not go through it (unless you are completely stuck), but look at the outline/hints from this (Exercise 7). – Clement C. Jan 02 '17 at 16:03

1 Answers1

5

I remind you, this book is totally systematic, a question from chapter 4 will be solved using the second moment method:

Define the random variables: $\epsilon_i=Ber(\frac1 2)$

Define a random variable $X=\sum_{i=1}^n\epsilon _i v_i$ and compute the mean of each coordinate: $$\mu_x =\frac1 2 \sum_{i\leq n}x_i\space,\space \mu_y =\frac1 2 \sum_{i\leq n}y_i$$ compute the variances: $$\sigma_x^2 =\frac1 4 \sum_{i\leq n}x^2_i\space,\space \sigma_y^2 =\frac1 4 \sum_{i\leq n}y^2_i$$ Both of the are bounded by $\frac{2^n}{40000}$. By Chebyshev, we get for any $\lambda$: $$Pr[|X_x − \mu_x| \geq \frac{λ · 2^{n/2}}{200}] ≤ λ^{−2}$$ $$Pr[|X_y − \mu_y| \geq \frac{λ · 2^{n/2}}{200}] ≤ λ^{−2}$$ The probability that both are false is at least $1 − 2λ^{ −2}$ . In the box delineated by these two inequalities there are at most $λ^ 2 2^ n/10000$ lattice points, so if every value of $ X $ occurs at most once, $$(1-2\lambda^{-2})2^n\leq \frac{\lambda^2 2^n}{10000}$$ since there are $2^n$ total values of $X$. Picking $λ = 2$ is enough to see a contradiction. Thus X takes some vector value twice, i.e. there exist distinct subsets $I, J \subseteq [1, n] $ for which $$\sum_Iv_i=\sum_Jv_j$$

Removing the intersection $I \cap J$ from both sets we still have equal sums, as desired.

Alon Yariv
  • 1,363