[Math] หลักการช่องนกพิราบ อย่างง่าย


หลักการช่องนกพิราบ หรือที่เรียกกันว่า หลักการรังนกพิราบ ( 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 ลงตัว

จริงๆ แล้วยังมีตัวอย่างอีกหลากหลายสำหรับทฤษฎีบทนี้ แต่อันนี้ยกตัวอย่างมาเพียงเพื่อให้เห็นภาพและประโยชน์คร่าวๆเพียงเท่านั้น นอกจาก หลักการแบบอย่างง่ายแล้ว หลักการช่องนกพิราบยังมีในรูปแบบของ หลักการทั่วไปอยู่อีกด้วย ซึ่งจะพูดถึงในคราวหน้า

355 Total Views 3 Views Today
mu

mu

ชอบคณิตศาสตร์เชิงวิเคราะห์ ทฤษฎีความน่าจะเป็น Numerical และการ Optimization ในรูปแบบต่างๆ อยากเห็นประเทศไทยให้ความสำคัญกับงานด้านวิจัย และคณิตศาสตร์

ใส่ความเห็น

อีเมลของคุณจะไม่แสดงให้คนอื่นเห็น ช่องที่ต้องการถูกทำเครื่องหมาย *