# N.Alon, J.Spencer Probabilistic methods problem ch. $4$ problem $5$

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.

#### Solutions Collecting From Web of "N.Alon, J.Spencer Probabilistic methods problem ch. $4$ problem $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.