# Using the pigeonhole principle to show that there are sequences with the same sum

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!

• "I know this should be solvable using the pigeonhole principle" Do you actually know this? Commented Dec 30, 2020 at 14:50
• @mathworker21 It was from a sequence pigeonhole principle problem set, so that should be the case Commented Dec 30, 2020 at 14:54
• You may want to give a look to this thread math.stackexchange.com/questions/496113/… Commented Dec 30, 2020 at 18:14
• @Suzet Thanks! Should I just delete this question then? Commented Dec 31, 2020 at 9:31

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$$
• Consider $A=\{1,1,1,...,1,2\}$ and $B=\{n,...,n\}$ - and make sure to include $P_0$ & $Q_0$ :-) Commented Jan 6, 2021 at 1:01