3
$\begingroup$

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 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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.