Utiliser le principe du casier pour montrer qu'il existe des séquences avec la même somme

Question

Nous avons $a_1,a_2,...,a_n$, et $b_1,b_2,...,b_m$, tous les entiers positifs, avec $a_i < m+1$ pour tout ce que je, et $ b_j < n+1$pour tous j. Il est connu que$m>n$, et que la somme de $b_1,..,b_m$ est strictement plus grande que la somme de $a_1, a_2,...,a_n$. Montrez qu'il existe un sous-ensemble de$a_1,..,a_n$ dont la somme est égale à la somme d'un sous-ensemble de $b_1,...,b_m$.

Je sais que cela devrait être résolu en utilisant le principe du casier sur plusieurs séquences, mais je n'arrive tout simplement pas à trouver la séquence qui fonctionne. J'ai essayé d'utiliser des séquences qui excluaient l'une des valeurs, mais je pense que comme il y a tellement de séquences possibles, cela ne fonctionnera tout simplement pas, et utiliser toutes les sommes possibles semble assez difficile à faire, car il peut y avoir plusieurs occurrences de la même nombre.

J'apprécierais beaucoup tous les indices, merci!

Answer 1

Disposez les nombres de sorte que $a_1 \le a_2 \le \dotsb \le a_n$ et $ b_1 \le b_2 \le \dotsb \le b_m$, considérons maintenant les sommes $P_k = a_1+ a_2+ ... + a_k$, $Q_l= b_1+b_2+ \dotsb b_l$, puis appelez $t_k$ le nombre tel que $Q_{t_k} \le P_k < Q_{t_k +1}$. Puis, depuis$b_{t_k+1} \le n$, $P_k -Q_{t_k} < n$, et nous avons $n$ de telles différences, donc par le théorème de Pigeonhole nous avons deux différences égales.

WLOG, supposons que $P_k -Q_{t_k} = P_m -Q_{t_m}$, ensuite nous avons $P_k-P_m=Q_{t_k} - Q_{t_m}$ ce qui signifie $ a_{m+1}+a_{m+2}+ \dotsb + a_k = b_{t_k +1} +b_{t_k +2} +\dotsb + b_{t_m}$.

QED $\square$