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

หลักการรังนกพิราบ(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 คนที่มีวันเกิดวันเดียวกัน

หลักการรังนกพิราบ (The pigeonhole principle)

หลักการรังนกพิราบ (The pigeonhole principle)

          

    หลักการรังนกพิราบ (The pigeonhole principle) เป็นการใช้ความจริงในธรรมชาติซึ่งเกี่ยวกับนกพิราบและรังของนกพิราบ โดยกล่าวว่า “ถ้ามีจำนวนนกพิราบมากกว่ารังนกพิราบแล้ว จะต้องมีอย่างน้อยหนึ่งรัง ที่ทีจำนวนนกพิราบอย่างน้องสองตัว” และหลักการรังนกพิราบนี้ มีชื่อเรียกอีกอย่างหนึ่งว่า “Dirichlet drawer principle” เนื่องจากหลักการนี้ถูกใช้ครั้งแรกโดยนักคณิตศาสตร์ชื่อ P.G.L. Dirichlet (1805-1859)  ซึ่งจากหลักการนี้ สามารถนำไปประยุกต์ใช้ในการแก้ปัญหา แหละคาดการเหตุการณ์การต่างๆ ได้ซึ่งจะนำเสนอต่อไปนี้

ทฤษฎีบทที่ 1                            หลักการรังนกพิราบ (The pigeonhole principle)ให้  K € I⁺ถ้ามีนกพิราบอย่างน้อย K+ 1 ตัว บินเข้ารัง K  รัง แล้วมีรังอย่างน้อย  1 รัง ที่มีนกพิราบอย่างน้อย  2 ตัว

พิสูจน์ทฤษฎีบทที่ 1

             จะใช้วิธีการขัดแย้ง (by  contradiction) ในการพิสูจน์ ให้ K € I⁺   มีนกอย่างน้อย  K+1 ตัว บินเข้ารัง K  รัง  สมมติให้  ไม่มีรังนกใดเลยใน K  รัง  ที่มีนกมากกว่า 1 ตัว ดังนั้นรังนกแต่ละรังจะมีนก 1 ตัว หรือไม่มีเลย และมีรังนกทั้งหมด K  รัง  จึงได้ว่าจะมีจำนวนนกทั้งหมดน้อยกว่า 1 ตัวหรือเท่ากับ K  ตัว  (จำนวนทั้งหมด ≤ K ×1 )

             เกิดข้อขัดแย้ง  เพราะมีจำนวนนกอย่างน้อย K+ 1 ตัว เพราะฉะนั้น ถ้ามีนกอย่างน้อย K+ 1 ตัว บินเข้ารัง K  รัง  จะมีรังอย่างน้อย 1 รัง ที่มีนกน้อย 2 ตัว

ทฤษฎีบทที่ 2           หลักการรังนกพิราบในกรณีทั่วไป (The Generalized pigeonhole principle) ให้  N, K € I⁺ ถ้ามีนกพิราบ N ตัว บินเข้ารัง K รัง จะได้ว่าจะมีรังอย่างน้อย  1 รัง ที่มีนกพิราบอย่างน้อย N/K ตัว

พิสูจน์ทฤษฎีบทที่ 2

                     ใช้วิธีการขัดแย้ง (by  contradiction) ในการพิสูจน์

ให้ให้  N, K € I⁺ , ถ้ามีนก  N ตัว บินเข้ารัง K รัง สมมติให้ไม่มีรังนกใดที่มีนกอยู่มากกว่า 1 ตัว

     จะได้ว่า  จะมีจำนวนนกทั้งหมดไม่เกิน  K ×  ตัว

     จากคุณสมบัติของ ceiling  function  ที่กล่าวว่า <  X+1

     ดังนั้น  จะได้ว่า   <   + 1

     เพราะฉะนั้น  K  ×   K 

     เกิดข้อขัดแย้ง  เพราะมีนกอยู่ทั้งหมด N ตัว

  

การพิสูจน์ทฤษฎีและวิธีการหาคำตอบ

จากการพิสูจน์ทฤษฎี

            เนื่องด้วยโครงงานนี้เป็นโครงงานคณิตศาสตร์ ประเภทการสร้างทฤษฎีหรือการอธิบาย (Thertied Research Project) จึงได้นำเสนอความคิดใหม่ๆ ในการอธิบายเรื่องทฤษฎีรังนกพิราบนี้ โดยใช้หลักการความเป็นเหตุเป็นผลทางคณิตศาสตร์หรือทฤษฎีสนับสนุน ในการทำโครงงาน

ผู้นำโครงงานได้ศึกษาค้นคว้าข้อมูลเพิ่มเติมจากห้องสมุดโรงเรียน อินเทอร์เน็ต และอาจารย์ที่ปรึกษาให้คำแนะนำในการทำโครงงานในครั้งนี้

                   จากการพิสูจน์ทฤษฎีดังกล่าวสามารถนำมาช่วยแก้ปัญหาและประยุกต์ใช้ในการหาคำตอบโจทย์ต่างๆ ดังนี้

1)            ในกลุ่มคนที่มี 367 คน จะต้องมีอย่างน้อย 2 คน ที่เกิดวันเดียวกัน เนื่องจากมีวันเกิดที่แตกต่างกันได้ทั้งหมด 366 วัน

2)            ในบรรดาคำต่างๆ ในภาษาอังกฤษ 27 คำ จะต้องมีอย่างน้อย 2 คำ ที่ขึ้นต้นด้วยอักษรตัวเดียวกันเนื่องจากอักษรภาษาอังกฤษมีทั้งหมด 26 ตัว

3)            จงหาว่าจะต้องมีนักเรียนอย่างน้อยเท่าใดในชั้นเรียน จึงจะสามารถอธิบายได้ว่า จะมีนักเรียน 2 คน ที่ได้รับคะแนนเท่ากัน จากการสอบครั้งนี้ คะแนนมีค่าตั้งแต่ 0 ถึง 100 คะแนน

วิธีการหาคำตอบ

              เนื่องจากการมีคะแนนที่เป็นไปได้ทั้งหมด 101 ค่า ดังนั้น จากทฤษฎีบทที่ 1  ของหลักการรังนกพิราบจะได้ว่า ต้องมีนักเรียนอย่างน้อย 101 + 1 = 102 คน จึงจะแน่ใจได้ว่า จะมีจำนวนนักเรียนอย่างน้อย 2 คนที่ได้รับคะแนนเท่ากัน

4)            อยากทราบว่าจะต้องมีคนอย่างน้อยที่สุดกี่คนจึงจะรับประกันได้ว่าจะมีคนเกิดเดือนเดียวกันสามคน และจงพิสูจน์ว่าคำตอบนั้นเป็นจริง

5)            มีจุดห้าจุดอยู่ในรูปสามเหลี่ยมด้านเท่ายาวด้านละสองหน่วย จงแสดงว่าจะมีจุดสองจุดที่ห่างกันไม่เกินหนึ่งหน่วย

6)            ถ้าให้จุดสิบจุดอยู่ในรูปสี่เหลี่ยมด้านเท่ายาวด้านละสามหน่วย จงแสดงว่าจะมีจุดสองจุดที่ห่างกันไม่เกินหน่วย

7)            ถ้าเรามีจำนวนเต็มบวกที่ต่างกัน n+1 ตัว ที่น้อยกว่าหรือเท่ากับ 2n จงแสดงว่าภายในจำนวนนี้จะมีจำนวนคู่หนึ่งที่บวกกันได้ 2n+1

8)            ถ้าเรามีจำนวนเต็มบวกที่ต่างกัน n+1 ตัว ที่น้อยกว่าหรือเท่ากับ 2n จงแสดงว่าภายในจำนวนนี้จะมีจำนวนคู่หนึ่งที่ตัวหารร่วมมากของสองจำนวนนี้เท่ากับหนึ่ง

การหาคำตอบ

              ข้อ 6) สร้างรูปสี่เหลี่ยมด้านเท่าด้านละ 1 หน่วย จะได้ 9 รูป ให้ 9 รูปนั้นแทงรัง และ 10 จุดนั้นแทนนก เราจะได้สิ่งที่ต้องการ

              ข้อ 7) สร้างเซตต่อไปนี้ {1,2n},{2,2n¯1},{3,2n¯2},…, {n,n+1}  ให้เซตเหล่านี้ทั้งหมดแทนรัง ให้จำนวนทั้งหมด n+1 แทนนก เราจะได้สิ่งที่ต้องการ

              ข้อ 8) ทำนองเดียวกับข้อ 4 แต่สร้างเซตแบบนี้ค่ะ {1,2},{3,4},{5,6},…, {n,n+1}

ผลที่เกิดจากการการพิสูจน์ทฤษฎีและการประยุกต์ใช้

ผลที่เกิดจากการการพิสูจน์ทฤษฎีและการประยุกต์ใช้

จากทฤษฎีบทที่ 2 หลักการรังนกพิราบในกรณีทั่วไป (The Generalized Pigeonhole Principle ) ให้ N , K € I⁺ ถ้ามีนกพิราบ N ตัว บินเข้ารัง K รัง จะได้ว่า จะมีรังนกอย่างน้อย 1 รัง ที่มีนกพิราบอย่างน้อย N/K ตัว

กิจกรรมที่ 1

                      ในจำนวนคน 100 คน จะมีอย่างน้อย100/12   = 9 คน ที่เกิดเดือนเดียวกัน เพราะเนื่องจากหนึ่งปีมี 12 เดือน

กิจกรรมที่ 2

                        จงหาจำนวนนักเรียนที่น้อยที่สุดที่เรียนวิชาคณิตศาสตร์เพื่อให้แน่ใจได้ว่ามีนักเรียนอย่างน้อย 6 คน ที่ได้เกรดเดียวกัน โดยเกรดที่เป็นไปได้ทั้งหมดในการเรียนวิชานี้ มีอยู่ 5 เกรด คือ A,B,C,D และ F เราพิจารณาว่าเกรดแต่ละเกรดเป็นรังนก ซึ่งมี 5 รัง ( มี 5 เกรด ) และจำนวนนักเรียนเปรียบเป็นจำนวนนกพิราบ โดยให้จำนวนนักเรียนที่เรียนทั้งหมด ให้มีนักเรียนอย่างน้อย 6 คน ที่ได้รับเกรดเดียวกัน เป็น N คน จากทฤษฎีบทที่ 2 ของหลักการรังนกพิราบ จะได้ว่า  N/5= 6 ดังนั้น ค่า N ที่เป็นไปได้ทั้งหมด มีอยู่ 5 ค่า คือ

(5X5) + 1 = 26

(5X5) + 2 = 27

(5X5) + 3 = 28

(5X5) + 4 = 29

(5X5) + 5 = 30

        ดังนั้น จะได้ว่า ค่า N ที่น้อยที่สุด คือ 26 คน เพราะฉะนั้น จำนวนนักเรียนที่น้อยที่สุดที่จะทำให้แน่ใจได้ว่าจะมีนักเรียนอย่างน้อย 6 คน ที่ได้เกรดเดียวกัน คือ 26 คน

การนำไปประยุกต์ใช้

การนำไปประยุกต์ใช้

                  ต่อไปจะนำหลักการรังนกพิราบ ( The Pigeonhole principle ) ไปประยุกต์ใช้กับปัญหาหนึ่งซึ่งเกี่ยวข้องกับการให้สีกราฟ โดยในที่นี้จะเป็นการพิสูจน์กรณีหนึ่งของการเกิด monochromatic triangle ( กรณี 6 จุด ) ซึ่งเป็นการให้สีเส้นเชื่อม ( edge ) ที่เชื่อมกันระหว่างจุด 2 จุด

ปัญหา

         วาดจุด 6 จุด ลงบนระนาบโดยทุกเส้นเชื่อม ( edge ) ระหว่างจุด 2 จุดจะถูกระบายสีเส้นเป็นสีแดง หรือสีฟ้าอย่างใดอย่างหนึ่ง จงพิสูจน์ว่าจะเกิด monochromatic triangle

หมายเหตุ ;

                 Monochromatic triangle คือสามเหลี่ยมที่มีด้านหรือเส้นเชื่อมมีสีเป็นสีเดียวกันทั้ง 3 เส้นและการเกิด monochromatic triangle จะเกิดขึ้นได้ต้องมีจำนวนจุดอย่างน้อย 6 จุด ถ้ามีจำนวนจุดน้อยกว่า 6 จุดจะไม่เกิด

แนวคิดและการพิสูจน์

                   ปัญหานี้ดูผิวเผินแล้วดูเหมือนไม่น่าจะมีส่วนเกี่ยวข้องกับหลักการรังนกพิราบ ( The Pigeonhole principle ) ได้เลย แต่ในความเป็นจริงแล้วมันมีความเกี่ยวข้องกันอยู่ ซึ่งสามารถนำมาช่วยในการพิสูจน์ปัญหานี้ได้ จะเริ่มด้วยการพิจารณาว่า อะไรคือสิ่งที่แทนจำนวนรังนกและอะไรแทนจำนวนนกพิราบ ซึ่งเริ่มต้นเรายังไม่สามารถระบุลงไปชัดเจนได้ว่า จะใช้อะไรแทนดี แต่อย่างไรก็ตาม เราก็ยังพอที่จะคิดหรือรู้ได้ว่า สามเหลี่ยมจะต้องถูกสร้างขึ้นมาจากเส้นเชื่อมระหว่าจุดแน่นอน เนื่องจากจำนวนเส้นเชื่อมทั้งหมดระหว่างจุด 2 จุด ( มีจำนวนจุดอยู่ทั้งหมด 6 จุด ) เท่ากับ   15 เส้นเชื่อม

พิสูจน์ทฤษฎีบทที่2

                      จากหลักการรังนกพิราบ ( ทฤษฎีบทที่ 2 ) โดยเปรียบให้จำนวนเส้นเชื่อม 15 เส้น คือ จำนวนนกพิราบ 15 ตัว และ จำนวนสี คือ จำนวนรังนกพอราบ ( มีอยู่ 2 สี แดงกับฟ้า ) ดังนั้น เราจะได้ว่า จะมีอย่างน้อย   8 เส้นเชื่อม ที่ถูกระบายสีเป็นสีเดียวกัน ( เปรียบเหมือนอยู่ในรังนกเดียวกัน ) เราจะเลือกสีมา 1 สี ระหว่างสีแดงกับสีฟ้า สมมุติเป็นสีแดง ( ถ้าเลือกสีฟ้าก็เป็นไปในทำนองเดียวกัน ) แต่หลังจากลองวาดรูปและลองพิจารณาดูแล้วจะเห็นว่า เราไม่สามารถที่จะยืนยันได้ว่าจะเกิดสามเหลี่ยมที่มีด้านทั้งสามเป็นสีแดงได้ ดังรูปที่ 1

 

รูปที่ 1 ไม่เกิดสามเหลี่ยมที่เกิดจากเส้นเชื่อทั้งแปด

                     

         ดังนั้น การกำหนดรูปแบบในลักษณะแบบนี้ จึงใช้ไม่ได้เราจึงต้องมาพิจารณาหารูปแบบใหม่ โดยคราวนี่เราจะพิจารณาโดยเริ่มจากการเน้นไปที่จุดใดจุดหนึ่งใน 6 จุด สมมุติให้เป็นจุด A ( ถ้ากำหนดหรือสมมุติเป็นจุดอื่นก็จะได้ผลออกมาในทำนองเดียวกัน ) ดังนั้นเราได้ว่าจะมีเส้นเชื่อมที่ติดกับ ( incident ) จุด A อยู่ทั้งหมด 5 เส้นเชื่อม ดังรูปที่2

   

                            รูปที่สอง : แสดงเส้นเชื่อมทั้ง 5 เส้น ที่ติดกับจุด A 

พิสูจน์หลักการรังนกพิราบทฤษฎีบทที่ 2

 พิสูจน์หลักการรังนกพิราบทฤษฎีบทที่ 2

            จากหลักการรังนกพิราบ ( ทฤษฎีบทที่ 2 ) โดยเปรียบให้จำนวนเส้นเชื่อมทั้ง 5 เส้นที่ติดกับจุด A คือจำนวนนกพิราบ 5 ตัว และจำนวนสีคือรังของนกพิราบเราจะได้ว่าจะมีอย่างน้อย  = 3  เส้นเชื่อมที่ติดกับจุด A ถูกระบายเป็นสีเดียวกัน สมมุติให้เป็นสีแดง และให้ด้าน AB , AC, และ 3 เส้นเชื่อนั้น ( ถ้ากำหนดให้เป็นสีฟ้า และเป็น 3 เส้นเชื่อมอื่นโดยเลือกจาก 5 เส้นเชื่อมที่ติดกับจุด A แล้วก็จะได้ผลออกมาในทำนองเดียวกัน )

                   ขั้นต่อมา เราจะแบ่งออกได้ 2 กรณี โดยพิจารณาจากด้าน BC และ BD ดังนี้

1)            ถ้าด้านใดด้านหนึ่งระหว่าง BC,CD และ BD เป็นสีแดงอย่างน้อย 1 ด้านก็จะทำให้เกิดสามเหลี่ยมที่มีด้านทั้ง 3 เป็นสีแดง ดังรูปที่ 3

     

                                                รูปที่ 3 แสดงกรณีการเกิดสามเหลี่ยมที่มีด้านทั้ง 3 เป็นเส้นสีแดง

  

2)             ถ้าทั้ง 3 เส้นเชื่อม คือ BC,CD และ BD เป็นสีฟ้าทั้ง 3 เส้นก็จะทำให้เกิดสามเหลี่ยมที่มีด้านทั้ง 3 ด้านเป็นสีฟ้า ดังรูปที่ 4

   

                รูปที่ 3 แสดงกรณีการเกิดสามเหลี่ยมที่มีด้านทั้ง 3 เป็นเส้นสีแดง ( สามเหลี่ยมสีแดง BCD )

จะเห็นได้ว่า จากทั้ง 2 กรณี ก็ล้วนแต่ทำให้เกิดสามเหลี่ยมที่มีด้านทั้งสามเป็นสีเดียวกันจึงได้ว่า จะมี monochromatic triangle เกิดขึ้น