The pigeonhole principle - how to solve questions like that?

415 Views Asked by At

We have two sequences , $(a_i)_{i=1}^{2n}$ and $(b_i)_{i=1}^{2n}$ such that $1\leq a_i, b_i\leq n$ for every $i$.

Show that there are two sets of indexes $I, J \subseteq \left \{ 1,2, ... 2n \right \}$ such what $\sum_{i\in I}a_i=\sum_{j\in J}b_j$.

Well, the question didn't say anything about those sets being empty but I believe that's not what they meant. I don't know that to do with questions like these. There are obviously much more subsets that possible sums ($2^{2n}-1$ compared to $2n^2$) but it doesn't really help.

I'd be glad to hear ideas, hints or solutions.

1

There are 1 best solutions below

0
On BEST ANSWER

I am assuming that $a_i$ and $b_i$ denote integers, although that is not stated in the OP.

Define $S_j = \sum_{i=1}^j a_i$ and $T_k = \sum_{i=1}^k b_i$, so $1 \leq S_j \leq 2n^2$ and $1 \leq T_k \leq 2n^2$ for $1 \leq j \leq 2n$ and $1 \leq k \leq 2n$. Notice that the $S_j$'s are all distinct, and so are the $T_k$'s. We have $|S_j - T_k| \leq 2n^2-1$, so there are $4n^2-1$ possible values of $S_j-T_k$ for $1 \leq j \leq 2n$ and $1 \leq k \leq 2n$.

Consider the $4n^2$ pairs $(S_j, T_k)$ for $1 \leq j \leq 2n$ and $1 \leq k \leq 2n$. Since there are more pairs than there are possible values of $S_j-T_k$, by the pigeonhole principle there must be at least two distinct pairs, say $(S_j,T_k)$ and $(S_l, T_m)$, which map to the same difference, i.e. $$S_j- T_k = S_l - T_m$$ We may as well assume, without loss of generality, that $j > l$. Then $$S_j - S_l = T_k - T_m$$ implies $$\sum_{i=l+1}^j a_i = \sum_{i=m+1}^k b_i$$