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<x_2<...<x_{2n}$ and $y_1<y_2<...<y_{2n}$, 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<m$ 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)
