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

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

ในสาขาคณิตศาสตร์ หลักรังนกพิราบ (อังกฤษ: pigeonhole principle) กล่าวว่าหากมีนกพิราบอยู่ 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 กุมภาพันธ์)

จำนวนนับ[แก้]

กำหนดให้ n+1 และจำนวนที่เราเลือกมาคือ a1,...,an+1 และเขียน aiในรูปของ 2kb โดยที่ bi เป็นจำนวนคี่ ดังนั้นเรามี b1,...,bn+1 เป็นจำนวนคี่ n+1 จำนวนในช่วง [1, 2n-1] สำหรับหลักรังนกพิราบเปรียบเทียบให้ bi เป็นลูกแก้ว ส่วนจำนวนคี่ที่อยู่ในช่วง [1, 2n-1] เป็นกล่อง เรามีลูกแก้ว n+1 ลูก แต่มีกล่อง n กล่อง (เพราะตั้งแต่ 1 ถึง 2n-1 มีจำนวนคี่อยู่ n ตัว) ดังนั้นต้องมี biอย่างน้อยสองตัวในกล่องเดียวกัน คือเป็นจำนวนคี่จำนวนเดียวกัน สมมติว่าจำนวนคี่สองจำนวนนั้นคือ bx = by ดังนั้นคู่ ax กับ ay ไม่ตัวใดก็ตัวหนึ่งต้องหารอีกตัวหนึ่งลงตัว

ประโยชน์[แก้]

รูปทั่วไป[แก้]

แหล่งข้อมูลอื่น[แก้]