Skúffuregla Dirichlets

Úr Wikipediu, frjálsa alfræðiritinu

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 minnst að kosti ein skúffan að innihalda fleiri en einn hlut. Viðfang reglunar 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.

[breyta] Óbein sönnun

Gerum ráð fyrir því að engin skúffa inniheldur meira en \left\lceil \frac{k}{N} \right\rceil - 1 hluti. Þá er heildarfjöldi hluta að hámarki

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

þar sem að ójafnan \left\lceil \frac{k}{N} \right\rceil < \left( \frac{k}{N} + 1 \right) er notuð. Þetta leiðir til mótsagnar þar sem að um k hluti er að ræða.

[breyta] 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.

[breyta] Tenglar

Þessi grein er stubbur sem ekki hefur verið settur í undirflokk.
  Þú getur hjálpað til með því að bæta við hana, eða með því að flokka hana betur.