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$

149 Views Asked by At

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.