Főmenü megnyitása
A skatulyaelv szemléltetése galambokkal. n (= 10) galamb m (= 9) lyukban, ezért lesz lyuk, amibe több galamb jut.

A skatulyaelv az a Dirichlet által megfogalmazott matematikai tétel, mely szerint ha n és m pozitív egészek és n>m, akkor n elemet m skatulyába helyezve kell lennie olyan skatulyának, amelyben 1-nél több elem van. Az elv végtelen halmazokra is alkalmazható, csak ilyenkor elemszám helyett számosságot kell használni.

Másképpen megfogalmazva: nem létezik olyan véges halmazokon értelmezett injektív függvény, amelynek az értékkészlete kisebb elemszámú, mint az értelmezési tartománya.

BizonyításSzerkesztés

A skatulyaelv indirekt módon bizonyítható: ha az elv nem igaz, akkor minden skatulyába legfeljebb egy elem kerül. Ekkor legfeljebb annyi elem van, ahány skatulya. Ellentmondás.

PéldákSzerkesztés

HajszálszámSzerkesztés

Egyszerűsége ellenére a skatulyaelvvel érdekes következtetésekre lehet jutni, például, hogy van legalább két budapesti lakos, akiknek pontosan ugyanannyi szál haja van.

A bizonyításhoz mindenkihez hozzárendeljük a hajszálaik pontos számát. Egy ember hajszálainak száma általában 100 000 és 200 000 közötti. Feltehetjük, hogy senkinek sincs egy milliónál több hajszála. Márpedig Budapesten több, mint egy millióan laknak.

SoftballSzerkesztés

Öt lány softballt akar játszani, de nem akarnak ugyanabba a csapatba kerülni, és csak négy csapatba jelentkezhetnek. Mivel lehetetlen az öt lányt úgy elosztani a négy csapat között, hogy mindegyikbe legfeljebb egy jusson, így a skatulyaelv szerint lesz, aki hoppon marad.

Zoknik példájaSzerkesztés

Legyen egy fiókban 10 fekete és 12 fehér zokni. Sorra vesszük ki a zoknikat úgy, hogy nem nézünk a dobozba. Legalább hány zoknit kell kivenni, hogy legyen köztük egy pár?

VálaszSzerkesztés

Mivel két kategória van, ezért a "legrosszabb" esetben két különböző színű zoknit vettünk ki. Ebben az esetben egy harmadik zokni már valamelyik foglalt kategóriába kell kerüljön, így három zokni esetén biztosan van egy pár.

Legyen B a fekete, W a fehér zokni jelölése. Ha egy zoknit választunk, akkor tuti nincsen pár, tehát ezzel az esettel nem foglalkozunk.

Két zokni esetén a lehetőségeink: BB, WW és BW, tehát van, hogy nincs két egyforma.

Három zokni esetén a lehetőségek: BBB, BBW, BWW és WWW, mindegyik esetben van két egyforma betű, tehát három zokni esetén mindig van egy pár.

KézfogásSzerkesztés

Ha n > 1 ember kezet fog egymással, akkor mindig lesz közöttük kettő, akik ugyanannyiszor fogtak kezet.

A kézrázások lehetséges száma nullától n-1-ig terjed, n-1 skatulyát alkotva. Ez azért van, mert vagy a nullaszor, vagy az n-1-szer kezet fogók halmaza üres, mivel, ha van, aki mindenkivel kezet fogott, akkor nem lehet senki, aki nem fogott kezet senkivel, és fordítva. Az n embert elosztva az n-1 skatulya között lesz skatulya, ahova több ember kerül.

AlkalmazásokSzerkesztés

SzámítástechnikaSzerkesztés

A számítástechnikában is előkerül a skatulyaelv.

Például, mivel egy tömbnek kevesebb eleme van, mint ahány lehetséges kulcs, ezért nincs hash-elő algoritmus, amivel el lehetne kerülni az ütközéseket. Egy másik példát a veszteségmentes tömörítő algoritmusok adnak, amik egyes fájlokat tömörítenek, másokat meg épp hosszabbá tesznek.

AnalízisSzerkesztés

A matematikai analízis egy fontos tétele szerint az α irracionális szám egész számú többszörösei tetszőlegesen közel kerülnek egy egész számhoz, sőt, törtrészeik sűrűek [0,1]-ben.

Elsőre ez nem nyilvánvaló, mert hogyan találjunk adott ε > 0-hoz olyan n, m egész számokat, amikre |nα − m| < ε? A feladat azonban megoldható egy M > 1/ε választásával. A skatulyaelv szerint van n1, n2∈ {1, 2, ..., M + 1}, hogy n1α és n2α törtrésze ugyanabba az 1/M hosszú részintervallumba esik. Ez azt jelenti, hogy n1α ∈ (p + k/M, p + (k + 1)/M), és n2α ∈ (q + k/M, q + (k + 1)/M) valami p, q egészekre és k eleme {0, 1, ..., M − 1}-re. Innen könnyű látni, hogy (n1-n2)α benne van (q − p − 1/M, q − p + 1/M)-ben, ahonnan következik, hogy {nα} < 1/M < ε. Ebből látszik, hogy 0 torlódási pontja az {nα} sorozatnak. A többi p torlódási pontra: válasszunk egy n egészet, hogy {nα} < 1/M < ε legyen; ekkor, ha p ∈ (0, 1/M], akkor készen vagyunk. Különben p benne vagy egy (j/M, (j + 1)/M] intervallumban, és ha k választása k = sup{r ∈ N : r{nα} < j/M}, akkor kapjuk, hogy |[(k + 1)nα] − p| < 1/M < ε.

ÁltalánosításSzerkesztés

A skatulyaelv így általánosítható:

Ha n elemet k halmazba osztunk, és n > k, akkor van legalább egy halmaz, ami legalább (n-1)/k elemet tartalmaz.

Az elv kombinatorikus általánosításaival a Ramsey-elmélet foglalkozik.

Véletlenített általánosításSzerkesztés

A skatulyaelv egy véletlenített általánosítása így hangzik:

Ha n galambot m galambdúcban helyezünk el úgy, hogy minden galamb egymástól függetlenül egyenletes eloszlás szerint kerül az m galambdúc egyikébe, akkor annak az esélye, hogy lesz olyan galambdúc, amibe több galamb is kerül,

 

ahol (m)n=m(m − 1)(m − 2)...(mn + 1). Ha n legfeljebb 1, akkor egybeesés nem lehetséges; egyébként, valahányszor n > m, a skatulyaelv szerint az egybeesés elkerülhetetlen.

Még ha 1 < nm is, a választás véletlenszerűsége miatt gyakoriak lesznek az egybeesések. Például, ha két galambot osztunk így szét négy galambdúc között, 25% lesz annak az esélye, hogy legalább két galamb ugyanabba a dúcba kerül. Öt galambra és tíz dúcra ez már 69,76%, és tíz galambra és húsz dúcra 93,45%. Ha rögzítjük a dúcok számát, akkor minél több galambot veszünk, annál nagyobb eséllyel kerül több galamb is egy dúcba. Ez a születésnap-paradoxon.

Valószínűségszámítási általánosításSzerkesztés

A véletlenített általánosítás további általánosításának tekinthető az az elv, hogy az X valós valószínűségi változó E(X) várható értéke véges, akkor legalább ½ annak a valószínűsége, hogy XE(X), és fordítva, legalább ½ annak a valószínűsége, hogy XE(X).

Ez valóban a skatulyaelv általánosítása: tekintsük ugyanis a galambok egy elrendezését, és válasszunk egyenletes valószínűséggel egy dúcot. Az X valószínűségi változó legyen az ebben a dúcban levő galambok száma. X várható értéke n/m, ami egynél nagyobb, ha több galamb van, mint dúc. Kell, hogy X értéke néha egynél nagyobb legyen; ez az egész értékűség miatt azt jelenti, hogy ilyenkor legalább kettő.

ForrásokSzerkesztés