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.
↑ Jeff Miller, Peter Flor, Gunnar Berg, and Julio González Cabillón. "Pigeonhole principle". In Jeff Miller (ed.) Earliest Known Uses of Some of the Words of Mathematics. 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.

[3] Jeff Miller, Peter Flor, Gunnar Berg, and Julio González Cabillón. "Pigeonhole principle". In Jeff Miller (ed.) Earliest Known Uses of Some of the Words of Mathematics. 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]