หลักรังนกพิราบ (จากหนังสือ สอวน.)

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

1. ให้ A เป็นเมทริกซ์ขนาด $m\times n$ และกำหนดให้ $d_i$ คือผลต่างของค่ามากสุดและค่าน้อยสุดในแถว i
$d=max{d_1,d_2,...,d_m}$ และเมื่อ เรียงเลขในแต่ละหลักจากมากไปน้อยโดยค่ามากสุดอยู่บนสุด จงแสดงว่า
ผลต่างระหว่างค่าสูงสุดกับค่าต่ำสุดของแต่แถว ของเมทริกซ์ที่สลับแล้วมีค่าไม่เกิน d

2. มีทีมฟุตบอตทั้งหมด 28 ทีม แข่งแบบพบกันหมดโดยทีมที่ชนะจะได้ 2 คะแนน เสมอ 1 แพ้ 0 เมื่อการแข่งขันสิ้นสุดแล้วพบว่ามากกว่า 75% ของการแข่งขันมีผลเสมอ จงแสดงว่าต้องมี 2 ทีมที่คะแนนรวมเท่ากัน

[Thgx0312555]

กำลังรออยู่ว่าจะมีคนมาตอบไหม
ในเมื่อผ่านมาหนึ่งวันแล้ว เดี๋ยว hint ให้ก่อน

1. ลองพิจารณาแค่ 2 คอลัมน์ใดๆ
สมมติจำนวนที่อยู่ใน 2 คอลัมน์นั้นเป็น $a_1 \ge a_2 \ge \cdots \ge a_n$ และ $b_1 \ge b_2 \ge \cdots \ge b_n$

2. ลองเปลี่ยนเป็นชนะได้ 1 คะแนน เสมอได้ 0 คะแนน แพ้ได้ -1 คะแนนดูครับ

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

#2 ขอ hint เพิ่มหน่อยครับ ยังมองไม่ออกครับ

[Thgx0312555]

แล้วก็ลองคิดดูว่าถ้าสมมติขัดแย้ง ทุกทีมคะแนนต่างกันหมดจะเกิดอะไรขึ้นครับ

อีกนิด

แล้วการที่จะเกิดผลลัพธ์เช่นนั้นได้(ทุกทีมคะแนนต่างหมด) ต้องเกิดการแพ้/ชนะอย่างน้อยกี่ครั้ง

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

ไม่แน่ใจตรวจให้หน่อยครับรู้สึกแปลกๆ

2.สมมุติให้ ทุกทีมคะแนนต่างกันหมด

ให้ $x_i$ คือคะแนนของทีมที่ i โดย $x_i\not= x_j $ เมื่อ $i\not= j$ และ $-27 \leq x_i \leq 27$

และจะมีอย่างน้อย 14 ทีมที่มีคะแนนเป็นบวก /ลบ เหมือนกัน

โดยไม่เสียนัยให้ทีมที่มีคะแนนเป็นบวกเหมือนกัน 14 ทีม จึงได้

$\sum _{ x_i >0} x_i \geq 1+2+3+...+14= 105$

เพราะฉะนั้นจะต้องมีการชนะเกิดขึ้นอย่างน้อย 105 ครั้ง

แต่จำนวนการแพ้/ชนะ ที่เกิดขึ้นได้มากสุดคือ $\binom{28}{2} /4= 94.5 $ หรือ 94 ครั้ง

เกิดข้อขัดแย้ง เพราะฉะนั้นต้องมี 2 ทีมที่มีคะแนนเท่ากัน


ปล. ขอข้อ 1 ด้วยครับยังไม่ได่เหมือนกัน ( มารื้อฟื้นความรู้ ทำไม่ค่อยได้เลย ����)

[Thgx0312555]

เป็น hint ที่หนักเหมือนกันแต่ยังไม่ขนาดเฉลยครับ

hint

เพื่อความง่ายเราจะดูแค่สองคอลัมน์และดูตารางที่สลับแล้ว
สมมติว่าตารางเป็นแบบนี้ (แต่ละคอลัมน์เรียงจากมากไปน้อย)
$\matrix{x_1 & y_1 \\ x_2 & y_2 \\ x_3 & y_3 \\ x_4 & y_4 \\ x_5 & y_5} $

ทีนี้ไม่ว่าจะสลับมั่วๆอย่างไร เช่น
$\matrix{x_1 & y_3 \\ x_2 & y_4 \\ x_3 & y_1 \\ x_4 & y_5 \\ x_5 & y_2} $

ต้องพิสูจน์ว่า

ค่า max ของผลต่างก็จะเพิ่มขึ้น

ปล. solution ข้อสองถูกแล้ว และเป็นวิธีเขียนที่สะอาดมากเลย

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

#6 ยังไม่ออกเลยครับ 5555

ขอฝากโจทย์เพิ่ม

1.มีนักเรียน 49 คนทำข้อสอบ 3 ข้อ โดยแต่ละข้อมีคะแนนตั้งแต่ 0-7 จงแสดงว่า

มีนักเรียนอย่างน้อย 2 คนซึ่งหนึ่งในนั้นได้คะแนนในแต่ละข้อไม่น้อยกว่าอีกคนเสมอ

2.ให้ $S={a_1,a_2,...,a_n}$ เป็นลำดับของจำนวนเต็มบวก ซึ่ง $a_n \not= n+1$ และ

$a_1+a_2+...+a_n=2n$

จงแสดงว่า ถ้า n เป็นเลขคู่ แล้วจะมีบางสับเซตของ S ซึ่งผลบวกของสมาชิกทุกตัวเท่ากับ n

[Thgx0312555]

Hint สุดท้ายแล้วครับ
สำหรับทุก $i$ จะมี $(x,y)$ ซึ่ง $a_i-b_i \le a_x - b_y$ โดยที่ $a_x$ อยู่แถวเดียวกับ $b_y$
ถ้ายังไม่ได้อีก 2-3 วันเดี๋ยวมาเฉลยครับ

ข้อข้างล่างคุ้นๆเหมือนเคยเฉลยอยู่ครั้งนึงครับ

[Thgx0312555]

ข้อข้างล่างข้อ 1 เคยเฉลยไว้ครั้งนึงในบอร์ดนี้แล้ว
แต่จะยังไม่ลงลิงค์ให้ เดี๋ยวลง hint ให้ก่อน

hint

ถ้าให้คะแนนของนักเรียนแต่ละคนแทนด้วย $(a,b,c)$
สังเกตว่าไม่มีนักเรียนสองคนใดมี $(b,c)$ เท่ากันครับ

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

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$ ทำคล้ายๆกัน แต่กลับข้างเครื่องหมายปะครับ?

[Thgx0312555]

ข้อความเดิมเขียนโดยคุณ ความรู้ยังอ่อนด้อย

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$ แทน

hint เพิ่ม 1

ให้ $x_i$ แทนจำนวนของตัวเลข $i$

hint เพิ่ม 2

induction บนจำนวนของตัวเลขที่มากกว่า $1$

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

ผมก็รู้สึกว่าเขียนงงๆ แต่ไม่รู้จะเขียนออกมายังไงเดี๋ยวจะไปแก้ครับ ส่วนอีกข้อลองตรวจให้หน่อยครับ

ให้ $a_i \leq a_{i+1}$ โดยที่ i=1,2,...,n-1
พิจารณา $\sum_{i=1}^{n} a_i \geq n-1+a_n$

เพราะฉะนั้นจะได้ $a_n \leq n $ และ $a_1=1$ สำหรับจำนวนนับ n $(a_n \not= n+1)$

พิจารณา $\sum_{i=1}^{n-1} a_i \geq \dfrac{n}{2}+\dfrac{na_{\frac{n}{2}+1}}{2}$ จะได้ว่า $a_{\frac{n}{2}+1} \leq 3$

ถ้ามี i ที่ $i \leq n/2$ ซึ่ง $a_i \geq 3$ จะทำให้ $\sum_{i=1}^{n} a_i > 2n$

เพราะฉะนั้น $a_i=1,2$ สำหรับ $i \leq n/2$

ให้ $p=a_1+a_2+...+a_{n/2}$ และให้ $P=\left\{\,a_1,a_2,...,a_{\frac{n}{2}}\right\} $

จะเห็นว่า $\dfrac{n}{2}\geq p \leq n-1$ พิสูจน์ได้ไม่ยากว่ามีบางสับเซตของ P , called Q, ซึ่ง $\sum_{i \in Q} a_i =k $ สำหรับทุก $k \leq p$ ( พิสูจน์จาก k สามารเขียนในรูป 2j หรือ 2j+1)

ให้ r เป็นจำนวนเต็มบวกซึ่ง $\sum_{i=\frac{n}{2}+1}^r <n$ แต่ $\sum_{i=\frac{n}{2}+1}^{r+1} a_i >n$

ให้ $\sum_{i=\frac{n}{2}+1}^r =n-s$

กรณี 1: $s \leq p$ จะได้

$\sum_{i \in Q} a_i + \sum_{i=\frac{n}{2}+1}^{r}=n$

กรณี 2: $s > p$

จาก$\sum_{i =\frac{n}{2}+1}^{r+1} >n $ ทำให้ $a_{r+1}>s>p\geq \dfrac{n}{2}$

เพราะฉันนั้น $a_i \geq \dfrac{n}{2}+2$ สำหรับ $i\geq r+1$

สำหรับ n>5 พิจารณา

$a_1+a_2+...+a_n= p+\sum_{i=\frac{n}{2}+1}^{r+1}+a_{r+2}+...+a_n > \dfrac{n}{2}+n+\dfrac{n}{2}+2>2n $

เหลือแค่กรณี n=2,n=4 (นั่งแทนค่า )

[Thgx0312555]

solution ยังผิดอยู่แต่สามารถแก้ได้ครับ
บรรทัดสุดท้ายถ้า $r+1=n$ ก็จะผิดครับ เช่นในกรณี $1,1,1,...,1,n+1$

เนื่องจากว่าดูเหมือนจะไม่มีใครใช้วิธีที่ hint ให้ไป ขอเฉลยวิธีผมเลยนะครับ แต่ยังไม่ต้องดูก็ได้

solution outline

induction บนจำนวนของจำนวนเต็มที่มากกว่า 1 ในลำดับดังกล่าว

ให้ $P(k)$ แทนข้อความ ให้ $a_1,a_2,...,a_n$ เป็นลำดับของจำนวนเต็มบวกซึ่ง $a_1+a_2+\cdots+a_n=2n$ และมีจำนวนที่มีค่ามากกว่า $1$ อยู่ $k$ ตัว
โดยมีเงื่อนไขคือมีจำนวนที่มากกว่า $2$ อยู่อย่างน้อย $1$ ตัว (ตัดเงื่อนไข $n$ เป็นเลขคู่ออก)

Case $k=1$ จะได้จำนวนที่มากกว่า $1$ นั้นคือ $n+1$ ขัดแย้งกับโจทย์
จึงเพียงพอที่จะพิสูจน์ว่า $P(k)$ เป็นจริงสำหรับ $k \ge 2$

Base Step $k=2$ เหมือน step induction
Base Step $k=3$ สมมติจำนวนที่มากกว่า $1$ คือ $l,m,p$ จะต้องมีเลข $1$ อยู่ $l+m+p-6$ ตัว
ขั้นนี้เป็นขั้นที่ใช้เงื่อนไขมีจำนวนมากกว่า $2$ จึงสมมติ $l \ge 3$ และเลือก $S=\left\{ \overbrace{1,1,...,1}^{l-3},m,p \right\}$

Inductive Step สมมติ $P(k-2)$ ใช้ได้ จะพิสูจน์ $P(k)$ ใช้ได้
สมมติ $l,m \ge 2$ (เลือก $l,m$ ให้เหลือเลขที่เกิน $2$ อยู่) จะมีเลข $1$ อยู่อย่างน้อย $l+m-4$ ตัว
แบ่งเป็นสองกลุ่มที่ผลบวกเท่ากันได้ดังนี้
$\left\{ \overbrace{1,1,...,1}^{m-2},l \right\}$, $\left\{ \overbrace{1,1,...,1}^{l-2},m \right\}$
ตัดออกและใช้ induction

Case เป็น $2$ หมด trivial, เฉพาะเคสนี้ที่ใช้เงื่อนไข $n$ เป็นคู่

ส่วนที่ hint ให้ใช้ $x_i$ แทนจำนวนของตัวเลข $i$ จะได้ความสัมพันธ์นี้ครับ ซึ่งบอกจำนวนเลข $1$ ที่ต้องมี
$x_1=x_3+2x_4+3x_5+\cdots+(n-2)x_n$

[Thamma]

ขอบคุณ คุณThgx0312555 ที่ให้คำแนะนำนะคะ

พิสูจน์แบบนี้ ใช้ได้ไหมคะ


ให้ $T = \{a_1, a_2, a_1 + a_2, a_1 + a_2 + a_3, ..., a_1+a_2+...+a_n \}$ ซึ่งมี $n+1$ สมาชิก

โดยหลักรังนกพิราบ จะมีอย่างน้อย 2 สมาชิก $A, B \in T$ ซึ่ง $A \equiv B (\bmod n)$


กรณีที่ 1 : $\mid A \mid = \mid B \mid$

$A = a_1 , B = a_2$

1.1 $a_1 = a_2$ ที่สอดคล้องกับเงื่อนไขโจทย์ มี 2 กรณี คือ

$ a_1 = a_2 = 1$ และ $a_n \not= n+1$ เป็นไปได้หลายแบบ เช่น

$ S = \{\underbrace{1, 1, ..., 1}_{\text{$n-2\;$ ตัว}},2, n \} $ และ subset ที่เลือกมามี 1 อยู่ $n-2$ ตัว และมี 2 อยู่ 1 ตัว

$ a_1 = a_2 = 2$ เป็นไปได้แบบเดียวคือ

$ S = \{\underbrace{2, 2, ..., 2}_{\text{$n\; $ตัว }}\} \;$โดย $n$ ต้องเป็นเลขคู่ และ subset ที่เลือกมามี 2 อยู่ $\frac{n}{2}$ ตัว

1.2 $a_1 \not= a_2$

$a_2 < n+1 $ มิฉะนั้น จะมีบาง $a_i = 0 $

$a_2 - a_1 < n+1-a_1 \leq n$

$a_2 - a_1 < n$

ดังนั้น $a_2 \not\equiv a_1 (\bmod n)$ ซึ่งขัดแย้งกับ $A \equiv B (\bmod n)$


กรณีที่ 2 : $\mid A \mid \not= \mid B \mid$

$A-B$ จะมีผลบวกของสมาชิกทุกตัว หารด้วย $n$ ลงตัว

เนื่องจาก $a_1+a_2+...+a_n=2n$ ดังนั้น $A-B$ จะมีผลบวกของสมาชิกทุกตัว เท่ากับ $ n$

จึงสรุปได้ว่า จะมีบางสับเซตของ $S$ ซึ่งผลบวกของสมาชิกทุกตัวเท่ากับ $n $


ไม่ทราบว่ากรณี $ a_1 = a_2 = 1$ ต้องหารูปทั่วไปของกรณีที่ใช้ได้ไหมคะ หรือแค่ยกตัวอย่างก็พอแล้ว

[Thgx0312555]

ข้อความเดิมเขียนโดยคุณ Thamma

1.1 $a_1 = a_2$ ที่สอดคล้องกับเงื่อนไขโจทย์ มี 2 กรณี คือ

$ a_1 = a_2 = 1$ และ $a_n \not= n+1$ เป็นไปได้หลายแบบ เช่น

$ S = \{\underbrace{1, 1, ..., 1}_{\text{$n-2\;$ ตัว}},2, n \} $ และ subset ที่เลือกมามี 1 อยู่ $n-2$ ตัว และมี 2 อยู่ 1 ตัว

$ a_1 = a_2 = 2$ เป็นไปได้แบบเดียวคือ

$ S = \{\underbrace{2, 2, ..., 2}_{\text{$n\; $ตัว }}\} \;$โดย $n$ ต้องเป็นเลขคู่ และ subset ที่เลือกมามี 2 อยู่ $\frac{n}{2}$ ตัว

solution นี้เป็น solution ที่สวยงามมากครับ แต่ยังถือว่ายังทำไม่จบ ตรงสีแดงต้องพิสูจน์ว่าทุกแบบแบ่งได้ด้วยครับ
และต้องบอกด้วยว่าทำไมถึงแบ่งได้แค่ 2 แบบนี้

(จริงๆตรงนี้สามารถแก้ได้ไม่ยาก ลองสังเกตว่าเราไม่จำเป็นต้องเลือกคู่ $a_1,a_2$ มาก็ได้)