0

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

Uria Mor
  • 961
  • 1
    I think there should be some condition on the $b_i$'s. – Pgatti Dec 09 '14 at 09:56
  • you are right just a moment – Uria Mor Dec 09 '14 at 09:57
  • What are your ideas? What did you try? – Pgatti Dec 09 '14 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. – Pgatti Dec 09 '14 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 – Uria Mor Dec 09 '14 at 10:37

2 Answers2

1

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.

KDuck
  • 742
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

Uria Mor
  • 961