I'm stuck on the following problem:
Seeing as it's from chapter 4 of "The Probabilistic Method", the proof has to be by the first or second-moment method. I've tried to model the problem probabilistically by defining the random variable $$X=\sum \epsilon_i v_i$$ with $\epsilon_ i $ iid. uniform rv taking values in $\{-1,0,1\}$, more precisely I was going off of $P(\epsilon_i=1)=P(\epsilon_i=-1)=p$ and hoping to prove $P(X=0)>P(\epsilon_i=0 \forall i)$. Unfortunately I've had no success for hours. I'm quite frustrated because the theory is not hard, but the exercises are very tricky... Do you know how to do this?
$\bf{Edit:}$
I think I have formulated a solution, although it feels a little messy. As suggested by MR_BD, and in a way which allows us to treat this case similarly to the classic distinct sume problem, set $$(X,Y)=\sum^n \epsilon_i v_i, \ \ \epsilon_i\in \{0,1\} \text{ taking value 1 with probability p}.$$ We suppose by contradiction that all combinations of the $v_i$ are distinct, which is equivalent to the (negation of) the problem. We have $E[X]=p\sum_i x_i, Var(X)=p(1-p)\sum_i x_i^2 \leq \frac{2^{n-2}}{10^4}$, and same for $Y$. Since by assumption all sums are distinct, and $p=0.5$, we have $$P(-t \leq X,Y\leq t)\leq (2t+1)^2\cdot 2^{-n} \forall 0<t\in \mathbb{R}.$$ The complement of this event satisfies (Chebyshev) $$P(|X|>t \cup |Y|>t)\leq P(|X|>t)+ P(|Y|>t)\leq \frac{Var(X)+Var(Y)}{t^2}\leq \frac{2^{n-1}}{10^4 t^2}.$$ Hence by assumption we must have $$1-\frac{(2t+1)^2}{2^n}\leq \frac{2^{n-1}}{10^4 t^2} \ \forall 0<t\in \mathbb{R}.$$ Reformulate this to $$f(t):= 4t^4+4t^3+(1-2^n)t^2+\frac{2^{2n-1}}{10^4}\geq 0 \forall t>0.$$ To show that this inequality does not in fact hold for all t, we split into two cases:
$n>4:$
Choose t s.t. $t^2=2^{n-4}$. Then $4 (t^4 +t^3)+t^2 \leq 9 t^4 \leq \frac{9 \cdot 2^{2n-1}}{2^7} $ Hence $$ f(t)\leq (\frac{1}{10^4}+\frac{9}{2^7})2^{2n-1}-\frac{1}{2^3}2^{2n-1}<0 $$, which is a contradiction.
If $n\leq 4$:
$$f(t)=t^2(4t^2+4t+1-2^n)+C$$ where $C=\frac{2^{2n-1}}{10^4}\leq \frac{128}{10^4}$. The quadratic term is minimized at $-0.5$, and $$f(-0.5)=-2^{n-1}+C<0, $$ which is a contradiction. Hence not all sums are distinct.
Let me give you two hints.
Notice that we can ignore the disjoint condition, since we can remove the intersection of $I,J$ from both of them. Imagine $I \subset [n]$ and $\sum_{i\in I}v_i = (X,Y)$. Then due to the bounds on $|x_i|,|y_i|$ we know that $|X|,|Y| < nB$. Therefore there are at most $4n^2B^2$ possible values for $\sum_{i\in I}v_i$ which is lower than $2^n$. Then a pigeonhole argument will solve the problem. For the second-moment part, you should prove that in most cases $|X|,|Y|$ are much smaller than $nB$ which means that the number of possibilities are much lower than $4n^2B^2$.