การใช้หลักการ pigeonhole เพื่อแสดงว่ามีลำดับที่มีผลรวมเดียวกัน

Question

เรามี $a_1,a_2,...,a_n$และ $b_1,b_2,...,b_m$จำนวนเต็มบวกทั้งหมดด้วย $a_i < m+1$ สำหรับฉันและ $ b_j < n+1$สำหรับ j. เป็นที่ทราบกันดีว่า$m>n$และนั่นคือผลรวมของ $b_1,..,b_m$ มีขนาดใหญ่กว่าผลรวมของ $a_1, a_2,...,a_n$. แสดงว่ามีส่วนย่อยของ$a_1,..,a_n$ ซึ่งผลรวมเท่ากับผลรวมของชุดย่อยของ $b_1,...,b_m$.

ฉันรู้ว่าสิ่งนี้ควรแก้ไขได้โดยใช้หลักการของรูนกพิราบในหลาย ๆ ลำดับ แต่ดูเหมือนจะหาลำดับที่ใช้งานไม่ได้ ฉันลองใช้ลำดับที่ยกเว้นค่าใดค่าหนึ่ง แต่ฉันคิดว่าเนื่องจากมีลำดับที่เป็นไปได้มากมายสิ่งนี้จึงใช้ไม่ได้ผลและการใช้ผลรวมที่เป็นไปได้ทั้งหมดดูเหมือนจะทำได้ยากเนื่องจากอาจมีหลายเหตุการณ์ที่เหมือนกัน จำนวน.

ฉันจะขอบคุณมากคำแนะนำใด ๆ ขอบคุณ!

Answer 1

จัดเรียงตัวเลขเพื่อให้ $a_1 \le a_2 \le \dotsb \le a_n$ และ $ b_1 \le b_2 \le \dotsb \le b_m$ตอนนี้พิจารณาผลรวม $P_k = a_1+ a_2+ ... + a_k$, $Q_l= b_1+b_2+ \dotsb b_l$แล้วโทร $t_k$ จำนวนดังกล่าว $Q_{t_k} \le P_k < Q_{t_k +1}$. ตั้งแต่นั้นเป็นต้นมา$b_{t_k+1} \le n$, $P_k -Q_{t_k} < n$และเรามี $n$ ความแตกต่างดังกล่าวดังนั้นโดยทฤษฎีบท Pigeonhole เราจึงมีความแตกต่างที่เท่ากันสองประการ

WLOG สมมติว่า $P_k -Q_{t_k} = P_m -Q_{t_m}$แล้วเราก็มี $P_k-P_m=Q_{t_k} - Q_{t_m}$ ซึ่งหมายความว่า $ a_{m+1}+a_{m+2}+ \dotsb + a_k = b_{t_k +1} +b_{t_k +2} +\dotsb + b_{t_m}$.

QED $\square$