Page 187 - vol1

meglévő n skatulya valamelyikébe kerül, tehát legalább egy skatulyába legalább
k+1 darab tárgy lesz.
A skatulya-elvnek van indirekt formája is: Amikor nem sikerül
bizonyítani direkt módon, hogy valamelyik skatulyában legalább 1-gyel több
tárgy lesz mint a többibe, akkor tagadjuk a konklúziót, és akkor a feltevéssel
ellentmondásra jutunk, ami abból adódik, hogy nem fogadtuk el a konklúziót
(hogy egyik skatulyába legalább 2 tárgy van), tehát az állítás igaz kell legyen,
miszerint egyik skatulyába legalább 1-gyel több tárgy van.
Nézzünk most néhány példát, aztán néhány megoldott feladatot!

1. példa: Egy iskolába 367 diák jár. Bizonyítsuk be, hogy van legalább 2 diák, akik
ugyanazon a napon ünneplik a születésnapjukat.

Valóban, jelen esetben a skatulyák az év 366 napja, és a tárgyak a 367
tanuló. Mivel 367=366+1, ezért az állítás nyilvánvaló.

2. példa: Legalább hány fős az az osztály, ahol teljesül, hogy van legalább 6
tanuló, akik a hétnek ugyanazon a napján születtek?
Vizsgáljuk a legrosszabb
esetet, amikor a hét minden
napján legtöbb 5 tanuló született:

Ekkor legalább 5×5+1=26 tanuló kell legyen az osztályban!

3. példa: Ha 6 dobozba szétosztunk 13 tárgyat, akkor bizonyítsuk be, hogy van
legalább 1 doboz, amelyikbe 3 tárgy kerül!
Valóban, a legrosszabb esetet vizsgálva, ha minden dobozba csak 2-2
tárgy jut, akkor ez összesen6×2=12 tárgy, de még van 1 tárgy, így valamelyik
dobozba 3 tárgy jut.

4. példa: Egy urnában 15 zöld és 13 piros golyó van.
Véletlenszerűen kihúzunk néhányat közülük.
Legalább hányat kell kihúzzunk, hogy a kihúzott
golyók között biztosan legyen 3 zöld és 2 piros?

187