Feladat: 2001. évi Nemzetközi Matematika Diákolimpia 13. feladata Korcsoport: 18- Nehézségi fok: nehéz
Megoldó(k):  Vörös László 
Füzet: 2001/október, 391. oldal  PDF  |  MathML 
Témakör(ök): Kombinatorikai leszámolási problémák, Szöveges feladatok, Nemzetközi Matematikai Diákolimpia
Hivatkozás(ok):Feladatok: 2001/szeptember: 2001. évi Nemzetközi Matematika Diákolimpia 13. feladata

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.

Készítsünk egy 21×21-es táblázatot, amelynek oszlopai jelentsék az egyes fiúkat, míg a sorok a résztvevő lányokat. A táblázat minden egyes mezőjébe írjuk be annak a feladatnak a sorszámát, amelyet mind az oszlophoz tartozó fiú, mind a sorhoz tartozó lány megoldott.
(2) szerint ilyen feladat mindig létezik. (Ha több is van, akkor elég az egyik ilyen feladat sorszámát beírni.) Az ábrán látható 5-ös szám például azt jelenti, hogy az 5. feladatot a 2. számú fiú és a 3. számú lány is megoldotta.
Ezek után vizsgáljuk az egyes oszlopokat. Fessük be kékre azokat a mezőket, amelyeken olyan szám áll, amelyik az adott oszlopban legalább háromszor előfordul.
Mivel az (1) feltétel szerint minden oszlopban legfeljebb hatféle szám szerepelhet, azért:

ha egy adott oszlopban

*‐egyféle számot festettünk be, akkor a többi maximum (6-1)⋅2=10 mezőt fed le, tehát legalább 11 kék mezőnk van;
*‐kétféle számot festettünk be, akkor a be nem festettek száma maximum (6-2)⋅2=8, azaz legalább 13 kék mező van;
*‐háromféle kék szám esetén minimum 15 kék mező van;
*‐4, 5, 6-féle kék szám esetén is legalább 4⋅3, 5⋅3, 6⋅3, azaz 12, 15 és 18 mezőt festettünk be.
Összefoglalva: láthatjuk, hogy minden oszlopban legalább 11 kék mező van, ez pedig 21 oszlop esetén már több, mint a mezők fele (21⋅11>2122+0,5).
Most vizsgáljuk a sorokat, és fessük pirosra egy adott soron belül azokat a mezőket, amelyeken szereplő számok legalább háromszor fordulnak elő az adott sorban.
Ekkor ugyanúgy belátható, hogy a mezők több, mint fele piros. A skatulya-elv miatt lesz tehát olyan mező, amelyik kék is és piros is, és ez azt jelenti, hogy az ezen mezőkhöz tartozó feladatot legalább három lány (mert a mező kék) és legalább 3 fiú (mert a mező piros) megoldotta.
 Vörös László (Győr, Révai M. Gimn., 12. o.t.)