Usando o princípio do escaninho para mostrar que existem sequências com a mesma soma

Question

Nós temos $a_1,a_2,...,a_n$e $b_1,b_2,...,b_m$, todos os inteiros positivos, com $a_i < m+1$ para todos eu, e $ b_j < n+1$para todos j. Sabe-se que$m>n$, e que a soma de $b_1,..,b_m$ é estritamente maior do que a soma de $a_1, a_2,...,a_n$. Mostre que existe um subconjunto de$a_1,..,a_n$ cuja soma é igual à soma de um subconjunto de $b_1,...,b_m$.

Sei que isso pode ser resolvido usando o princípio da classificação em várias sequências, mas simplesmente não consigo encontrar a sequência que funciona. Tentei usar sequências que excluíam um dos valores, mas acho que, como existem tantas sequências possíveis, isso simplesmente não vai funcionar, e usar todas as somas possíveis parece muito difícil de fazer, uma vez que pode haver várias ocorrências do mesmo número.

Eu apreciaria muito qualquer dica, obrigado!

Answer 1

Organize os números para que $a_1 \le a_2 \le \dotsb \le a_n$ e $ b_1 \le b_2 \le \dotsb \le b_m$, agora considere as somas $P_k = a_1+ a_2+ ... + a_k$, $Q_l= b_1+b_2+ \dotsb b_l$, então ligue $t_k$ o número tal que $Q_{t_k} \le P_k < Q_{t_k +1}$. Então, desde$b_{t_k+1} \le n$, $P_k -Q_{t_k} < n$, e nós temos $n$ tais diferenças, então pelo teorema Pigeonhole temos duas diferenças iguais.

WLOG, assuma que $P_k -Q_{t_k} = P_m -Q_{t_m}$, então nós temos $P_k-P_m=Q_{t_k} - Q_{t_m}$ que significa $ a_{m+1}+a_{m+2}+ \dotsb + a_k = b_{t_k +1} +b_{t_k +2} +\dotsb + b_{t_m}$.

QED $\square$