การนำไปประยุกต์ใช้
ต่อไปจะนำหลักการรังนกพิราบ
(
The Pigeonhole principle ) ไปประยุกต์ใช้กับปัญหาหนึ่งซึ่งเกี่ยวข้องกับการให้สีกราฟ
โดยในที่นี้จะเป็นการพิสูจน์กรณีหนึ่งของการเกิด monochromatic triangle ( กรณี 6 จุด ) ซึ่งเป็นการให้สีเส้นเชื่อม
( edge ) ที่เชื่อมกันระหว่างจุด 2 จุด
ปัญหา
วาดจุด 6 จุด ลงบนระนาบโดยทุกเส้นเชื่อม (
edge ) ระหว่างจุด 2 จุดจะถูกระบายสีเส้นเป็นสีแดง
หรือสีฟ้าอย่างใดอย่างหนึ่ง จงพิสูจน์ว่าจะเกิด monochromatic triangle
หมายเหตุ ;
Monochromatic triangle คือสามเหลี่ยมที่มีด้านหรือเส้นเชื่อมมีสีเป็นสีเดียวกันทั้ง
3 เส้นและการเกิด monochromatic triangle จะเกิดขึ้นได้ต้องมีจำนวนจุดอย่างน้อย 6 จุด
ถ้ามีจำนวนจุดน้อยกว่า 6 จุดจะไม่เกิด
แนวคิดและการพิสูจน์
ปัญหานี้ดูผิวเผินแล้วดูเหมือนไม่น่าจะมีส่วนเกี่ยวข้องกับหลักการรังนกพิราบ
(
The Pigeonhole principle ) ได้เลย แต่ในความเป็นจริงแล้วมันมีความเกี่ยวข้องกันอยู่
ซึ่งสามารถนำมาช่วยในการพิสูจน์ปัญหานี้ได้ จะเริ่มด้วยการพิจารณาว่า
อะไรคือสิ่งที่แทนจำนวนรังนกและอะไรแทนจำนวนนกพิราบ
ซึ่งเริ่มต้นเรายังไม่สามารถระบุลงไปชัดเจนได้ว่า จะใช้อะไรแทนดี แต่อย่างไรก็ตาม
เราก็ยังพอที่จะคิดหรือรู้ได้ว่า
สามเหลี่ยมจะต้องถูกสร้างขึ้นมาจากเส้นเชื่อมระหว่าจุดแน่นอน
เนื่องจากจำนวนเส้นเชื่อมทั้งหมดระหว่างจุด 2 จุด ( มีจำนวนจุดอยู่ทั้งหมด 6 จุด ) เท่ากับ
15 เส้นเชื่อม
ไม่มีความคิดเห็น:
แสดงความคิดเห็น