Feladat: F.2910 Korcsoport: 16-17 Nehézségi fok: átlagos
Megoldó(k):  Futó Gábor 
Füzet: 1993/február, 61. oldal  PDF file
Témakör(ök): Részhalmazok, Kombinatorikai leszámolási problémák, Variációk, Feladat
Hivatkozás(ok):Feladatok: 1992/május: F.2910

Egy iskolában a tanulók 10 fős csapatokat szerveztek. Egy diák több csapatnak is tagja lehet, vagy akár egyiknek sem. A csapatok száma 500. Bizonyítsuk be, hogy a diákokat el lehet helyezni két terembe úgy, hogy minden csapatnak mindkét teremben legyen tagja.

A szöveg csak Firefox böngészőben jelenik meg helyesen. Használja a fenti PDF file-ra mutató link-et a letöltésre.

Legyen a diákok száma n. Ha csak annyi lenne a feladat, hogy osszuk el őket két terembe, azt 2n lehetséges módon tehetnénk meg, mert az egyes diákokról egymástól teljesen függetlenül kellene eldöntenünk, hogy az első vagy a második terembe helyezzük el őket. Ezek között azonban vannak ,,rossz'' elhelyezések, amelyekben valamelyik (vagy több) csapatnak minden tagja ugyanabba a terembe kerül. Megmutatjuk, hogy a rossz elhelyezések száma kisebb, mint 2n; ebből következik, hogy létezik jó elhelyezés is.
Tekintsünk egy tetszőleges csapatot, és számítsuk ki, hány olyan rossz elhelyezés van, amikor ennek a csapatnak minden tagja ugyanabba a terembe kerül. Először el kell döntenünk, melyik ez a terem; ez 2 lehetőség. Ezután a többi n-10 embert szét kell osztanunk, amit 2n-10-féleképpen tehetünk meg. Összesen tehát 22n-10=2n-9 olyan rossz elhelyezés van, amikor egy kiszemelt csapat minden tagját ugyanabban a teremben helyeztük el.
500 csapat lévén, az összes rossz elhelyezések száma legfeljebb 5002n-9. (Azokat a rossz elhelyezéseket, amikor több olyan csapat is van, amelynek minden tagja egyazon terembe jut, többször is számoltuk.)
Mivel 5002n-9=5005122n<2n, a feladat állítása igaz.