creatio ex nihilo

ศล
Location :
กรุงเทพ Thailand

[Profile ทั้งหมด]

ให้ทิปเจ้าของ Blog [?]
ฝากข้อความหลังไมค์
Rss Feed
Smember
ผู้ติดตามบล็อก : 85 คน [?]




Group Blog
 
All Blogs
 
Friends' blogs
[Add ศล's blog to your web]
Links
 

 
kürschak 2490

โดย ศล



โจทย์ข้อนี้เป็นคำถามในรายการแข่งขัน Kürschak พ.ศ. 2490 และการแข่งขัน Putnam พ.ศ. 2496 จงพิสูจน์ว่าในคน 6 คนจะต้องมี 3 คนที่รู้จักกันหรือ 3 คนที่ไม่รู้จักกันเสมอ

“นำลูกแก้ว n+1 ลูก ใส่กล่อง n กล่อง จะมีกล่องอย่างน้อย 1 กล่องที่มีลูกแก้วมากกว่า 1 ลูก” จำข้อเท็จจริงนี้ให้ดีนะครับ เพราะมันมีประโยชน์มากในการพิสูจน์ปัญหาการจัดหมู่ในทฤษฎีจำนวน เมื่อขยายขอบเขตให้กว้างขึ้น “มีลูกแก้ว m ลูก นำใส่กล่อง n กล่อง เมื่อ m>n จะมีอย่างน้อย 1 กล่องที่มีลูกแก้วมากกว่า 1 ลูก” หลักการอันนี้เรียกว่า Dirichlet’s Box Principle หรือ Pigeonhole Principle ตามชื่อนักคณิตศาสตร์ชาวเยอรมันผู้ยิ่งใหญ่แห่งศตวรรษที่ 19 Johann Peter Gustav Lejeune Dirichlet


ถ้าเราวาดกราฟเชื่อมระหว่างซาสึเกะคุง 6 คนตามรูปที่ 1 เรียกว่า complete graph คือกราฟที่แต่ละจุดเชื่อมกับทุกจุดที่เหลือ จากนั้นลงสีบนเส้นกราฟ มีสีให้เลือก 2 สี คือ สีคนรู้จักกัน (แดง) กับสีคนไม่รู้จักกัน (ดำ) แต่ละซาสึเกะมีเส้น 5 เส้นเปรียบเสมือนเป็นลูกแก้ว 5 ลูก มีสี 2 สีเปรียบเสมือนเป็นกล่อง 2 กล่อง เราสามารถสรุปได้ว่ามี 1 กล่องที่ต้องมีลูกแก้วอย่างน้อย 3 ลูก แต่ละคนมีเส้นเชื่อมที่เป็นสีเดียวกันอย่างน้อย 3 เส้น ต่อมาให้เลือกซาสึเกะ 1 คนพร้อมด้วยเส้นกราฟสีเดียวกัน 3 เส้น สมมติว่าสีแดง แต่ละเส้นจะเชื่อมไปยังคนอีก 1 คน รวม 3 เส้นเป็น 3 คน คือ A B C ตามรูปที่ 2 ถ้าด้านของสามเหลี่ยม ABC มีด้านใดด้านหนึ่งเป็นสีแดง เราย่อมสามารถสร้างสามเหลี่ยมสีแดงทั้ง 3 ด้านได้ (คนรู้จักกัน 3 คน) แต่ถ้าไม่มีด้านใดของ ABC เป็นสีแดงเลย เราก็สามารถสร้างสามเหลี่ยมสีดำทั้ง 3 ด้านได้ (คนไม่รู้จักกันทั้ง 3 คน)



ลองขยายแนวคิดโจทย์ข้อนี้ขึ้นอีกระดับ นักวิทยาศาสตร์ 17 คน พูดคุยแลกเปลี่ยนงานวิจัยซึ่งกันและกัน หัวข้องานวิจัยมีทั้งหมด 3 หัวข้อ ระหว่างนักวิทยาศาสตร์ 2 คนใดๆ พูดคุยงานวิจัยกันเพียงหัวข้อเดียว จงพิสูจน์ว่ามีกลุ่มนักวิทยาศาสตร์ 3 คน ที่พูดคุยเรื่องเดียวกัน

คิดเลียนแบบข้อที่แล้วได้เลยครับ นักวิทยาศาสตร์ 17 คน แต่ละคนคุยกับคนอื่น 16 คน แทนด้วยลูกแก้ว 16 ลูก หัวข้องานวิจัย 3 เรื่อง แทนด้วยกล่อง ดังนั้นมีอย่างน้อย 1 กล่องที่มีลูกแก้วมากกว่า 5 ลูก หรือมีหัวข้อวิจัยอย่างน้อย 1 เรื่องที่มีนักวิทยาศาสตร์คนหนึ่งๆ พูดคุยกับคนอื่นๆ อีก 6 คน เราเลือกนักวิทยาศาสตร์ 1 คน กับเรื่องวิจัย (สีแดง) ที่นักวิทยาศาสตร์คนนั้นคุยกับคนอื่น 6 คน ตั้งชื่อทั้ง 6 ว่า V1 V2 … V6 ตามรูปที่ 3 ถ้าในกลุ่มนักวิทยาศาสตร์ 6 คนนั้นมีใครที่คุยเรื่องวิจัยสีแดง เราสามารถสร้างสามเหลี่ยมสีแดงได้ แต่ถ้าไม่มีใครคุยเรื่องสีแดงกันเลย หมายความว่าในกลุ่ม 6 คนนั้นคุยกันด้วยเรื่องอีก 2 สีที่เหลือ เราก็สามารถสร้างกลุ่ม 3 คนของสีใดสีหนึ่งในสองสีที่เหลือได้โดยวิธีตามข้อ 8 โจทย์ข้อนี้คือกรณีที่เพิ่มกล่องอีก 1 กล่องจากโจทย์ข้อ 8 นั่นแหละครับ



ถ้าเราเรียกกรณีแบบข้อแรกว่า กรณี n=2 เพราะมีกล่อง 2 กล่องหรือใช้สี 2 สี และเรียกกรณีแบบข้อที่สองว่า กรณี n=3 เพราะมีกล่อง 3 กล่องหรือใช้สี 3 สี กรณี n=2 จะเห็นได้ว่าเราใช้คนหรือจุด 6 จุด ส่วนกรณี n=3 เราใช้ 17 จุด อยากรู้ว่ากรณี n=4 เราจะใช้กี่จุด สามารถย้อนรอยวิธีการคิดกลับไปได้ว่าเมื่อเราดึงจุด (หรือคน) ออกมา 1 จุด แล้วจุดนั้นเชื่อมกับกราฟกรณี n=3 คือ 17 จุด หมายความว่าจำนวน 17 คือจำนวนลูกแก้วน้อยที่สุดที่เราจะพบในกล่องอย่างน้อย 1 กล่อง (จาก 4 กล่อง) ดังนั้นต้องมีลูกแก้วขั้นต่ำรวม (16x4) +1 = 65 ลูก หรือมีจุด 66 จุด ทำนองเดียวกัน ถ้า n=5 หรือ 5 กล่อง มี 327 จุด, n=6 ต้องมี 1958 จุด กำหนด Pn แทนจำนวนจุดที่ n ใดๆ (P1 = 3, P2 = 6, P3 = 17, P4 = 66, …) เราสามารถเขียนความสัมพันธ์รูปทั่วไป



ค่าในวงเล็บปีกา […] เปรียบเทียบได้กับจำนวนลูกแก้วกรณีมี n+1 กล่อง

ที่ n ใด ๆ ถ้ากำหนดให้มีจำนวนลูกแก้วเท่ากับ Qn ดังนั้น Pn = Qn+1 หรือ Qn = Pn-1 เราได้สมการ



หรือ




ที่แสดงมานี้ เราสามารถพิสูจน์ได้ว่ามี 3 เหลี่ยมสีเดียวกันอย่างน้อย 1 รูปของ complete graph ที่มี Pn จุด เมื่อเส้นเชื่อมแต่ละจุดเลือกลงสีใดสีหนึ่งจากจำนวน n สีได้เสมอ









Create Date : 30 พฤศจิกายน 2550
Last Update : 3 ธันวาคม 2550 15:51:05 น. 0 comments
Counter : 1260 Pageviews.

ชื่อ : * blog นี้ comment ได้เฉพาะสมาชิก
Comment :
  *ส่วน comment ไม่สามารถใช้ javascript และ style sheet
 
 Pantip.com | PantipMarket.com | Pantown.com | © 2004 BlogGang.com allrights reserved.