Page 186 - vol1

22. A skatulya-elv és alkalmazása

A nálunk meghonosodott skatulya-elv elnevezést különböző
országokban különbözőképpen nevezik. Például Franciaországban úgy ismerik,
mint a “fiókok elvét”, Angliában mint a “galambdúcok
elvét” míg Bulgáriában és Oroszországban mint
Dirichlet-elvet. Az elv a nagy német matematikussal,
Gustav Lejeune Dirichlet-el (1805 – 1859) áll
kapcsolatban, bár már előtte is jól ismerték az elvet.
Dirichlet érdeme nem az előbbi egyszerű tény
felfedezése volt, hanem az alkalmazása számos
érdekes probléma megoldásában a számelmélet
terén.

A “skatulya nyelvét” használva, a skatulya-elv kimutatja egy bizonyos
tulajdonságokkal rendelkező skatulya létezését. Így ez tulajdonképpen a létezés
bizonyítása. Azonban ez az elv nem ad egy algoritmust arra, hogy meg is találjuk
a kívánt skatulyát, és következésképpen nem konstruktív tulajdonságú. Ugyanis,
a létezés konstruktív bizonyítása közelebb áll a gondolkodáshoz és meggyőzőbb.
Úgy tűnik, hogy ez a legfőbb oka annak, hogy a skatulyaelv számos alkalmazásra
váratlannak tűni.

A skatulya-elv leg egyszerűbb megfogalmazása:
1. változat: ha m tárgyat szétosztunk n skatulyába és m > n, akkor legalább két
tárgy azonos skatulyába fog kerülni.
A bizonyítása indirekt módszerrel a következő: feltételezzük a
legrosszabb esetet, vagyis, hogy minden skatulyában legtöbb 1 tárgy kerül.
Akkor az n skatulyába összesen n tárgy lesz, és még marad m n−  1 tárgy,
amelyet (amelyeket) az n skatulya közül valamelyikbe kell helyezzük, így
legalább két tárgy azonos skatulyába fog kerülni.
Az általánosabb változat a következő:
2. változat: ha nk+r tárgyat szétosztunk n skatulyába és r  1, akkor legalább egy
skatulyába legalább k+1 darab tárgy lesz.
A bizonyítás az előbbivel azonos, megint a legrosszabb esetet tekintve,
ha mindegyik skatulyában legfeljebb k tárgy lenne, mivel n darab skatulyánk van,
ez csak nk tárgyat jelent, és még van r  1 tárgy, amelyből valamelyik a már

186