Need hint about with pigeonhole principle problem

Question

$a_i$ and $b_i$ are two sequences with $2n$ elements where $\forall i:\ 1\leq i\leq 2n\implies\ 1 \leq a_i , b_i \leq n$ . I need to show that there are two subsets of indexes $I,J\subset [2n]$ so that $\sum_{i\in I}a_i=\sum_{j\in J}b_j$ any ideas?

Answer 1

Ok I got a hint from the teaching assistant and solved it. It is going like this
Let $a_1,...,a_{2n}$ and $b_1,...,b_{2n}$ be integers between 1 and $n$. Now dentoe $s_i=\sum_{k=1}^{i}a_k $ and $t_j=\sum_{k=1}^jb_j$ for all $1\leq j,i\leq 2n$.
Counting the possible pairs $(i,j)$ gives us $4n^2$ possibilities - these are the pigeons.
For all $1\leq j,i\leq 2n$ , the sum $s_i+t_j$ is somewhere between 2 and $4n^2$ which gives us $4n^2-2$ possibilities - pigeonholes.
By the pigeonhole-principle we get that there must be two different pairs $(i,j),(k,m)$ so that $s_i+t_j=s_k+t_m$.
If $i=k$ then $s_k-s_i=0$ and by that we get that $t_j-t_m=0$ thus $j=m$ and the pairs aren't different. So without loss of generality we assume $k>i$ and as a result - $j>m$
We got that $s_k-s_i=t_j-t_m$
Notice that $s_k-s_i= \sum_{p=i+1}^k a_p$ and $t_j-t_m= \sum_{p=m+1}^j b_p$ and $$\sum_{p=i+1}^k a_p=\sum_{p=m+1}^j b_p$$ It will be great if you could confirm that it's correct

Answer 2

Try induction on $n$. The case $n=1$ is obvious. Assume your statement holds for $n$ and prove it for $n+1$. You have to distinguish between the cases when each of the sequences take the value $n+1$ and when they don't. There are four cases, one can be proved by the induction hypothesis, one has an obvious proof. The other two (which are essential just one case) are the difficult ones. I can give you another hint for that if you need one.

I don't see how to use the pigeon hole principle for a direct proof.