Feladat: B.3890 Korcsoport: 16-17 Nehézségi fok: nehéz
Megoldó(k):  Véges Márton 
Füzet: 2007/március, 148. oldal  PDF  |  MathML 
Témakör(ök): Szöveges feladatok, Skatulyaelv, Indirekt bizonyítási mód, Feladat
Hivatkozás(ok):Feladatok: 2006/február: B.3890

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.

I. megoldás. Tegyük fel, hogy van két olyan tudós, akik nem beszélnek közös nyelvet. Mivel bármely három ember közt van kettő, akik megértik egymást, így ha ehhez a két emberhez kiválasztunk még egy harmadikat, akkor ő beszél közös nyelvet a két ember valamelyikével. Ezen a két emberen kívül még 198 van, így a két ember valamelyike legalább 99 emberrel beszél közös nyelvet; nevezzük ezek egyikét A-nak. Mivel egy ember legfeljebb 4 nyelvet beszél, a skatulya-elv alapján ebből a 99 emberből legalább 25 beszél egy közös nyelvet. Az A-t is beleszámítva tehát van 26 ember, aki egy nyelvet beszél.
Ha nincs két olyan ember, aki nem érti meg egymást, akkor mindenki mindenkivel tud beszélgetni. Válasszunk ki egy B embert; ekkor ő 199 emberrel tud beszélni. Mivel egy ember legfeljebb 4 nyelvet beszél, ismét a skatulya-elv alapján B legalább 50 emberrel beszél egy bizonyos nyelven.
Mindkét esetben beláttuk, hogy van olyan nyelv, amit legalább 26-an beszélnek.

 
II. megoldás. Tegyük fel, hogy ‐ a feladat állításával ellentétben ‐ minden nyelvet a résztvevők közül legfeljebb 25-en beszélnek. Vegyünk közülük egyet, A-t, ő bármelyik általa beszélt nyelven legfeljebb 24 másik tudóssal tud kommunikálni; ez azt jelenti, hogy van legalább 200-424-1=103 tudós, aki nem beszél A-val közös nyelven. Ha ezek egyike B, akkor B is legfeljebb 424=96 másik tudóssal tud beszélni, marad tehát legalább 103-96-1=6 olyan, aki sem A-val, sem B-vel nem beszél közös nyelvet. Ha egyikük C, akkor A, B, C közül semelyik kettő nem beszél közös nyelvet, ami ellentmond a feladat feltételének.