สำหรับ เ็ สอวน. หรือผู้ที่สนใระเบียบวิธี หรือเรื่อมือ่าๆในารแ้ปัหา ะุ้นุยับหลัารรันพิราบ(Pigeon Hole Principle) นี้เป็นอย่าี แ่สำหรับนอื่นๆล่ะ?
ริๆแล้วเรื่อนี้เป็นเรื่อที่ผมไม่เยให้ วามสนใับมันเลยรับ ้วยวามที่เป็นนที่ไม่สนใิศาสร์ทา้านนี้เอาเลย ึทำให้วามสามารถ้านนี้ถถอยเหลือเิน
แล้วทำไมวันนี้ถึหยิบเรื่อนี้ึ้นมาเียน?
้อ อบแบบนี้รับ เมื่อเร็วๆนี้ มีอาารย์ท่านหนึ่ไ้มาพูถึปัหารันพิราบ(Pigeon Hole Problems) ที่น่าสนใในระับยา้อหนึ่ในลาส ึทำให้ผมระหนัถึวามสามารถอเรื่อมือนี้ ว่า เออ ริๆหลัาร่ายๆ(ที่สุ) แบบนี้ สามารถนำมาพิสูน์ หรือ แ้ปัหายาๆไ้อย่า่ายาย
ร่ายมาะยืยาว ราวนี้เราลอมาูันว่า เ้าหลัรันพิราบมันล่าวว่าอย่าไรบ้า
[The Pigeon Hole Principle] : หามีรันอยู่ n รั และมีนอยู่อย่าน้อย n+1 ัว ะมีอย่าน้อยหนึ่รั ที่ะมีนอยู่อย่าน้อย 2 ัว
หา!? แ่นี้เอเหรอ?
ใ่ รับ สั้นๆ ่ายๆ แบบนี้แหละรับ แ่ถ้าไม่มีหลัารนี้ ะทำให้ีวิเรายาลำบาึ้นเยอะรับ เพราะทาิศาสร์เราไม่สามารถยอะไรลอยๆึ้นมาไ้
ทีนี้ ะสสัยันว่า เออ มัน็ริอยู่แล้ว ถ้ามีนมาว่ารั มัน็้อแร์รัันใ้อยู่แล้ว เ็เินไม่เป็น็ิไ้!! ใ่รับ เพราะวาม่ายเวอร์ๆอมันนี่แหละรับ ทำให้ผมัสินใหยิบหลัารนี้ึ้นมานำเสนอใหุ้ๆไ้อ่านัน ลอินนาารูสิ ถ้าผมเอาทฤษีสัมพัทธภาพพิเศษอไอน์สไน์มาีแผ่!!
ในอนแรนี้เราะใหู้ปัหารันพิราบ แบบ่ายๆ มาให้ลอมัน่อนรับ
[1] ริหรือไม่ ที่ว่า "ในำนวนน 367 น ะมีอย่าน้อย 2 นที่เิวันเียวัน" ?
รั : ำนวนวันในหนึ่ปี (เลือใ้ 366 วันนะรับ)
น : นทั้ 367 น
าหลัรันพิราบ ะมีนอย่าน้อย 2 ัว ที่อยู่ในรัเียวัน หรือนั่น็ือ ะมีอย่าน้อย 2 นที่เิวันเียวันนั่นเอรับ #
[2] ริหรือไม่ ที่ว่า "ในบรราำศัพท์่าๆในภาษาอัฤษ 27 ำ ะมีอย่าน้อยสอำ ที่ึ้น้น้วยัวอัษรเียวัน" ?
รั : ัวอัษรทั้หม 26 ัวในภาษาอัฤษ
น : ัวอัษรัวแรอำทั้ 27 ำ
า หลัรันพิราบ ะมีนอย่าน้อย 2 ัว ที่อยู่ในรัเียวัน หรือนั่น็ือ ะมีัวอัษรัวแรอำแ่ละำ ที่เป็นัวเียวัน อย่าน้อย 2 ัว
หลั าัวอย่าที่บรม่าย 2 ัวอย่านี้แล้ว ะพอเห็นอยู่ลาๆว่า ุสำัอหลัารนี้็ือ ารสร้ารั และารสร้าน หรือพู่ายๆว่า ะเอาอะไรมาเป็นรั และรันั้นะมีหน้าายัไ และะเอาอะไรมาเป็นน และนหน้าายัไ สัเุาัวอย่าที่สอ ถ้าเลือนเป็น ำทั้ 27 ำ ็ะไม่เวิร์ ันั้นเรา้อเลือเอาเพาะัวอัษรัวแรอแ่ละำ มาเป็นน ริมั้ยรับ?
เอาล่ะ สำหรับอนที่ 1 อหลัรันพิราบ ็ะอปิเรื่อเพียเท่านี้ และอฝาปัหาให้นัิ(ถ้ามีนอ่าน 55) ลอแู้อีหนึ่ปัหา ึ่แน่นอน ยาว่าัวอย่าที่ยให้แน่นอนรับ
[โทย์ฝาิ] ริหรือไม่ ที่ว่า "ำหนให้เ A = {1,2,3,...,8,9,10} ถ้าเรามีับเใๆอ A ที่มีนาเท่าับ 5 ะมีอย่าน้อย 2 สมาิ ที่มีผลรวมเท่าับ 11" ?
ความคิดเห็น