Question about the pigeonhole principle with sums of series

96 Views Asked by At

Suppose there are two series: {a1, a2, ..., an,..., a2n}, {b1, b2,..., bn, ..., b2n}, that answer on next condition: for every i, $1 \le i \le 2n : 1 \le ai \le n, 1 \le bi \le n$.

I need to prove that there are two sets of indexes $I,J \in [2n]$, that for them
$$\sum_{i \in I}^{} {ai} = \sum_{j \in J}^{} {bj}$$

1

There are 1 best solutions below

0
On BEST ANSWER

For $1\le k\le 2n$, let $A_k=\sum_{i=1}^k a_i$, $B_k=\sum_{i=1}^k b_i$. Then the sequences $A_k$ and $B_k$ are strictly increasing and we have $1\le A_k, B_k\le 2n^2$. Then the $4n^2$ numbers $A_k-B_l$ range from $1-2n^2$ to $2n^2-1$, which is just $4n^2-1$ different numbers so that some value must repeat. So say $A_k-B_l = A_{k'}-B_{l'}$ with $(k,l)\ne (k',l')$, where wlog $k\ge k'$. If $k=k'$, we conclude $B_l=B_{l'}$ and hence $l=l'$, contradiction. So $k>k'$ and $B_l-B_{l'}=A_k-A_{k'}>0$, hence $l>l'$ and we find $$\sum_{k'<i\le k}a_i=\sum_{l'<j\le l}b_j. $$