หลักการรังนกพิราบ (The
pigeonhole principle)
หลักการรังนกพิราบ (The pigeonhole principle)
เป็นการใช้ความจริงในธรรมชาติซึ่งเกี่ยวกับนกพิราบและรังของนกพิราบ โดยกล่าวว่า “ถ้ามีจำนวนนกพิราบมากกว่ารังนกพิราบแล้ว
จะต้องมีอย่างน้อยหนึ่งรัง ที่ทีจำนวนนกพิราบอย่างน้องสองตัว” และหลักการรังนกพิราบนี้
มีชื่อเรียกอีกอย่างหนึ่งว่า “Dirichlet drawer principle”
เนื่องจากหลักการนี้ถูกใช้ครั้งแรกโดยนักคณิตศาสตร์ชื่อ P.G.L. Dirichlet (1805-1859) ซึ่งจากหลักการนี้
สามารถนำไปประยุกต์ใช้ในการแก้ปัญหา แหละคาดการเหตุการณ์การต่างๆ
ได้ซึ่งจะนำเสนอต่อไปนี้
|
ทฤษฎีบทที่ 1
หลักการรังนกพิราบ (The pigeonhole
principle)ให้
K
€ I⁺ถ้ามีนกพิราบอย่างน้อย
K+ 1 ตัว บินเข้ารัง K รัง แล้วมีรังอย่างน้อย 1 รัง
ที่มีนกพิราบอย่างน้อย 2 ตัว
|
พิสูจน์ทฤษฎีบทที่ 1
จะใช้วิธีการขัดแย้ง (by
contradiction) ในการพิสูจน์ ให้ K € I⁺ มีนกอย่างน้อย K+1 ตัว บินเข้ารัง K
รัง สมมติให้ ไม่มีรังนกใดเลยใน K รัง ที่มีนกมากกว่า
1 ตัว ดังนั้นรังนกแต่ละรังจะมีนก 1
ตัว หรือไม่มีเลย และมีรังนกทั้งหมด K รัง
จึงได้ว่าจะมีจำนวนนกทั้งหมดน้อยกว่า 1
ตัวหรือเท่ากับ K
ตัว (จำนวนทั้งหมด ≤ K ×1 )
เกิดข้อขัดแย้ง
เพราะมีจำนวนนกอย่างน้อย K+ 1
ตัว เพราะฉะนั้น ถ้ามีนกอย่างน้อย K+ 1
ตัว บินเข้ารัง K
รัง จะมีรังอย่างน้อย 1 รัง ที่มีนกน้อย 2 ตัว
|
ทฤษฎีบทที่ 2
หลักการรังนกพิราบในกรณีทั่วไป (The Generalized
pigeonhole principle)
ให้ N, K € I⁺ ถ้ามีนกพิราบ N ตัว บินเข้ารัง K รัง
จะได้ว่าจะมีรังอย่างน้อย 1 รัง
ที่มีนกพิราบอย่างน้อย N/K ตัว
|
พิสูจน์ทฤษฎีบทที่ 2
ใช้วิธีการขัดแย้ง
(by contradiction) ในการพิสูจน์
ให้ให้ N, K € I⁺ , ถ้ามีนก N ตัว บินเข้ารัง K รัง สมมติให้ไม่มีรังนกใดที่มีนกอยู่มากกว่า
1 ตัว
จะได้ว่า
จะมีจำนวนนกทั้งหมดไม่เกิน K ×
ตัว
จากคุณสมบัติของ ceiling
function ที่กล่าวว่า
<
X+1
ดังนั้น จะได้ว่า
<
+ 1
เพราะฉะนั้น K ×
K
เกิดข้อขัดแย้ง
เพราะมีนกอยู่ทั้งหมด N ตัว
ไม่มีความคิดเห็น:
แสดงความคิดเห็น