[ความรู้ยังอ่อนด้อย]

1. ตามที่ hint เลยนะครับ พิจารณาใน 2 คอลัมน์ใดๆ

ให้ $a_{i+1} \geq a_i$ และ $b_{i+1}\geq b_i $ โดยที่ i=1,2,...,m-1

สำหรับจำนวนเต็มบวก k ซึ่ง $1\leq k\leq m$

พิจารณา $a_k-b_k \leq a_i-b_k$ เมื่อ $m\geq i \geq k$

และ $a_k-b_k \leq a_k-b_j$ เมื่อ $k \geq j \geq 1$

ให้ $S=\left\{\,(a_i,b_j) | m\geq i \geq k และ k \geq j \geq 1\right\} $

สมมุติให้ สลับแถวเรียบร้อยแล้ว แล้วมีไม่มีคู่อันดับ $(a_i,b_j)$ ซึ่ง $(a_i,b_j)\in S$

จะได้ว่า $(a_i,b_j) \notin S$ สำหรับ $k \leq i\leq m$ และ $k+1 \leq j \leq m$

จะเห็นว่า จะต้องมีบาง $b_i$ ซึ่งใช้ร่วมกับ $a_x,a_y$ เป็นไปไม่ได้ (แต่ละ $a_i$ คู่กับ $b_j$ ได้เพียงตัวเดียว)


เพราะฉะนั้นไม่ว่าจะสลับอย่างไร ก็จะต้องมี $(x,y)$ ซึ่งทำให้ $a_i-b_j \leq a_x-b_y$ เสมอ

ปล. ถ้า $a_x-b_y < 0$ ทำคล้ายๆกัน แต่กลับข้างเครื่องหมายปะครับ?