Skatulyaelv

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.

A skatulyaelv szemléltetése galambokkal. n (= 10) galamb m (= 9) lyukban, ezért lesz lyuk, amibe több galamb jut.

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

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

Hajszálszám

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

Ö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ája

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álasz

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á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ások

Számítástechnika

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ízis

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 n₁, n₂∈ {1, 2, ..., M + 1}, hogy n₁α és n₂α törtrésze ugyanabba az 1/M hosszú részintervallumba esik. 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 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

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

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)...(m − n + 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 < 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.

Valószínűségszámítási általánosítá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 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ő.

Források

• Grimaldi, Ralph P. Discrete and Combinatorial Mathematics: An Applied Introduction. 4th edn. 1998. ISBN 0-201-19912-2. pp. 244–248.
• Jeff Miller, Peter Flor, Gunnar Berg, and Julio González Cabillón. "Pigeonhole principle". In Jeff Miller (ed.) Earliest Known Uses of Some of the Words of Mathematics. Hozzáférés: November 11, 2006.
• "The strange case of The Pigeon-hole Principle"; Edsger Dijkstra a skatulyaelvről.
• "The Pigeon Hole Principle"; Larry Cusick: Elemi példák az elvre.
• "Pigeonhole Principle from Interactive Mathematics Miscellany and Puzzles"; Alexander Bogomolny elemzése és példái.
• "The Puzzlers' Pigeonhole"; Alexander Bogomolny az elv fontosságáról az analízisben.