หลักการช่องนกพิราบ หรือที่เรียกกันว่า หลักการรังนกพิราบ ( Pigeonhole Principle )
เป็นทฤษฎีบทแรกๆ ในการเรียนวิชาคณิตศาสตร์เชิงการจัด หรือในบางที่ถูกใส่เข้าไว้ในวิชาดิสครีทแมท เป็นทฤษฎีบทง่ายๆ เหมาะกับการเริ่มต้นเรียนวิชานี้
ทฤษฎีบท หลักการช่องนกพิราบ
"หากมีนกพิราบจำนวน n+1 ตัว บินลงมาในรัง n รังแล้ว จะต้องมีอย่างน้อย 1 รัง ที่มีนกมากกว่า หรือเท่ากับ 2 ตัว"
มันเป็นอย่างไร ให้อธิบายเป็นภาพก็คงเป็น .....
สมมติภาพในกรณี n = 3
ในกรณีที่เลวร้ายที่สุดที่จะไม่ทำให้ทฤษฎีบทนี้เป็นจริงคือ ทุกกล่องต้องมี ไม่เกิน 1 ตัว
ดังนั้นจะมีนก 1 ตัวที่เหลือรอดจากกการเข้าไปอยู่ในรัง นกตัวนี้จึงจำเป็นต้องเข้าไปอาศัยอยู่ในรังที่มีนกอยู่แล้ว
สรุปได้ว่า ไม่ว่ายังไงจะต้องมีอย่างน้อยรังนึง ที่มีนก อย่างน้อย สองตัว แน่ๆ
ตัวอย่าง กำหนดให้มีคู่รักจำนวน n คู่ จะต้องเลือกมาอย่างน้อยทั้งหมดกี่คน ถึงจะการันตีได้ว่า ในจำนวนที่เลือกมามีคู่รักอยู่ด้วยหนึ่งคู่เสมอ
- ให้มองว่ามีกล่องใส่คู่รักจำนวน n กล่อง หากเขาเป็นคู่รักกันจะได้อยู่ในกล่องเดียวกัน จากหลักการช่องนกพิราบอย่างง่าย จะได้ว่า เราจำเป็นต้องเลือก n+1 คนเพื่อที่จะการันตีได้ว่ามีอย่างน้อย 1 กล่องที่มี 2คน ขึ้นไปเสมอ ( ในที่นี้ก็มีได้แค่ 2 คนละนะ )
ตัวอย่าง กำหนด จำนวนเต็ม a[1] , a[2] , ... , a[m] จะมีจำนวนเต็ม k , l ที่ 0 <= k <= l <= m ( <= คือ น้อยกว่าหรือเท่ากับ ) ที่ทำให้ a[k+1] + a[k+2] +...+a[l] หารด้วย m ลงตัว
หรือพูดง่ายๆว่า ในลำดับ a[1] , a[2] , ... , a[m] จะมีลำดับย่อยที่ผลรวมของมันหารด้วย m ลงตัว
- พิจารณาผลรวมของสมาชิกแต่ละตัวโดยเริ่มจาก a[1] เสมอ
a[1] , a[1]+a[2] , a[1]+a[2]+a[3] , ... , a[1]+a[2]+...+a[m]
มีทั้งหมด m แบบ ในกรณีที่หนึ่ง ในนี้ หารด้วย m ลงตัว จะได้ว่า ตัวนั้นคือลำดับย่อยที่มองหาอยู่
แต่ถ้าในกรณีที่ผลรวมแต่ละแบบที่พิจารณา ไม่มีแบบที่หารด้วย m ได้ลงตัวเลยล่ะ?
ในเมื่อมันหารด้วย m ไม่ลงตัว แสดงว่าเศษของการหาร ไม่เท่ากับ 0
นั่นคือ เศษจากการหารที่เป็นไปได้คือ 1 , 2 , ... , m-1
แต่ a[1] , a[1]+a[2] , a[1]+a[2]+a[3] , ... , a[1]+a[2]+...+a[m] มีจำนวน m ตัว
โดยหลักการช่องนกพิราบจะได้ว่า จะต้องมีอย่างน้อย 2 แบบในนี้ ที่ให้เศษที่เท่ากันแน่นอน
กำหนดให้
a[1]+a[2]+...+a[k] และ a[1]+a[2]+...+a[l] เมื่อ 0 <= k <= l <= m
หรือพูดง่ายๆว่า ให้ a[1] + ... + a[k] และ a[1] + ... + a[ l ] คือลำดับย่อยที่มีเศษ r เท่ากัน นั่นคือ
a[1]+a[2]+...+a[k] = bm + r
และ
a[1]+a[2]+...+a[l] = cm + r
จับลบกันจะได้
a[k+1]+a[k+2]+...+a[l] = (c-b)m
นั่นคือ a[k+1]+a[k+2]+...+a[l] หารด้วย m ลงตัว
จริงๆ แล้วยังมีตัวอย่างอีกหลากหลายสำหรับทฤษฎีบทนี้ แต่อันนี้ยกตัวอย่างมาเพียงเพื่อให้เห็นภาพและประโยชน์คร่าวๆเพียงเท่านั้น นอกจาก หลักการแบบอย่างง่ายแล้ว หลักการช่องนกพิราบยังมีในรูปแบบของ หลักการทั่วไปอยู่อีกด้วย ซึ่งจะพูดถึงในคราวหน้า
