Usando el principio del casillero para mostrar que hay secuencias con la misma suma

Dec 28 2020

Tenemos $a_1,a_2,...,a_n$y $b_1,b_2,...,b_m$, todos enteros positivos, con $a_i < m+1$ por todo yo, y $ b_j < n+1$para todos j. Se sabe que$m>n$, y que la suma de $b_1,..,b_m$ es estrictamente mayor que la suma de $a_1, a_2,...,a_n$. Muestre que hay un subconjunto de$a_1,..,a_n$ cuya suma es igual a la suma de un subconjunto de $b_1,...,b_m$.

Sé que esto debería poder resolverse usando el principio de casillero en varias secuencias, pero parece que no puedo encontrar la secuencia que funcione. Intenté usar secuencias que excluían uno de los valores, pero creo que, dado que hay tantas secuencias posibles, esto simplemente no funcionará, y usar todas las sumas posibles parece bastante difícil de hacer, ya que puede haber múltiples apariciones del mismo número.

Agradecería mucho cualquier sugerencia, ¡gracias!

Respuestas

2 NikolaTolzsek Dec 31 2020 at 21:18

Organiza los números para que $a_1 \le a_2 \le \dotsb \le a_n$ y $ b_1 \le b_2 \le \dotsb \le b_m$, ahora considera las sumas $P_k = a_1+ a_2+ ... + a_k$, $Q_l= b_1+b_2+ \dotsb b_l$, luego llame $t_k$ el número tal que $Q_{t_k} \le P_k < Q_{t_k +1}$. Entonces, desde$b_{t_k+1} \le n$, $P_k -Q_{t_k} < n$, y tenemos $n$ tales diferencias, por lo que por el teorema de Pigeonhole tenemos dos diferencias iguales.

WLOG, suponga que $P_k -Q_{t_k} = P_m -Q_{t_m}$, entonces tenemos $P_k-P_m=Q_{t_k} - Q_{t_m}$ lo 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$