Skúffuregla Dirichlets

Skúffuregla Dirichlets er regla sem segir að; ef k hlutir eru settir í N skúffur, þar sem k > N (hlutirnir eru fleiri en skúffurnar), þarf að minnsta kosti ein skúffan að innihalda fleiri en einn hlut. Viðfang reglunnar er mikilvægt í talnafræði.

Höfundur þessarrar reglu, G. Lejeune Dirichlet, notaði samlíkingu við dúfur (k) og dúfnaholur (N) og því er reglan kölluð „the pigeonhole principle“ á ensku (einnig þekkt sem „Dirichlet's Box Principle“). Á íslensku hefur myndast sú hefð að kalla þetta skúffureglu.

Almenna skúffureglan er þannig: Ef að k hlutir eru settir í N skúffur, þá er að lágmarki til ein skúffa sem inniheldur $\left\lceil {\frac {k}{N}}\right\rceil$ hluti.

Óbein sönnun

Gerum ráð fyrir því að engin skúffa innihaldi fleiri en $\left\lceil {\frac {k}{N}}\right\rceil -1$ hluti. Þá er samanlagður fjöldi hluta í skúffum lægri en k.

$N\left(\left\lceil {\frac {k}{N}}\right\rceil -1\right)<N\left(\left({\frac {k}{N}}+1\right)-1\right)=N\left({\frac {k}{N}}+1-1\right)=k$,

þar sem að ójafnan $\left\lceil {\frac {k}{N}}\right\rceil <\left({\frac {k}{N}}+1\right)$ er notuð. Þetta er mótsögn: k hlutir voru upphaflega settir í skúffurnar og eru þar enn. Því hlýtur að vera til skúffa sem inniheldur fleiri en $\left\lceil {\frac {k}{N}}\right\rceil -1$ hluti. Sú skúffa inniheldur að lágmarki $\left\lceil {\frac {k}{N}}\right\rceil$ hluti.

Dæmi

Í 100 manna hópi eru að lágmarki $\left\lceil {\frac {100}{12}}\right\rceil =9$ manns sem eiga afmæli í sama mánuði.

Tenglar

• Pigeonhole Principle
• Einföld útskýring á MathWorld

  Þessi grein er stubbur. Þú getur hjálpað til með því að bæta við greinina.