„Skatulyaelv” változatai közötti eltérés

 

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 [[Halmazelmélet|véges halmazokon]] értelmezett [[injektív függvény]], amelynek az [[értékkészlet]]e kisebb, mint az [[értelmezési tartomány]]a.

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.

 

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.

Öt lány [[softball]]t 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.

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.

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.

 

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.

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ám]]hoz, sőt, törtrészeik [[sűrű halmaz|sűrűek]] [0,1]-ben.

 

Ez azt jelenti, hogy n₁α ∈ (p + k/M, p + (k + 1)/M), és n₂α ∈ (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 (n₁-n₂)α 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 pont]]ja 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 < ε.

 

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

 

 

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

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

 

 

:<math>1 - \frac{(m)_n}{m^n}, \!</math>

 

 

Még ha 1 < ''n'' ≤ ''m'' 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]].

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ék]]e véges, akkor legalább ½ annak a valószínűsége, hogy ''X'' ≥ ''E''(''X''), és fordítva, legalább ½ annak a valószínűsége, hogy ''X'' ≤ ''E''(''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ő.

* Grimaldi, Ralph P. ''Discrete and Combinatorial Mathematics: An Applied Introduction''. 4th edn. 1998. ISBN 0-201-19912-2. pp.&nbsp;244–248.

* "[http://www.cs.utexas.edu/users/EWD/transcriptions/EWD09xx/EWD980.html The strange case of The Pigeon-hole Principle]"; [[Edsger Dijkstra]] a skatulyaelvről.

* "[http://zimmer.csufresno.edu/~larryc/proofs/proofs.pigeonhole.html The Pigeon Hole Principle]"; Larry Cusick: Elemi példák az elvre.