หลักรังนกพิราบ

thumb|right|จะเห็นว่าในรูปมีนกพิราบอยู่ 10 ตัว และมีรังอยู่เพียงแค่ 9 รัง ดังนั้นจึงมีอย่างน้อยหนึ่งรังที่มีนกอยู่สองตัว

ในสาขาคณิตศาสตร์ **หลักรังนกพิราบ** () กล่าวว่าหากมีนกพิราบอยู่ n ตัว แล้วต้องการนำนกพิราบเหล่านี้ไปใส่ในรังนกพิราบ m รัง โดยที่ n > m แล้ว จะได้ว่าจะมีอย่างน้อยหนึ่งรังที่มีนกพิราบอยู่มากกว่าหนึ่งตัว ทฤษฏีนี้ปูทางให้เราสามารถกล่าวได้ว่า *"จะต้องมีถุงมือข้างซ้ายอย่างน้อย 2 ข้าง ไม่ก็ถุงมือขวาข้างอย่างน้อย 2 ข้าง ทุก ๆ ถุงมือ 3 ข้าง"*  หรือแม้แต่คำพูดที่ดูแล้วน่าทึ่งเช่น *"รับประกันได้เลย ใน[[กรุงเทพมหานคร]]มีอย่างน้อยสองคนที่มีจำนวนเส้นผมบนหัวเท่ากัน"* ก็สามารถพิสูจน์ให้เห็นจริงได้ด้วยหลักรังนกพิราบได้เช่นกัน (ซึ่งแสดงไว้ด้านล่าง)

## ตัวอย่าง
### หยิบถุงเท้า
สมมติว่าในกล่องใบหนึ่งมีถุงเท้าสีขาวอยู่ 12 ข้าง และสีดำอยู่ 10 ข้าง จงหาจำนวนครั้งในการหยิบน้อยที่สุดที่รับประกันได้เลยว่าจะได้ถุงเท้าสีเดียวกันหนึ่งคู่ เราจะกล่าวได้ว่ารังนกพิราบก็คือ รังของนกสีขาวและรังของนกสีดำนั่นคือมีสองรังเท่านั้น * (m = 2) * ต้องหาจำนวนนกพิราบที่จะรับประกันได้ว่าจะมีอย่างน้อยหนึ่งรังที่มีนกสองตัว จากหลักรังนกพิราบจะได้ว่าต้องหา n > m ที่น้อยที่สุดนั่นก็คือ n = 3 จะเห็นว่าถ้าเราหยิบถุงเท้ามาแล้วสองข้าง * (n=2) * อย่างแย่ที่สุดเราจะก็มีถุงเท้าสีขาวและสีดำอย่างละข้างเมื่อหยิบอีกหนึ่งข้างก็ต้องได้ครบคู่

### นับเส้นผม
เราสามารถกล่าวได้ว่ามีคนอย่างน้อยสองคนในกรุงเทพมหานครที่มีจำนวนเส้นผมบนหัวเท่ากันพอดี เนื่องจากโดยปกติแล้วเส้นผมของมนุษย์จะมีประมาณ​ 150,000 เส้น ดังนั้นการสมมติว่าไม่มีใครที่มีเส้นผมเกินล้านเส้นก็สมเหตุสมผล * (m = 1,000,000) * ประกอบกับมีคนมากกว่าล้านคนในกรุงเทพมหานคร * (n > 1,000,000 = m) * สามารถเปรียบเทียบได้กับมีนกพิราบมากกว่าหนึ่งล้านตัว แต่มีรังนกพิราบเพียงหนึ่งล้านรัง จากหลักของรังนกพิราบเพราะ n > m จะได้ว่ามีอย่างน้อยหนึ่งรังที่มีนกพิราบอาศัยอยู่อย่างน้อยสองตัว นั่นคือมีอย่างน้อยสองคนในกรุงเทพมหานครที่มีจำนวนเส้นผมบนหัวเท่ากัน แต่หากประชาการในกรุงเทพมหานครไม่ถึงหนึ่งล้านคนก็มิได้หมายความว่าจะไม่มีใครที่มีเส้นผมเท่ากันเลย อาจจะมีอยู่ก็ได้ แต่หลักรังนกพิราบไม่ได้รับประกัน

### ปัญหาวันเกิด
ปัญหาวันเกิดถามว่าในกลุ่มคนกลุ่มหนึ่งจะมีโอกาสเท่าไหร่ที่จะมีคนที่มีวันเกิดซ้ำกัน แต่สำหรับหลักรังนกพิราบนั้นหากมี 367 คน ก็จะรับประกันได้ว่ามีคนที่มีวันเกิดซ้ำกันแน่นอน เพราะว่าจำนวนคน (n = 367) จะมากกว่ารูปแบบของวันที่เป็นไปได้ในหนึ่งปี (m = 366 รวมวันที่ 29 กุมภาพันธ์)

### ทีมฟุตบอล
สมมุติมีคน 11 คนที่ต้องการเล่นฟุตบอล โดยมีทีมให้เลือกลงเล่น 6 ทีม โดยหลักรังนกพิราบเราสามารถแสดงได้ว่า 11 คนนี้ไม่สามารถเล่นทีมแตกต่างกันได้ทุกคน และต้องมีอย่างน้อยทีมหนึ่งที่มี 2 คนจาก 6 คนนี้ในทีมนั้น ซึ่งแสดงได้จาก

:\left\lfloor \frac{n-1}{m} \right\rfloor + 1 = \left\lfloor \frac{11-1}{6} \right\rfloor + 1 = \left\lfloor \frac{10}{6} \right\rfloor + 1 = 1 + 1 = 2

## ประโยชน์

## รูปทั่วไป
ให้ *q<sub>1</sub>, q<sub>2</sub>, ..., q<sub>n</sub>* เป็นจำนวนเต็มบวก ถ้านำนกพิราบจำนวน *q<sub>1</sub> + q<sub>2</sub> + ... + q<sub>n</sub> - n + 1* ตัวใส่ใน n รัง แล้ว รังที่หนึ่งมีนกอย่างน้อย *q<sub>1</sub>* ตัว หรือ รังที่สองมีนกอย่างน้อย *q<sub>2</sub>* ตัว หรือ ... หรือ รังที่ *n* มีนกอย่่างน้อย *q<sub>n</sub>* ตัว

* กรณี *q<sub>1 =</sub> q<sub>2 =</sub> ... = q<sub>n</sub> = 2* จะได้นก *n + 1* ตัว ตรงกับหลักรังนกพิราบธรรมดา

* กรณี *q<sub>1 =</sub> q<sub>2 =</sub> ... = q<sub>n</sub> = r* จะได้เป็นหลักว่า "เมื่อนำนก *n(r - 1) + 1* ตัวไปใส่ในรัง n รัง แล้วอย่างน้อย 1 รังจะมีนกอย่างน้อย *r* ตัว" หรือสามารถเขียนได้อีกแบบว่า "หากนำนก k ตัวใส่ในรัง n รัง  อย่างน้อย 1 รังจะมีนกอย่างน้อย \lceil{k/n}\rceilตัว (\lceil x \rceilเป็นฟังก์ชันเพดาน)"

## แหล่งข้อมูลอื่น
* 
* "The strange case of The Pigeon-hole Principle"; Edsger Dijkstra investigates interpretations and reformulations of the principle.
* "The Pigeon Hole Principle"; Elementary examples of the principle in use by Larry Cusick.
* "Pigeonhole Principle from Interactive Mathematics Miscellany and Puzzles"; basic Pigeonhole Principle analysis and examples by Alexander Bogomolny.
* "The Puzzlers' Pigeonhole "; Alexander Bogomolny on the importance of the principle in the field of puzzle solving and analysis.
* "16 fun applications of the pigeonhole principle"; Interesting facts derived by the principle.

หมวดหมู่:หลักการทางคณิตศาสตร์
หมวดหมู่:คณิตศาสตร์เชิงการจัด