Egwyddor dwll colomen

Ym mathemateg, mae'r egwyddor dwll colomen yn dweud, os rhoddir $n$ eitem i mewn $m$ cynhwysydd, gyda $n>m$ , yna rhaid i o leiaf un cynhwysydd gynnwys mwy nag un eitem.^[1] Mewn geiriau eraill, os oes gennych chi fwy o "wrthrychau" nag sydd gennych chi "dyllau," rhaid i o leiaf un twll fod â mwy nag un gwrthrych ynddo. Er enghraifft, "os oes gennych dair maneg, yna mae gennych o leiaf ddwy faneg dde, neu o leiaf ddwy faneg chwith," oherwydd bod gennych 3 gwrthrych, ond dim ond dau gategori i'w rhoi mewn (dde neu chwith). Gellir defnyddio'r datganiad ymddangosiadol amlwg hwn, math o ddadl gyfrif, i ddangos canlyniadau annisgwyl o bosibl.

Er bod yr egwyddor dwll colomen yn ymddangos mor gynnar â 1624 mewn llyfr a briodolir i Jean Leurechon,^[2] fe'i gelwir yn gyffredin yn egwyddor blwch Dirichlet neu egwyddor ddrôr Dirichlet ar ôl defnydd Peter Gustav Lejeune Dirichlet o'r egwyddor ym 1834 o dan yr enw Schubfachprinzip ("egwyddor drôr" neu "egwyddor silff").^[3]

Mae gan yr egwyddor sawl cyffredinoliaeth a gellir ei nodi mewn sawl ffordd. Mewn fersiwn fwy meintiol: ar gyfer rhifau naturiol $k$ a $m$ , os yw $n=km+1$ gwrthrych yn cael eu dosbarthu ymhlith $m$ set, yna mae'r egwyddor dwll colomen yn honni y bydd o leiaf un o'r setiau'n cynnwys o leiaf $k+1$ gwrthrych.^[4]

Er mai'r cymhwysiad mwyaf syml yw setiau meidraidd (fel colomennod a blychau), fe'i defnyddir hefyd gyda setiau anfeidraidd na ellir eu rhoi mewn gohebiaeth un-i-un. I wneud hynny mae angen datganiad ffurfiol o'r egwyddor dwll colomen, sef "nid oes ffwythiant mewnsaethol yn bodoli y mae ei amrediad yn llai na'i barth". Mae profion mathemategol uwch fel lema Siegel yn adeiladu ar y cysyniad mwy cyffredinol hwn.

Enghreifftiau

Dewis hosanau

Tybiwch fod drôr yn cynnwys cymysgedd o sanau du a sanau glas, y gellir gwisgo pob un ohonynt ar y naill droed, a'ch bod yn tynnu nifer o sanau o'r drôr heb edrych. Beth yw'r nifer lleiaf o sanau sydd angen eu tynnu i sicrhau cael pâr o'r un lliw? Gan ddefnyddio'r egwyddor dwll colomen, i gael o leiaf un pâr o'r un lliw (m = 2 twll, un ar gyfer pob lliw) gan ddefnyddio un twll colomennod i bob lliw, mae angen i chi dynnu dim ond tair hosan o'r drôr (n = 3 eitem). Naill ai mae gennych chi dri o un lliw, neu mae gennych chi ddau o un lliw ac un o'r llall.

Ysgwyd llaw

Os oes n bobl sy'n gallu ysgwyd llaw â'i gilydd (lle mae $n > 1$ ), mae'r egwyddor dwll colomen yn dangos bod yna bob amser pâr o bobl a fydd yn ysgwyd llaw gyda'r un nifer o bobl. Wrth gymhwyso'r egwyddor, y 'twll' y mae person wedi'i aseinio iddo yw nifer y dwylo sy'n cael eu hysgwyd gan y person hwnnw. Gan fod pob person yn ysgwyd dwylo gyda rhyw nifer o bobl o 0 i $n - 1$ , ceir $n$ tyllau posibl. Ond, rhaid i'r twll '0' neu'r twll $' n - 1'$ , neu'r ddau fod yn wag - oherwydd mae'n amhosibl i ryw berson ysgwyd llaw â phawb arall tra bod rhywun arall yn ysgwyd llaw gyda neb. Felly mae hyn yn gadael $n$ o bobl i gael eu gosod ar y mwyaf mewn $n - 1$ o dyllau anwag - felly mae'r egwyddor yn berthnasol.

Cyfri gwallt

Gallwn ddangos bod yn rhaid bod o leiaf dau o bobl yn Llundain gyda'r un nifer o flew ar eu pennau.^[5] Gan fod gan ben dynol nodweddiadol oddeutu 150,000 o flew ar gyfartaledd, mae'n rhesymol tybio (fel amcangyfrif ar gyfer fin uchaf) nad oes gan unrhyw un fwy na 1,000,000 o flew ar eu pen $(m = 1 miliwn$ o dyllau). Mae mwy na 1,000,000 o bobl yn Llundain (mae $n$ yn fwy nag 1 miliwn). Mae'r egwyddor dwll colomen yn dweud felly bod o leiaf dau berson yn Llundain yn yr un twll, hynny yw gyda'r un nifer o flew ar eu pennau. Efallai y bydd tyllau colomen wag, ond mae'r egwyddor yn profi bodolaeth gorgyffwrdd yn unig; nid yw'n dweud dim am y nifer sy'n gorgyffwrdd.

Efallai taw'r cyfeiriad ysgrifenedig cyntaf at egwyddor dwll colomen oedd mewn brawddeg fer o'r gwaith Lladin Selectæ Propositiones, gan y Jeswit Ffrengig Jean Leurechon a ymddangosodd ym 1622,^[2] lle ysgrifennodd "Mae'n angenrheidiol bod gan ddau ddyn yr un nifer o flew, écus, neu bethau eraill, a'i ei gilydd."^[6] Cafodd yr egwyddor lawn ei nodi dwy flynedd yn ddiweddarach, gydag enghreifftiau ychwanegol, mewn llyfr arall a briodolwyd yn aml i Leurechon, ond a allai fod wedi'i ysgrifennu gan un o'i fyfyrwyr.

Y broblem pen-blwydd

Mae'r broblem pen-blwydd yn gofyn, ar gyfer set o $n$ bobl a ddewiswyd ar hap, beth yw'r tebygolrwydd y bydd rhai pâr ohonynt yn cael yr un pen-blwydd? Yn ôl yr egwyddor dwll colomen, os oes 367 o bobl yn yr ystafell, rydyn ni'n gwybod bod o leiaf un pâr sy'n rhannu'r un pen-blwydd, gan mai dim ond 366 o benblwyddi posib sydd i ddewis o'u plith (gan gynnwys Chwefror 29).

Cyfeiriadau

↑ Herstein 1964
↑ ^2.0 ^2.1 Rittaud, Benoît; Heeffer, Albrecht (2014). "The pigeonhole principle, two centuries before Dirichlet". The Mathematical Intelligencer 36 (2): 27–29. doi:10.1007/s00283-013-9389-1. MR 3207654. https://biblio.ugent.be/publication/4115264. Adalwyd 2020-03-31.
↑ Jeff Miller, Peter Flor, Gunnar Berg, and Julio González Cabillón. "Pigeonhole principle Archifwyd 2010-02-12 yn y Peiriant Wayback". In Jeff Miller (ed.) Earliest Known Uses of Some of the Words of Mathematics Archifwyd 2009-03-04 yn y Peiriant Wayback. Electronic document, retrieved November 11, 2006
↑ Fletcher & Patty 1987
↑ To avoid a slightly messier presentation we assume that "people" in this example only refers to people who are not bald.
↑ Leurechon, Jean (1622), Selecæe Propositiones in Tota Sparsim Mathematica Pulcherrimæ, Gasparem Bernardum, p. 2

Brualdi, Richard A. (2010), Introductory Combinatorics (5th ed.), Pentice Hall, ISBN 978-0-13-602040-0
Fletcher, Peter; Patty, C.Wayne (1987), Foundations of Higher Mathematics, PWS-Kent, ISBN 978-0-87150-164-6
Grimaldi, Ralph P. (1994), Discrete and Combinatorial Mathematics: An Applied Introduction (3rd ed.), Addison-Wesley, ISBN 978-0-201-54983-6, https://archive.org/details/discretecombinat00grim_1
Herstein, I. N. (1964), Topics In Algebra, Waltham: Blaisdell Publishing Company, ISBN 978-1114541016

[Herstein64-1] Herstein 1964

[leurechon-2] 2.0 ^2.1 Rittaud, Benoît; Heeffer, Albrecht (2014). "The pigeonhole principle, two centuries before Dirichlet". The Mathematical Intelligencer 36 (2): 27–29. doi:10.1007/s00283-013-9389-1. MR 3207654. https://biblio.ugent.be/publication/4115264. Adalwyd 2020-03-31.

[3] Jeff Miller, Peter Flor, Gunnar Berg, and Julio González Cabillón. "Pigeonhole principle Archifwyd 2010-02-12 yn y Peiriant Wayback". In Jeff Miller (ed.) Earliest Known Uses of Some of the Words of Mathematics Archifwyd 2009-03-04 yn y Peiriant Wayback. Electronic document, retrieved November 11, 2006

[4] Fletcher & Patty 1987

[5] To avoid a slightly messier presentation we assume that "people" in this example only refers to people who are not bald.

[6] Leurechon, Jean (1622), Selecæe Propositiones in Tota Sparsim Mathematica Pulcherrimæ, Gasparem Bernardum, p. 2

[1]

[2]

[3]

[4]

[5]

[6]