The Pigeonhole Principle

Tony · #1 13 มีนาคม 2005, 08:56

ผมไม่ได้เข้ามาเว็บบอร์ดหลายเดือนแล้ว เพราะว่ามัวแต่เข้าค่ายอยู่เลยไม่ว่าง
แต่ตอนนี้กำลังดูเนื้อหาเรื่องหลักการรังนกพิราบอยู่ เลยมีโจทย์มาถามครับ

1. ในกลุ่มคน 6 คนโดยที่คนแต่ละคู่รู้จักกันหรือไม่รู้จักกัน จงแสดงว่ามี 3 คนที่รู้จักกันหรือมี 3 คนที่ไม่รู้จักกัน

2. นายดนัยต้องการซ้อมเทนนิสก่อนการแข่งขัน ซึ่งมีเวลาซ้อม 30 วัน โดยที่นายดนัยวางแผนการซ้อมว่าต้องเล่นวันละอย่างน้อย 1 เกมส์แต่ทั้งหมดรวมไม่เกิน 45 เกมส์ จงแสดงว่าไม่ว่านายดนัยวางแผนการซ้อมอย่างไรก็ตามต้องมีช่วงวันที่ติดต่อกันที่นายดนัยเล่นได้ 14 เกมส์พอดี

3. เลือกจำนวนเต็ม 201 จำนวน มาจาก {1,2,3,...,400} จงแสดงว่าในบรรดาจำนวนเต็ม 201 จำนวนที่เลือกมานั้นจะต้องมีจำนวนเต็มสองจำนวนซึ่งจำนวนหนึ่งหารอีกจำนวนหนึ่งลงตัว

R-Tummykung de Lamar · #2 13 มีนาคม 2005, 13:22

ข้อ 1 เรื่องกราฟ ปะ
จะพิสูจน์แย้งนะครับ (ใช่เรียกแบบนี้รึเปล่า)
สมมติว่าแต่ละคนมีชื่อว่า A B C D E และ F
แต่ละคู่จะมีเส้นเชื่อมต่อกัน ถ้าเป็นเส้นทึบแสดงว่ารู้จักกัน ถ้าเป็นเส้นประ แสดงว่าไม่รู้จักกันนะ

A ต้องลาก 5 เส้นแล้ว อย่างน้อย ต้องเส้นทึบ มากกว่าหรือเท่ากับ 3 หรือ เส้นประ มากกว่าหรือเท่ากับ 3
ดูกรณีแรกก่อนละกัน อย่างน้อยที่สุด คือมีเส้นทึบ สามเส้น สมมติลากไป A---B A---C และ A---D
เพื่อไม่ให้เกิดสามคนที่รู้จักกัน ก็ต้องลากเส้นประ B- - -C B- - -D C- - -D
แต่จะเกิด B- - -C- - -D ที่เป็นกลุ่มสามคนที่ไม่รู้จักกัน
อีกกรณีก็คล้ายๆกัน

ลองวาดรูปประกอบดูครับ

nooonuii · #3 13 มีนาคม 2005, 21:21

ข้อ 1 เป็นปัญหาที่เรียกโดยทั่วไปว่าปัญหา Ramsey Number ครับ เป็นปัญหาที่ยากและมีพัฒนาการน้อยมากเมื่อเทียบกับงานวิจัยในเรื่องอื่นๆ แต่ปัญหาข้อนี้มีวิธีคิดได้หลายแบบครับ อาจจะใช้ Pigeonhole Principle(หรือ Dirichlet Drawer Principle) หรืออาจจะเป็นเรื่องของ Complete bipartite graph ก็ได้ครับ ไม่แน่ใจว่าจะใช้พวก Coloring ได้รึปล่าว แต่คิดว่าน่าจะใช้ได้นะ

gon · #4 14 มีนาคม 2005, 23:24

ข้อ 3 ก่อนนะครับ.

ปัญหาข้อนี้ใช้ Trick ที่ว่า จำนวนเต็มใด n ใดๆ จะสามารถเขียนได้ในรูปของ 2^p ดq เสมอ
เมื่อ p ฮ {0, 1, 2, ... } หรือ จำนวนเต็มที่มากกว่าหรือเท่ากับศูนย์
และ q ฮ {..., -3, 1, 1, 3, ...} หรือ จำนวนเต็มคี่ใด ๆ
เช่น 12 = 2² ด 3
24 = 2³ ด 3
27 = 2⁰ ด 27

เหตุผลง่าย ๆ ก็คือ ถ้า n เป็นจำนวนคี่ ก็สามารถเขียนได้ว่า n = 2⁰ ด n แต่ถ้า n เป็นจำนวนเต็มคู่ เราก็จะนำ 2 ไปหารเรื่อย ๆ จนกว่าจะได้จะจำนวนคี่

ดังนั้น q ทั้งหมดที่เป็นไปได้จะมีตั้งแต่ 1, 3, 5, ... , 399 รวมทั้งหมด 200 จำนวน
สมมติให้มีรังนกทั้งหมด 200 รัง โดยที่แต่ละรัง แทนจำนวนคี่ตั้งแต่ 1, 3, 5, ... , 399

ดังนั้น ถ้าเราหยิบจำนวนเต็มใด ๆ 201 จำนวน จากเซต {1, 2, 3, ... , 400} แล้วเขียนจำนวนดังกล่าวในรูป ของ 2^p ด q เราก็จะได้ว่า จะต้องมีอย่างน้อย 2 จำนวน ที่มีค่า q เท่ากัน (คือเป็นจำนวนเต็มคี่ตัวเดียวกัน) แต่ p ไม่เท่ากัน (เพราะถ้าทั้ง q และ p เท่ากัน แสดงว่าเป็นจำนวนเดียวกัน) สมมติว่าเป็น 2^a ด q และ 2^b ด q จะเห็นได้เมื่อนำจำนวนทั้งสองมาหารกัน จำนวนที่มีเลขชี้นกำลังของ 2 มากกว่า ก็จะหาร จำนวนที่มีเลขชี้กำลังของ 2 น้อยกว่าได้ลงตัว เสมอ

gon · #5 14 มีนาคม 2005, 23:28

ข้อ 1 version P.P.

ในข้อนี้จะแบ่งปัญหาออกเป็น 2 แบบ แบบแรก มีอยู่ 3 คนที่รู้จักกัน และ แบบที่สองมีอยู่ 3 คน ที่ไม่รู้จักกันเลย

สมมติให้ x เป็นคน ๆ หนึ่งในกลุ่มดังกล่าว ดังนั้นจะเหลือคนอยู่ 5 คน ซึ่งแบ่งออกเป็น 2 ประเภท คือ ประเภทที่รู้จักกับ x กับ ประเภทไม่รู้จักกับ x

ในที่นี้มีรังอยู่ 2 รัง คือ รังที่รู้จักกับ x กับ รังที่ไม่รู้จักกับ x และ มีนกอยู่ 5 ตัว
โดยหลักรังนกพิราบ จะได้ว่า จะมีนกอย่างน้อย 3 ตัวที่อยู่รังเดียวกัน

กรณีที่ 1 : นกอย่างน้อย 3 ตัวที่ว่าอยู่รังที่รู้จักกับ x
นกกลุ่มนี้ก็จะแบ่งออกเป็น 2 กรณีใหญ่ ๆ คือ กรณีที่มีนก 2 ตัวใด ๆ รู้จักกัน กับ ไม่มีนก 2 ตัวใดเลยที่รู้จักกัน

กรณีที่ 1.1 ถ้ามีนก 2 ตัวใด ๆ ที่รู้จักกัน เมื่อรวมกับนก x ก็จะรู้จักกันรวมกันเป็น 3 ตัวพอดี ซึ่งเป็นแบบแรก
กรณีที่ 1.2 ถ้าไม่มีนก 2 ตัวใดเลยที่รู้จักกัน ก็จะไปเข้าแบบหลัง คือ ไม่มีนกที่รู้จักกันเลย 3 ตัว ก็จะเป็นแบบหลัง

กรณีที่ 2 นกอย่างน้อย 3 ตัว อยู่รังที่ไม่รู้จักกับ x
นกกลุ่มนี้ก็จะแบ่งออกเป็น 2 กรณีใหญ่ ๆ คือ กรณีที่มีนก 2 ตัวใด ๆ ไม่รู้จักกัน กับ กรณีที่ นกทุกตัวรู้จักกันหมด

กรณีที่ 2.1 ถ้ามีนก 2 ตัวใด ๆ ที่ไม่รู้จักกัน เมื่อรวมกับ x ด้วย ก็จะไม่รู้จักกันรวม 3 ตัวพอดี ซึ่งเป็นแบบหลัง
กรณีที่ 2.2 ถ้านกทุกตัวรู้จักกันหมด ก็จะเป็นแบบแรก

Tony · #6 20 มีนาคม 2005, 08:15

ก็พอจะทำได้แล้วนะครับ ทั้งหมดเลย
ขอบคุณสำหรับแนวคิดนะครับ

gon · #7 20 มีนาคม 2005, 09:51

ข้อ 2 น้อง Tony ทำอย่างไงครับ. อธิบายแนวคิดให้ฟังหน่อยสิ.

Tony · #8 08 เมษายน 2005, 13:19

ให้ a_i = จำนวนทั้งหมดจนถึงวันที่ i
จะได้ 1ฃ a₁,a₂,a₃,...,a₃₀ฃ45
พบว่าเป็นลำบเพิ่มอย่างแท้จริง a_iนa_j
a₁+4,a₂+14,a₃+14,...,a₃₀+14ฃ59
1ฃ a₁,a₂,a₃,...,a₃₀,a₁+4,a₂+14,a₃+14,...,a₃₀+14ฃ59
แสดงว่ามีอยู่ a_i=a_j+14
a_i-14=a_j
นั่นคือ จำนวนวันตั้งแต่วันที่ j ถึงวันที่ i มี 14 เกม

gon · #9 08 เมษายน 2005, 20:57

ท่าทางน้อง Tony น่าจะบรรลุุเรื่องนี้แล้ว. ขอบคุณที่มาแสดงวิธีคิดนะครับ.

warut · #10 08 เมษายน 2005, 22:38

ว้าว...ที่แท้ข้อ 2. ก็ทำอย่างนี้นี่เอง รอดูเฉลยมานานแล้วครับ ขอบคุณ คุณ Tony หลายๆเด้อ