Need hint about with pigeonhole principle problem

$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?

• I think there should be some condition on the $b_i$'s. Commented Dec 9, 2014 at 9:56
• you are right just a moment Commented Dec 9, 2014 at 9:57
• What are your ideas? What did you try? Commented Dec 9, 2014 at 10:07
• You should really say "subsets" instead of "subgroups". Anyway I do not understand how you obtained $2n^2$ as the number of possible partial sums. Commented Dec 9, 2014 at 10:29
• I tried counting the possibilities for partial sum which is 2n2 and denote it as pigeonholes. And the pigeons will be the possibilities to pick a subgset of [2n] which concludes to the astronomic number of 4n so it doesn't seem right Commented Dec 9, 2014 at 10:37

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.

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

• It is indeed correct. And after some time — I forget how long — the system will allow you to accept it. Commented Dec 9, 2014 at 22:58
• Thank you once again @BrianM.Scott Commented Dec 10, 2014 at 11:45
• You're welcome; I'm delighted that you were able to solve it. Commented Dec 10, 2014 at 12:16
• Well it wasn't all me. As I said - our teaching assistant helped us with hints. Commented Dec 10, 2014 at 12:55