หลักการรังนกพิราบ

kanji · #1 10 มิถุนายน 2006, 20:34

ให้ $A=\{x_1,x_2,\ldots,x_{12}\}$ โดยที่ $x_i$ เป็นจำนวนเต็ม
จงพิสูจน์ว่ามีสับเซตของ $A$ ที่ไม่เป็นเซตว่าง และผลรวมของสมาชิกถูกหารด้วย 12 ลงตัว

passer-by · #2 11 มิถุนายน 2006, 02:53

พิจารณา

$ S_1= x_1 $
$ S_i = x_1+x_2+\cdots +x_i \quad 2 \leq i \leq 12 $

กรณีที่ 1 : ถ้ามีบาง S_i ที่หารด้วย 12 ลงตัว การพิสูจน์สิ้นสุด

กรณีที่ 2 : 12 หาร S_iแล้วเหลือเศษ ทุก index i

เนื่องจากมีเศษได้ 11 ค่า แต่มี S ได้ 12 แบบ

จากหลักรังนกพิราบ จะมี $ S_m , S_n $ ซึ่งหารด้วย 12 แล้วเหลือเศษเท่ากัน

ถ้า m < n ดังนั้น $ 12 \mid S_n - S_m = x_{m+1}+x_{m+2}+\cdots +x_n $

และได้ $ \{x_{m+1},x_{m+2},\cdots ,x_n \} $ คือ subset ที่ต้องการ

kanji · #3 14 มิถุนายน 2006, 12:38

มีลำดับที่มี $n^2+1$ พจน์ที่แต่ละพจน์เป็นจำนวนจริงที่ต่างกัน จงแสดงว่า มีลำดับย่อย
ที่มี $n+1$ พจน์ที่เป็นลำดับเพิ่ม หรือมีลำดับย่อยที่มี $n+1$ พจน์ที่เป็นลำดับลด

nongtum · #4 14 มิถุนายน 2006, 17:13

นิยาม $f:\{i|i=1,...,n^2+1\}\to \mathbb{N},\ i\mapsto f(i)$
($f(i)$ แทนความยาวของลำดับเพิ่มที่ยาวที่สุดที่เริ่มที่เทอมที่ $i$ ของลำดับนี้)
หากมี $i$ ที่ทำให้ $f(i)\ge n+1$ จะเห็นว่าข้อความนี้เป็นจริง มิเช่นนั้นจะได้ว่า
สำหรับทุกๆ $i$: $f(i)<n+1$ ซึ่งจะทำให้มี $s\in\{1,...,n\};f(i)=s$ สำหรับ $\frac{n^2}{n}+1=n+1$ จำนวน
ให้ $a_{j_i},\ i=1,\dots,s+1$ เป็นลำดับเพิ่มที่เริ่มจาก $a_{j_1}$
หาก $a_{j_i}<a_{j_{i+1}}$ จะได้ว่า $|a_{j_i}|=s+1\ \wedge\ (a_{j_i})$ เป็นลำดับเพิ่ม เกิดข้อขัดแย้งกับ $f(j_i)=s$
ดังนั้น $(a_{j_i})$ จึงเป็นลำดับเพิ่มที่ $|f(j_i)|=n+1$

หากสนใจหรืออ่านแล้วไม่เข้าใจ ลองค้นหาทฤษฎีบทของ Erdös-szekeres ดูนะครับ

passer-by · #5 14 มิถุนายน 2006, 22:19

อีกวิธีนึงนะครับ

สมมติ $a_1 < a_2,\cdots < a_{n^2+1} $

ให้ $i_n$ และ $ d_n$ แทนความยาวลำดับเพิ่มและลำดับลด ที่เริ่มที่พจน์ $ a_n $ ตามลำดับ

By contradiction

ดังนั้น $ (i_n,d_n) $ จะมีอย่างมาก (n)(n) แบบ

จากหลักรังนกพิราบ เนื่องจากมี $n^2+1$ เทอม ดังนั้น ต้องมีอย่างน้อย 2 เทอมที่มีคู่อันดับดังกล่าวเหมือนกัน ซึ่งเป็นไปไม่ได้ (ลองคิดดูนะครับ ว่าทำไม)