We have $a_1,a_2,...,a_n$, and $b_1,b_2,...,b_m$, all positive integers, with $a_i < m+1$ for all i, and $ b_j < n+1$ for all j. It is known that $m>n$, and that the sum of $b_1,..,b_m$ is strictly larger than the sum of $a_1, a_2,...,a_n$. Show that there is a subset of $a_1,..,a_n$ whose sum is equal to the sum of a subset of $b_1,...,b_m$.
I know this should be solvable using the pigeonhole principle on several sequences, but I just can't seem to find the sequence that works. I tried using sequences that excluded one of the values, but I think that since there are so many possible sequences, this just won't work, and using all possible sums seems pretty hard to do, since there can be multiple occurrences of the same number.
I would greatly appreciate any hints, thanks!
Arrange the numbers so that $a_1 \le a_2 \le \dotsb \le a_n$ and $ b_1 \le b_2 \le \dotsb \le b_m$, now consider the sums $P_k = a_1+ a_2+ ... + a_k$, $Q_l= b_1+b_2+ \dotsb b_l$, then call $t_k$ the number such that $Q_{t_k} \le P_k < Q_{t_k +1}$. Then, since $b_{t_k+1} \le n$, $P_k -Q_{t_k} < n$, and we have $n$ such differences, so by Pigeonhole theorem we have two equal differences.
WLOG, assume that $P_k -Q_{t_k} = P_m -Q_{t_m}$, then we have $P_k-P_m=Q_{t_k} - Q_{t_m}$ which means $ a_{m+1}+a_{m+2}+ \dotsb + a_k = b_{t_k +1} +b_{t_k +2} +\dotsb + b_{t_m}$.
Q.E.D $\square$