Skatulyaelv

A Wikipédiából, a szabad enciklopédiából
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 elv, 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ás[szerkesztés | forrásszöveg szerkesztése]

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ák[szerkesztés | forrásszöveg szerkesztése]

Hajszálszám[szerkesztés | forrásszöveg szerkesztése]

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.

Softball[szerkesztés | forrásszöveg szerkesztése]

Ö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[szerkesztés | forrásszöveg szerkesztése]

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

A skatulyaelv szerint, mivel két szín van, ezért a harmadik zokni színe meg fog egyezni egy korábban kihúzott zokniéval. Ha tehát az első két zokni különböző színű, akkor a következő zokni már párt alkot valamelyikkel.

Kézfogás[szerkesztés | forrásszöveg szerkesztése]

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ások[szerkesztés | forrásszöveg szerkesztése]

Számítástechnika[szerkesztés | forrásszöveg szerkesztése]

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 hashelő 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ízis[szerkesztés | forrásszöveg szerkesztése]

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ás[szerkesztés | forrásszöveg szerkesztése]

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ás[szerkesztés | forrásszöveg szerkesztése]

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,

1 - \frac{(m)_n}{m^n}, \!

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ás[szerkesztés | forrásszöveg szerkesztése]

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ások[szerkesztés | forrásszöveg szerkesztése]