# Prove there exists two sub-sets of indices $I,J\subseteq [2n]$ such that $\sum_{i\in I}a_i=\sum_{j\in J}b_j$

Let $$(a_i)_{i=1}^{2n}, (b_i)_{i=1}^{2n}$$ be two sequences of size $$2n$$ of integers such that for every $$1\leq i \leq 2n$$: $$1\leq a_i \leq n, 1\leq b_i \leq n$$.

Prove there exists two nonempty sub-sets of indices $$I,J\subseteq [2n]$$ such that $$\sum_{i\in I}a_i=\sum_{j\in J}b_j$$.

I tried to work with pigeonhole principle, but got stuck.

Any help appreciated.

For each $$1\leq i\leq 2n$$ define $$x_i=a_1+...+a_i$$ and $$y_i=b_1+...+b_i$$. We know that $$x_1 and $$y_1, since we are adding positive terms to the partial sums. Then define:

$$X=\{x_1,...,x_{2n}\},Y=\{y_1,...,y_{2n}\}$$

Note that the number of elements in $$X\times Y$$ is $$4n^2$$. On the other hand, for each $$1\leq i\leq 2n$$ we have $$1\leq x_i,y_i\leq 2n^2$$. Hence, for each $$i,j$$ we have the following inequality:

$$-2n^2+1\leq x_i-y_j\leq 2n^2-1$$

So the number of options for $$x_i-y_j$$ is at most $$4n^2-1$$, which is less than the number of elements in $$X\times Y$$. From the pigeonhole principle we conclude that there are two different elements $$(x_i,y_j),(x_m,y_k)\in X\times Y$$ such that $$x_i-y_j=x_m-y_k$$. Without loss of generality we may assume that $$i>m$$, and then we get $$x_i-x_m=y_j-y_k$$. And this is exactly what you need because $$x_i-x_m=\sum_{t=m+1}^i a_t$$ and $$y_j-y_k=\sum_{t=k+1}^j b_t$$. (if we had $$i we would look at the equality $$x_m-x_i=y_k-y_j$$ instead. Note that the case $$i=m$$ is impossible because it would imply $$j=k$$ which would be a contradiction to $$(x_i,y_j),(x_m,y_k)$$ being different elements)

• so you're actually proving that the index sets are made from consecutive numbers, and not just a random choice of index right? Commented Jul 29, 2019 at 19:58
• Yes, I proved something a bit stronger.
– Mark
Commented Jul 29, 2019 at 20:03
• Oh, I forgot to write that we assume without loss of generality that $i>m$, which also implies $j>k$. Otherwise we just look at the equality $x_m-x_i=y_k-y_j$ instead.
– Mark
Commented Jul 29, 2019 at 20:26
• Yes. I noticed it myself, but worked alone to prove why it's not really a "problem", maybe you should add it to your answer. Commented Jul 29, 2019 at 20:37