Feladat: 1950. évi Kürschák matematikaverseny 1. feladata Korcsoport: 18- Nehézségi fok: nehéz
Megoldó(k):  Korányi Ádám ,  Szekerka Pál ,  Wellisch Tibor ,  Zergényi Erzsébet 
Füzet: 1951/május, 4 - 5. oldal  PDF  |  MathML 
Témakör(ök): Részhalmazok, Kombinatorikai leszámolási problémák, Logikai feladatok, Kürschák József (korábban Eötvös Loránd)
Hivatkozás(ok):Feladatok: 1951/május: 1950. évi Kürschák matematikaverseny 1. 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.

I. megoldás: Nézzük először azt az esetet, ha az olvasók közül bármelyik kettő találkozik a könyvtárban. Ekkor az utolsó érkezésétől az első távozásáig bármely időpontban az olvasók mindegyike a könyvtárban van. Ebben az esetben az először távozó olvasó is bevárja az utoljára érkezőt.
Ha nem találkozik mindegyik mindegyikkel a könyvtárban, akkor válasszunk ki két olyan olvasót, akik nem találkoznak, legyenek ezek a és b. A többi olvasót 3 csoportra oszthatjuk. Az első csoportba tartoznak azok, akik találkoznak a-val, de b-vel nem. Ez legyen az A csoport. A másodikba tartoznak azok, akik nem találkoznak a-val, csak b-vel. Ez legyen a B csoport. A harmadikba azok tartoznak, akik mindkettővel találkoznak. Ez legyen a C csoport. Minden könyvtárlátogató beletartozik e csoportok valamelyikébe, mert ha lenne olyan c látogató, aki sem a-val sem b-vel nem találkozna, így a, b, c nem találkoznak a könyvtárban, de ez a feltevés szerint nem fordul elő. Most C azon egyedeit, kik A minden egyedével találkoznak osszuk az A csoportba, akik B minden egyedével, azokat osszuk B-hez. Akik az A csoportnak is, B csoportnak is minden tagjával találkoznak, azokat bármelyikhez oszthatjuk. Az eredeti A csoportban bármely látogatónak kellett találkoznia, mert ha ketten nem találkoztak volna, akkor ők b-vel oly hármast alkotnának, akik nem találkoznak a könyvtárban. A C csoport tagjai szintén mind találkoznak egymással, hisz az a eltávozása és b megérkezése közötti időben mind bent kell hogy legyenek a könyvtárban. Viszont a C csoport azon tagjai, akikkel az A csoportot kibővítettük, mind találkoznak az A csoport tagjaival, így a kibővített A csoport minden tagja találkozik egymással, tehát van oly időpont, amint már láttuk; mikor mindnyájan a könyvtárban vannak. Ugyanígy látható be, hogy van egy oly időpont is, amikor a kibővített B csoport tagjai mind a könyvtárban vannak. E két időpont olyan, hogy bármely egyén e két időpontnak legalább egyikében a könyvtárban tartózkodik. A C csoport minden egyede találkozik vagy az A vagy a B csoport minden egyedével. Mert ha lenne a C csoportnak egy olyan c' egyede, aki az A csoport egyik egyedével a'-vel és a B csoport egyik egyedével b'-vel nem találkozna, akkor a' sem találkozhatna b'-vel ‐ hiszen, mivel c' nem találkozik sem a'-vel, sem b'-vel, a' előbb menne el, mint c' megérkezik, és b' később érkezne meg, mint c' elmenne ‐ így volna 3 olyan egyed, ugyanis a', b', c', akik egyáltalában nem találkoznának.

 
II. megoldás: Tekintsük azt a pillanatot, mikor az első olvasó eltávozik és azt a pillanatot, mikor az utolsó megérkezik. Ha valaki e két időpillanat egyikében sem volna ott, az csak úgy lehetne, ha az első eltávozása után érkezne ‐ hiszen előtte nem távozhat ‐ és az utolsó érkezése előtt távozna el ‐ hiszen utána nem érkezhet. Ez esetbén azonban ő, az első távozó és az utolsó érkező nem találkozna, ami ellentmond a feltevésnek.
 
III. megoldás: Képzeljük el a feladatot úgy, hogy a könyvtár portása utasítást kapott, hogy egy hirdetést olvasson fel két ízben, de úgy, hogy mégis minél többen hallják. Mikor válik szükségessé az első felolvasás? Nyilván akkor, amikor az első egyén távozni akar. És mikor kell másodszor felolvasni? Világos, hogy akkor, amikor azok közül, akik az első felolvasást nem hallották (tehát az első távozó után érkeztek) valaki távozni akar. Ha emellett teljesül a feladat kikötése is, akkor nem lehet, hogy valaki is ne hallotta volna a hirdetést, mert annak e két felolvasás után kellett volna jönnie, de ez esetben, ő, az első távozó, és az azután érkezők közül először távozó látogató közül senki senkivel sem találkozott volna.
 
Megjegyzés: E harmadik megoldás készen adja a feladat általánosításának bizonyítását is: ha n tetszőleges pozitív egész szám és azt tesszük fel, hogy (3 helyett) bármely n látogató közül találkozik legalább kettő a könyvtárban, akkor létezik olyan n-1 időpont, hogy minden látogató ezek valamelyikében a könyvtárban van.