ลิงก์ข้ามภาษาในบทความนี้ มีไว้ให้ผู้อ่านและผู้ร่วมแก้ไขบทความศึกษาเพิ่มเติมโดยสะดวก เนื่องจากวิกิพีเดียภาษาไทยยังไม่มีบทความดังกล่าว กระนั้น ควรรีบสร้างเป็นบทความโดยเร็วที่สุด |
บทความนี้ไม่มีจาก |
ในสาขาคณิตศาสตร์ หลักรังนกพิราบ (อังกฤษ: pigeonhole principle) กล่าวว่าหากมีนกพิราบอยู่ ตัว แล้วต้องการนำนกพิราบเหล่านี้ไปใส่ในรังนกพิราบ รัง โดยที่ แล้ว จะได้ว่าจะมีอย่างน้อยหนึ่งรังที่มีนกพิราบอยู่มากกว่าหนึ่งตัว ทฤษฏีนี้ปูทางให้เราสามารถกล่าวได้ว่า "จะต้องมีถุงมือข้างซ้ายอย่างน้อย 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 กุมภาพันธ์)
ทีมฟุตบอล
สมมุติมีคน 11 คนที่ต้องการเล่นฟุตบอล โดยมีทีมให้เลือกลงเล่น 6 ทีม โดยหลักรังนกพิราบเราสามารถแสดงได้ว่า 11 คนนี้ไม่สามารถเล่นทีมแตกต่างกันได้ทุกคน และต้องมีอย่างน้อยทีมหนึ่งที่มี 2 คนจาก 6 คนนี้ในทีมนั้น ซึ่งแสดงได้จาก
ประโยชน์
ส่วนนี้รอเพิ่มเติมข้อมูล คุณสามารถช่วยเพิ่มข้อมูลส่วนนี้ได้ |
รูปทั่วไป
ให้ q1, q2, ..., qn เป็นจำนวนเต็มบวก ถ้านำนกพิราบจำนวน q1 + q2 + ... + qn - n + 1 ตัวใส่ใน n รัง แล้ว รังที่หนึ่งมีนกอย่างน้อย q1 ตัว หรือ รังที่สองมีนกอย่างน้อย q2 ตัว หรือ ... หรือ รังที่ n มีนกอย่่างน้อย qn ตัว
- กรณี q1 = q2 = ... = qn = 2 จะได้นก n + 1 ตัว ตรงกับหลักรังนกพิราบธรรมดา
- กรณี q1 = q2 = ... = qn = r จะได้เป็นหลักว่า "เมื่อนำนก n(r - 1) + 1 ตัวไปใส่ในรัง n รัง แล้วอย่างน้อย 1 รังจะมีนกอย่างน้อย r ตัว" หรือสามารถเขียนได้อีกแบบว่า "หากนำนก k ตัวใส่ในรัง n รัง อย่างน้อย 1 รังจะมีนกอย่างน้อย ตัว (เป็นฟังก์ชันเพดาน)"
แหล่งข้อมูลอื่น
- Hazewinkel, Michiel, บ.ก. (2001), "Dirichlet box principle", , , ISBN
- "The strange case of The Pigeon-hole Principle"; Edsger Dijkstra investigates interpretations and reformulations of the principle.
- "The Pigeon Hole Principle"; Elementary examples of the principle in use by Larry Cusick.
- "Pigeonhole Principle from Interactive Mathematics Miscellany and Puzzles"; basic Pigeonhole Principle analysis and examples by Alexander Bogomolny.
- "The Puzzlers' Pigeonhole 2002-06-18 ที่ เวย์แบ็กแมชชีน"; Alexander Bogomolny on the importance of the principle in the field of puzzle solving and analysis.
- "16 fun applications of the pigeonhole principle"; Interesting facts derived by the principle.
wikipedia, แบบไทย, วิกิพีเดีย, วิกิ หนังสือ, หนังสือ, ห้องสมุด, บทความ, อ่าน, ดาวน์โหลด, ฟรี, ดาวน์โหลดฟรี, mp3, วิดีโอ, mp4, 3gp, jpg, jpeg, gif, png, รูปภาพ, เพลง, เพลง, หนัง, หนังสือ, เกม, เกม, มือถือ, โทรศัพท์, Android, iOS, Apple, โทรศัพท์โมบิล, Samsung, iPhone, Xiomi, Xiaomi, Redmi, Honor, Oppo, Nokia, Sonya, MI, PC, พีซี, web, เว็บ, คอมพิวเตอร์
lingkkhamphasa inbthkhwamni miiwihphuxanaelaphurwmaekikhbthkhwamsuksaephimetimodysadwk enuxngcakwikiphiediyphasaithyyngimmibthkhwamdngklaw krann khwrribsrangepnbthkhwamodyerwthisudbthkhwamniimmikarxangxingcakaehlngthimaidkrunachwyprbprungbthkhwamni odyephimkarxangxingaehlngthimathinaechuxthux enuxkhwamthiimmiaehlngthimaxacthukkhdkhanhruxlbxxk eriynruwacanasaraemaebbnixxkidxyangiraelaemuxir insakhakhnitsastr hlkrngnkphirab xngkvs pigeonhole principle klawwahakminkphirabxyu n textstyle n tw aelwtxngkarnankphirabehlaniipisinrngnkphirab m textstyle m rng odythi n gt m textstyle n gt m aelw caidwacamixyangnxyhnungrngthiminkphirabxyumakkwahnungtw thvstiniputhangiherasamarthklawidwa catxngmithungmuxkhangsayxyangnxy 2 khang imkthungmuxkhwakhangxyangnxy 2 khang thuk thungmux 3 khang hruxaemaetkhaphudthiduaelwnathungechn rbpraknidely inkrungethphmhankhrmixyangnxysxngkhnthimicanwnesnphmbnhwethakn ksamarthphisucnihehncringiddwyhlkrngnkphirabidechnkn sungaesdngiwdanlang caehnwainrupminkphirabxyu 10 tw aelamirngxyuephiyngaekh 9 rng dngnncungmixyangnxyhnungrngthiminkxyusxngtwtwxyanghyibthungetha smmtiwainklxngibhnungmithungethasikhawxyu 12 khang aelasidaxyu 10 khang cnghacanwnkhrnginkarhyibnxythisudthirbpraknidelywacaidthungethasiediywknhnungkhu eracaklawidwarngnkphirabkkhux rngkhxngnksikhawaelarngkhxngnksidannkhuxmisxngrngethann m 2 txnghacanwnnkphirabthicarbpraknidwacamixyangnxyhnungrngthiminksxngtw cakhlkrngnkphirabcaidwatxngha n gt m thinxythisudnnkkhux n 3 caehnwathaerahyibthungethamaaelwsxngkhang n 2 xyangaeythisuderacakmithungethasikhawaelasidaxyanglakhangemuxhyibxikhnungkhangktxngidkhrbkhu nbesnphm erasamarthklawidwamikhnxyangnxysxngkhninkrungethphmhankhrthimicanwnesnphmbnhwethaknphxdi enuxngcakodypktiaelwesnphmkhxngmnusycamipraman 150 000 esn dngnnkarsmmtiwaimmiikhrthimiesnphmekinlanesnksmehtusmphl m 1 000 000 prakxbkbmikhnmakkwalankhninkrungethphmhankhr n gt 1 000 000 m samarthepriybethiybidkbminkphirabmakkwahnunglantw aetmirngnkphirabephiynghnunglanrng cakhlkkhxngrngnkphirabephraa n gt m caidwamixyangnxyhnungrngthiminkphirabxasyxyuxyangnxysxngtw nnkhuxmixyangnxysxngkhninkrungethphmhankhrthimicanwnesnphmbnhwethakn aethakprachakarinkrungethphmhankhrimthunghnunglankhnkmiidhmaykhwamwacaimmiikhrthimiesnphmethaknely xaccamixyukid aethlkrngnkphirabimidrbprakn pyhawnekid pyhawnekidthamwainklumkhnklumhnungcamioxkasethaihrthicamikhnthimiwnekidsakn aetsahrbhlkrngnkphirabnnhakmi 367 khn kcarbpraknidwamikhnthimiwnekidsaknaennxn ephraawacanwnkhn n 367 camakkwarupaebbkhxngwnthiepnipidinhnungpi m 366 rwmwnthi 29 kumphaphnth thimfutbxl smmutimikhn 11 khnthitxngkarelnfutbxl odymithimiheluxklngeln 6 thim odyhlkrngnkphiraberasamarthaesdngidwa 11 khnniimsamarthelnthimaetktangknidthukkhn aelatxngmixyangnxythimhnungthimi 2 khncak 6 khnniinthimnn sungaesdngidcak n 1m 1 11 16 1 106 1 1 1 2 displaystyle left lfloor frac n 1 m right rfloor 1 left lfloor frac 11 1 6 right rfloor 1 left lfloor frac 10 6 right rfloor 1 1 1 2 praoychnswnnirxephimetimkhxmul khunsamarthchwyephimkhxmulswnniidrupthwipih q1 q2 qn epncanwnetmbwk thanankphirabcanwn q1 q2 qn n 1 twisin n rng aelw rngthihnungminkxyangnxy q1 tw hrux rngthisxngminkxyangnxy q2 tw hrux hrux rngthi n minkxyangnxy qn tw krni q1 q2 qn 2 caidnk n 1 tw trngkbhlkrngnkphirabthrrmdakrni q1 q2 qn r caidepnhlkwa emuxnank n r 1 1 twipisinrng n rng aelwxyangnxy 1 rngcaminkxyangnxy r tw hruxsamarthekhiynidxikaebbwa haknank k twisinrng n rng xyangnxy 1 rngcaminkxyangnxy k n displaystyle lceil k n rceil tw x displaystyle lceil x rceil epnfngkchnephdan aehlngkhxmulxunHazewinkel Michiel b k 2001 Dirichlet box principle ISBN 978 1 55608 010 4 The strange case of The Pigeon hole Principle Edsger Dijkstra investigates interpretations and reformulations of the principle The Pigeon Hole Principle Elementary examples of the principle in use by Larry Cusick Pigeonhole Principle from Interactive Mathematics Miscellany and Puzzles basic Pigeonhole Principle analysis and examples by Alexander Bogomolny The Puzzlers Pigeonhole 2002 06 18 thi ewyaebkaemchchin Alexander Bogomolny on the importance of the principle in the field of puzzle solving and analysis 16 fun applications of the pigeonhole principle Interesting facts derived by the principle