อ้างอิง:
ข้อความเดิมเขียนโดยคุณ ความรู้ยังอ่อนด้อย
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$ ทำคล้ายๆกัน แต่กลับข้างเครื่องหมายปะครับ?
|
วิธีการเขียนยังยุ่งๆอยู่ แต่วิธีทำได้แล้วครับ
idea ของข้อนี้คือ จะต้องมี $i \in \left\{ k,k+1,...,m \right\}$ และ $j \in \left\{ 1,2,...,k \right\}$ ซึ่ง $a_i$ อยู่แถวเดียวกับ $b_j$
ซึ่งการที่มาของข้อสรุปนี้ควรจะมาจากข้อความนี้
สังเกตว่า $a_k,a_{k+1},...,a_m$ ไม่สามารถจับคู่กับ $b_{k+1},...,b_m$ ได้ทั้งหมด
ซึ่งการเขียน $(a_i,b_j) \notin S$ สำหรับ $k \leq i\leq m$ และ $k+1 \leq j \leq m$ มันก็ยังผิดความหมายอยู่
ควรจะเขียนว่า สำหรับ $k \leq i\leq m$ ถ้า $(a_i,b_j) \notin S$ แล้ว $k+1 \leq j \leq m$ มากกว่า
ก็เรื่อง logic เล็กๆน้อยๆครับ
ส่วนกรณี $a_x-b_y < 0$ ไม่ต้องแยกกรณีครับเพราะใน proof นี้ไม่มีส่วนไหนที่ใช้ความที่ $a_x-b_y \ge 0$
อ้างอิง:
ข้อความเดิมเขียนโดยคุณ ความรู้ยังอ่อนด้อย
2.ให้ $S={a_1,a_2,...,a_n}$ เป็นลำดับของจำนวนเต็มบวก ซึ่ง $a_i \not= n+1$ และ
$a_1+a_2+...+a_n=2n$
จงแสดงว่า ถ้า n เป็นเลขคู่ แล้วจะมีบางสับเซตของ S ซึ่งผลบวกของสมาชิกทุกตัวเท่ากับ n
|
ข้อนี้ถือว่าอยู่ในระดับที่ยากครับ
ให้เป็น hint เหมือนเดิม
- induction (อะไรที่เท่ากันก็เอาไปไว้คนละข้าง)
- สังเกตว่าจะต้องมีตัวเลข $1$ อยู่เยอะมากเลยครับ
- เงื่อนไข $n$ เป็นเลขคู่ ให้มาเพื่อกำจัดกรณีเป็น $2$ หมดเฉยๆ สามารถตัดเงื่อนไขนี้ทิ้งและเปลี่ยนเงื่อนไขเป็น มีเลขที่มากกว่า $2$ แทน
ให้ $x_i$ แทนจำนวนของตัวเลข $i$
induction บนจำนวนของตัวเลขที่มากกว่า $1$