Page 17 - Tuzson - Hogyan oldjunk - mutatvany

Érdemes hangsúlyozni, hogy a szóban forgó, úgynevezett reductio ad absurdum módsze-
re sok közös vonást mutat a 9. fejezetben bemutatásra kerülő hipotézisek módszerével. Erről
az illető fejezet átolvasása után jobban meggyőződhetünk.
A továbbiakban térjünk ki egy másik (gyakran használt) általános bizonyítási (megol-
dási) módszerre.
4.2. A skatulyaelv (Dirichlet-elv)
A skatulyaelv megalkotója Peter Gustav Lejeune Dirichlet (1805–1859) német mate-
matikus. Matematikai tehetsége korán megmutatkozott. Eredményei elsősorban az analízisben
és a számelméletben jelentősek.
A skatulyaelv leegyszerűsített megfogalmazása a következő: ha n skatulyában n-nél több
tárgyat akarunk tenni, akkor lesz legalább egy olyan skatulya, amelybe legalább két tárgy
kerül.
Annak ellenére, hogy az elv alapgondolata nagyon egyszerű, segítségével számtalan ne-
héznek tűnő problémát meg tudunk oldani a matematika legkülönbözőbb területéről.
Belátható, hogy az elv indirekt módszer, ugyanis ha feltételezzük, hogy minden skatu-
lyába legfeljebb egy tárgy van, akkor n skatulyába legfeljebb n  1 = n, ami ellentmond a felté-
telnek. Így az ellentmondásra való visszavezetés elve alapján lesz olyan skatulya, melyben
legalább két tárgy lesz.
Feladatmegoldásaink során gyakran az elv alábbi két módosított változatát alkalmazzuk:
1. változat (véges halmazokra)
Adott n skatulya és k  n + r (r > 0) tárgy. Ha elhelyezzük a tárgyakat, akkor lesz legalább
egy olyan skatulya, amelyben legalább k + 1 tárgy van.
2. változat (végtelen halmazokra)
Ha n skatulyában végtelen sok tárgyat akarunk elhelyezni, akkor lesz legalább egy olyan,
amelyben végtelen sok tárgy van, azaz nem lehet mindegyikben véges sok.
A következő feladatot a skatulyaelv segítségével oldjuk meg.
2. feladat
Egy erdőben több mint 3720 fa van. Legfeljebb egytizedük 30 méternél magasabb, és
legfeljebb egyötödük négy méternél alacsonyabb. Bizonyítsuk be, hogy van legalább két olyan
fa, amelyeknek magassága ugyanakkora!
Bizonyítás
A 4 m és 30 m között (beleszámítva a 4-et és 30-at is) összesen 3001 – 400 = 2601 cm
van. Legfeljebb 3720 : 10 = 372 fa magasabb 30 m-nél, és legfeljebb 3720 : 50 = 744
alacsonyabb 4 m-nél. Tehát legalább 3720 – 372 – 744 = 2604 fa magassága 4 és 30 m közötti.
Alkalmazva a skatulyaelvet (2601 db skatulyánk és legalább 2604 tárgyunk van) kapjuk, hogy
van két fa, amelyeknek magassága ugyanakkora.
3. feladat
A 31-es létszámú osztályban mindenki írt matematikadolgozatot. A dolgozatot jeggyel
értékelték: 1-től 10-ig. Igazold, hogy volt legalább 4 tanuló, akik azonos jegyet kaptak!
Bizonyítás
A feladat a skatulyaelv első változata segítségével oldható meg. A skatulyák itt az
érdemjegyek (tehát n = 10). Mivel az osztályban 31 = 3  10 + 1 tanuló van (tehát k = 3), így az
említett 1. változat értelmében legalább 3 + 1 = 4 tanuló kapott azonos jegyet.
4. feladat
Legkevesebb hány tanulója van annak az iskolának, amely tanulói között biztosan van 3,
akik ugyanazon a napon születtek?

17