Menggunakan prinsip pigeonhole untuk menunjukkan bahwa ada urutan dengan jumlah yang sama

Question

Kita punya $a_1,a_2,...,a_n$, dan $b_1,b_2,...,b_m$, semua bilangan bulat positif, dengan $a_i < m+1$ untuk semua saya, dan $ b_j < n+1$untuk semua j. Diketahui itu$m>n$, dan itu adalah jumlah dari $b_1,..,b_m$ lebih besar dari jumlah $a_1, a_2,...,a_n$. Tunjukkan bahwa ada subset dari$a_1,..,a_n$ yang jumlahnya sama dengan jumlah bagian dari $b_1,...,b_m$.

Saya tahu ini harus diselesaikan menggunakan prinsip lubang merpati pada beberapa urutan, tetapi saya tidak bisa menemukan urutan yang berhasil. Saya mencoba menggunakan urutan yang mengecualikan salah satu nilai, tetapi saya pikir karena ada begitu banyak kemungkinan urutan, ini tidak akan berhasil, dan menggunakan semua kemungkinan jumlah tampaknya cukup sulit dilakukan, karena mungkin ada beberapa kejadian yang sama jumlah.

Saya akan sangat menghargai petunjuk apapun, terima kasih!

Answer 1

Susun angka-angkanya sehingga $a_1 \le a_2 \le \dotsb \le a_n$ dan $ b_1 \le b_2 \le \dotsb \le b_m$, sekarang pertimbangkan jumlahnya $P_k = a_1+ a_2+ ... + a_k$, $Q_l= b_1+b_2+ \dotsb b_l$, lalu telepon $t_k$ jumlahnya sedemikian rupa $Q_{t_k} \le P_k < Q_{t_k +1}$. Lalu, sejak$b_{t_k+1} \le n$, $P_k -Q_{t_k} < n$, dan kita mempunyai $n$ perbedaan tersebut, sehingga dengan Teorema Pigeonhole kita memiliki dua perbedaan yang sama.

WLOG, asumsikan itu $P_k -Q_{t_k} = P_m -Q_{t_m}$, maka kita punya $P_k-P_m=Q_{t_k} - Q_{t_m}$ yang berarti $ a_{m+1}+a_{m+2}+ \dotsb + a_k = b_{t_k +1} +b_{t_k +2} +\dotsb + b_{t_m}$.

QED $\square$