หลักการรังนกพิราบและตัวอย่าง

หลักการรังนกพิราบ(The pigeonhole principle) ถ้ามีนกพิราบ n ตัว และมีรังนกพิราบ m รัง โดยที่ m<n แล้วจะต้องมีอย่างน้อยหนึ่งรังที่มีนกพิราบมากกว่าหนึ่งตัว

ตัวอย่างที่ 1 ถ้าคน 8 คนถูกเลือกมาโดยวิธีใดวิธีหนึ่ง แล้วจะต้องมีคนอย่างน้อยสองคนที่เกิดวันเดียวกัน(วันในหนึ่งสัปดาห์)
วิธีทำ ในที่นี้แต่ละคน(นกพิราบ) จะต้องมีวันเกิด(รังนกพิราบ) และเนื่องจากมีคนอยู่ 8 คน และมีวันในสัปดาห์เพียง 7 วัน โดยหลักการรังนกพิราบจะบอกได้ว่ามีคนอย่างน้อยสองคนที่มีวันเกิดวันเดียวกัน 

ตัวอย่างที่ 2 จงแสดงว่าถ้าเลือกจำนวนห้าจำนวน จากจำนวน 1 ถึง 8 แล้วจะต้องมีจำนวนอย่างน้อยคู่หนึ่งที่รวมกันได้ 9
วิธีทำ จากจำนวน 1-8 สร้างเซตที่ประกอบด้วยจำนวนสองจำนวนที่รวมกันได้ 9 ได้ดังนี้ {1,8} , {2,7} , {3,6} , {4,5} แต่ละจำนวนที่เลือกมา 5 จำนวนจะต้องอยู่ในเซตใดเซตหนึ่ง แต่มีเซตอยู่เพียง 4 เซต ดังนั้นโดยหลักการนกพิราบจะต้องมีอย่างน้อย หนึ่งเซตที่มีจำนวนที่เลือกอยู่สองจำนวน นั่นคือจำนวนทั้งสองรวมกันได้ 9 นั่นเอง 

ตัวอย่างที่ 3 จงแสดงว่าถ้าเลือกจำนวน 11 จำนวน จากเซต {1, 2, ..., 20} แล้วจะต้องมีจำนวนอย่างน้อยหนึ่งจำนวน ที่เป็นตัวคูณ(multiple) ของอีกจำนวนหนึ่ง
วิธีทำ เนื่องจากทุกจำนวนเต็มบวก n สามารถเขียนอยู่ในรูป n = (2^k)(m) เมื่อ m เป็นจำนวนคี่และ k ณ 0 ได้เสมอ ในที่นี้จะขอเรียกจำนวน m ว่าส่วนคี่ ของจำนวน n เมื่อจำนวน 11 จำนวนถูกเลือกจากเซ็ต {1,2, ..., 20} แล้วจะมีอย่างน้อยสองจำนวนที่มีส่วนคี่เหมือนกัน ทั้งนี้เนื่องมาจากหลักการรังนกพิราบที่มีจำนวน 11 จำนวน(นกพิราบ) ในขณะที่มี จำนวนคี่เพียง 10 จำนวน จาก 1- 20 (รังนกพิราบ) ที่จะเป็นส่วนคี่ของ 11จำนวนนั้น
     ให้ n1 และ n2 เป็นจำนวนที่มีส่วนคี่เหมือนกัน เราจะได้ว่า n1=(2^k1)(m) และ n2 = (2^k2)(m) ถ้า K1>k2 จะได้ว่า n1 เป็นตัวคูณ(multiple) ของ n2

ส่วนขยายของหลักการรังนกพิราบ
หากลองพิจารณากรณีรังนกพิราบ m รัง และมีนกพิราบมากกว่า 2m ตัว แล้วจะได้ว่ามีนกพิราบอย่างน้อยสามตัวเข้าไปอยู่ในรังใดรังหนึ่งอย่างน้อยหนึ่งรัง
     ในกรณีทั่วไปสามารถเขียนหลักการรังนกพิราบ ที่มีความแข็งกว่าเดิมได้

หลักการรังนกพิราบส่วนขยาย(The Extended Pigeonhole Principle) ถ้ามีมีนกพิราบ n ตัว และมีรังนกพิราบ m รัง โดยที่ m<n แล้วจะต้องมีอย่างน้อยหนึ่งรังที่มีนกพิราบไม่ต่ำกว่าภ(n-1)/mู + 1ตัว โดย ภ(n-1)/mู แทนจำนวนเต็มที่มากที่สุดที่น้อยกว่าหรือเท่ากับ (n-1)/m

ตัวอย่างที่ 4 จงแสดงว่าในจำนวนคน 30 คน จะมีอย่างน้อย 5 คนที่มีวันเกิด(ในสัปดาห์)วันเดียวกัน
วิธีทำ ในจำนวนคน(นกพิราบ) 30 คน วันเกิดที่เป็นไปได้(รังนกพิราบ) 7 วัน โดยหลักการนกพิราบส่วนขยาย จะต้องมีคนอย่างน้อย ภ(n-1)/mู + 1 =ภ(30-1)/7ู + 1= 5 คนที่มีวันเกิดวันเดียวกัน