8
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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$ $\endgroup$ – d_e Jul 25 '16 at 10:24
  • $\begingroup$ What does mean exactly the notation in "a sequence of $(a_i)_{i=1}^{2n}$ " ? $\endgroup$ – user354674 Jul 25 '16 at 10:41
  • $\begingroup$ What kind of numbers are $a_i$ and $b_i$? $\endgroup$ – Piquito Jul 26 '16 at 19:32
  • $\begingroup$ " 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. $\endgroup$ – fleablood Aug 6 '16 at 0:37
  • $\begingroup$ can you please answer the questions raised in the comments please? where did you get this question from? is this the complete question? $\endgroup$ – Arjang Aug 9 '16 at 21:59
4
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.