Aynı toplamda dizilerin olduğunu göstermek için güvercin deliği prensibini kullanma

Question

Sahibiz $a_1,a_2,...,a_n$, ve $b_1,b_2,...,b_m$, tüm pozitif tam sayılar, $a_i < m+1$ her şey için ve $ b_j < n+1$tüm j. Biliniyor ki$m>n$ve toplamı $b_1,..,b_m$ toplamından kesinlikle daha büyüktür $a_1, a_2,...,a_n$. Bir alt kümesi olduğunu gösterin$a_1,..,a_n$ toplamı, bir alt kümesinin toplamına eşittir $b_1,...,b_m$.

Bunun güvercin deliği prensibini kullanarak birkaç sekans üzerinde çözülebilir olması gerektiğini biliyorum, ancak işe yarayan sekansı bulamıyorum. Değerlerden birini dışlayan dizileri kullanmayı denedim, ancak bence çok fazla olası dizi olduğundan, bu işe yaramayacak ve tüm olası toplamları kullanmak oldukça zor görünüyor, çünkü aynı şeyin birden fazla oluşumu olabilir. numara.

Herhangi bir ipucu için çok minnettar olurum, teşekkürler!

Answer 1

Numaraları öyle düzenleyin ki $a_1 \le a_2 \le \dotsb \le a_n$ ve $ b_1 \le b_2 \le \dotsb \le b_m$şimdi toplamları düşünün $P_k = a_1+ a_2+ ... + a_k$, $Q_l= b_1+b_2+ \dotsb b_l$, sonra ara $t_k$ sayı öyle ki $Q_{t_k} \le P_k < Q_{t_k +1}$. O zamandan beri$b_{t_k+1} \le n$, $P_k -Q_{t_k} < n$ve bizde $n$ Bu tür farklılıklar, dolayısıyla Pigeonhole teoremine göre iki eşit farkımız var.

WLOG, varsayalım ki $P_k -Q_{t_k} = P_m -Q_{t_m}$o zaman bizde $P_k-P_m=Q_{t_k} - Q_{t_m}$ bunun anlamı $ a_{m+1}+a_{m+2}+ \dotsb + a_k = b_{t_k +1} +b_{t_k +2} +\dotsb + b_{t_m}$.

QED $\square$