9

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.

35T41
  • 3,377
  • I think it is possible to show with induction on the length $n$. you will have to show that with $2n$ elements of ${1..n}$ you can reach sum of $(n+1)k$ where $k$ is anything between $1$ and 2$n$ – d_e Jul 25 '16 at 10:24
  • What does mean exactly the notation in "a sequence of $(a_i)_{i=1}^{2n}$ " ? –  Jul 25 '16 at 10:41
  • What kind of numbers are $a_i$ and $b_i$? – Piquito Jul 26 '16 at 19:32
  • " There are obviously much more subsets that possible sums (22n−1 compared to 2n2) but it doesn't really help." On the contarty! That is exactly why the statement must be true. If there are more subsets then sums, two subsets must have the same sum as then can't all have different sums. – fleablood Aug 06 '16 at 00:37
  • can you please answer the questions raised in the comments please? where did you get this question from? is this the complete question? – jimjim Aug 09 '16 at 21:59
  • All the numbers are integers. This is a question from a test I had and it is the complete question. – 35T41 Aug 10 '16 at 07:58

1 Answers1

4

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

awkward
  • 14,736