Используя принцип ячеек, чтобы показать, что существуют последовательности с одинаковой суммой

Question

У нас есть $a_1,a_2,...,a_n$, и $b_1,b_2,...,b_m$, все положительные целые числа, с $a_i < m+1$ для всех я и $ b_j < n+1$для всех j. Известно, что$m>n$, и что сумма $b_1,..,b_m$ строго больше, чем сумма $a_1, a_2,...,a_n$. Покажите, что существует подмножество$a_1,..,a_n$ сумма которых равна сумме подмножества $b_1,...,b_m$.

Я знаю, что это должно быть решено с использованием принципа ячейки для нескольких последовательностей, но я просто не могу найти последовательность, которая работает. Я пробовал использовать последовательности, исключающие одно из значений, но я думаю, что, поскольку существует так много возможных последовательностей, это просто не сработает, и использование всех возможных сумм кажется довольно сложным, поскольку может быть несколько вхождений одного и того же количество.

Буду очень признателен за любые подсказки, спасибо!

Answer 1

Расставьте числа так, чтобы $a_1 \le a_2 \le \dotsb \le a_n$ и $ b_1 \le b_2 \le \dotsb \le b_m$, теперь рассмотрим суммы $P_k = a_1+ a_2+ ... + a_k$, $Q_l= b_1+b_2+ \dotsb b_l$, затем позвони $t_k$ число такое, что $Q_{t_k} \le P_k < Q_{t_k +1}$. Тогда, поскольку$b_{t_k+1} \le n$, $P_k -Q_{t_k} < n$, и у нас есть $n$ такие различия, поэтому по теореме Пидженхола у нас есть две равные разности.

WLOG, предположим, что $P_k -Q_{t_k} = P_m -Q_{t_m}$, то имеем $P_k-P_m=Q_{t_k} - Q_{t_m}$ что значит $ a_{m+1}+a_{m+2}+ \dotsb + a_k = b_{t_k +1} +b_{t_k +2} +\dotsb + b_{t_m}$.

QED $\square$