Előszó

A kombinatorika a matematika egyik legfiatalabb és leggyorsabban fejlődő ága. Ez egymagában is indokolja, hogy a középiskolai oktatásban az eddigieknél nagyobb szerepet kapjon.

A feladatgyűjtemény az alapvető fogalmakról és feladatokról (megoldásaikkal együtt) olyan összeállítást ad, amely segítséget nyújt a kombinatorikai ismeretek megszerzéséhez, középiskolai tanításához.

A feladatokat különböző, középiskolásoknak szóló folyóiratokból, versenyekből választottam. A folyóiratok közül különösen a Középiskolai Matematikai és Fizikai Lapok (KÖMAL) és a Kvant (Szovjetunió), a versenyek közül az Arany Dániel Középiskolai Tanulóverseny, az Országos Középiskolai Tanulmányi Verseny (OKTV), a Kürschák József Matematikai Tanulóverseny és a Nemzetközi Matematikai Diákolimpia (IMO) szolgáltattak bőséges forrást. Az ezekből való feladatoknál a forrást megjelöltem. Sok feladatot középiskolai szakkörök során ismertem meg, ezeknél nem tudtam pontos forrást közölni. Az egyes megjegyzett források sem mindig megbízhatóak. Van feladat, amely több helyen, különböző forrásokkal megjelölve ismert. Ezeknél a számomra ismert legelső közlés helyét tüntettem fel.

A feladatok nehézsége változó. Az egyszerű gyakorló feladatoktól kezdve a Kürschák-versenyen, illetve a Nemzetközi Matematikai Olimpián kitűzött feladatokig terjednek. A legnehezebbnek vélt feladatokat * jellel láttam el. Olyan feladatokat is választottam, amelyekhez középiskolai anyagon túlmenő ismeretek szükségesek (például a komplex számok ismerete). Vannak feladatok, amelyek megoldásához később szereplő elméleti anyag szükséges. Ezekben az esetekben mindig kitettem a figyelmeztető *-ot. A feladatok elhelyezésénél főleg arra ügyeltem, hogy a hasonló típusú feladatok kerüljenek össze.

A feladatok sorát elméleti megjegyzések szakítják meg. Ezek megvilágítják, összefoglalják a feladatok mögött lévő fogalmakat, illetve módszereket. Ezeket a részeket betűkkel jelöltem meg (például 13.b. a 13. fejezet második, b jelű elméleti kitérőjét jelöli).

A megoldások közé is iktattam elméleti összefoglalót, illetve iránymutató megjegyzéseket. Ezek a megjegyzések önmagukban is érthetők. Ezek főleg akkor hasznosak, ha az olvasó megoldotta az előző feladatot (előző feladatokat). Ezeket a részeket nagybetűkkel jelöltem meg (például 18.C. a 18. fejezet megoldásai között található harmadik, azaz C jelzésű, elméleti kitérő). A megoldások közötti megjegyzések azt is sugallják, hogy a megoldás elolvasása és annak megértése nem jelentheti a ”feladat kipipálását”, azaz nem állhatunk meg azzal, hogy ”ezt is tudom”. Egy sikeres megoldás a jó problémamegoldót további gondolkodásra készteti. A megoldáson való elgondolkodás, az általános tanulságok levonása a későbbi feladatmegoldásoknál kamatozik. Egy megoldás továbbgondolása sokszor újabb kérdéseket vet fel, és újabb problémák megoldására sarkallhat.

A megoldások részletezése változatos. Általában törekedtem részletes megoldás megadására, azonban többször a megoldás leírása nagyobb lépésekben történt. Ennek az az oka, hogy a megoldás fő gondolatától kissé idegen, a feladat ötletét nem érintő technikai részletekkel nem akartam növelni a megoldás hosszát (a gyakorlatlanabb feladatmegoldók figyelmét ezzel nem tereltem el a ”lényeges” ötletekről). Néhol az azonos ötletek ismétlését kikerültem a korábbi feladatokra vagy megoldásokra való utalással. A gyakorlott feladatmegoldó a hiányzó lépéseket könnyen betöltheti, míg a gyakorlatlanabb olvasó újabb feladattal találja magát szemben (ez az ára annak, hogy a részletekben nem veszünk el). Egyes esetekben a megoldás inkább ötletnek vagy útmutatásnak tekinthető, amely alapján egy részletes megoldás kidolgozása már nem nehéz, de munkát igénylő feladat.

⋆  ⋆  ⋆

A feladatgyűjtemény első két fejezete két nagyon fontos bizonyítási módszerrel foglalkozik, a skatulyaelvvel és a teljes indukcióval.

A további fejezetek már szorosabban vett kombinatorikai témák. Az egyes problémakörök felsorolása előtt megpróbáljuk megfogalmazni, hogy mit értünk ”kombinatorika” alatt. A kombinatorika (mint a matematika többi ága) nem definiálható pontosan. Sokak szemében a kombinatorika a matematikának a szórakoztató problémák megoldásával foglalkozó része. Természetesen az elkötelezett feladatmegoldó számára minden probléma szórakoztató lehet. A kombinatorikai problémák talán abban különböznek a matematika megszokottabb ágaiban (geometriában, algebrában, analízisben) felmerülő problémáktól, hogy a használt fogalmak jóval egyszerűbbek. Vannak érdekes, fontos kombinatorikai struktúrák, amelyek leírhatók a sakktábla vagy egy játék segítségével.

A geometria megszokott alapfogalmai: pont, egyenes, sík, párhuzamosság, illeszkedés, hosszúság, szög…; az analízis megszokott alapfogalmai: függvény, folytonosság, határérték…; az algebra megszokott alapfogalmai: kommutativitás, részstruktúra, izomorfia… A fent felsorolt alapfogalmak gondolkodási módokat is sugallnak. A legtöbb geometriai feladat esetén mindenki megpróbál egy rajzot készíteni, segédegyeneseket rajzolni, egy geometriai transzformációval szimpatikusabb alakra hozni a problémát… Egy analízis feladat esetén sokszor az első természetes lépés a szereplő függvények folytonosságának, viselkedésének vizsgálata. Az algebra fejlődése során a strukturális szemléletmód alakult ki. Egy adott struktúra esetén a felismert összefüggések és a műveleti szabályok közötti kapcsolat tölt be központi szerepet. Ezeket az alapfogalmakat és az általuk felvetett gondolatokat, kérdéseket úgy is felfoghatjuk, mint egy szemüveget. Igazából a problémák a matematika mozgatói. Gyakran a probléma felvetése és megoldása is egyféle nyelvezetet és módszert, például a geometria nyelvezetét és módszereit használja. De a koordinátageometria ismerői tudják, hogy egy euklideszi geometriára vonatkozó kérdés algebrai (aritmetikai) nyelven is megfogalmazható, és a kérdés megoldása a valós számok algebrai struktúrájában való munkával is megoldható. A jól ismert Cauchy—Schwartz-egyenlőtlenség (x, y, α, β valós számok esetén αx + βy ≤ \sqrt{α^{2} + β^{2}}\sqrt{x^{2} + y^{2}}) valós számokra vonatkozik, de olvasható geometriai szemmel is: két vektor skaláris szorzata felülről becsülhető hosszuk szorzatával.

A kombinatorika definíciója helyett célszerűbb az alapfogalmait felsorolni: véges halmaz, véges halmazok egy rendszere, gráf, algoritmus… Ezek az alapfogalmak is gondolkodásmódot, szemléletet sugallnak. Ennek kialakulása után a problémákat tekinthetjük ”kombinatorikai szemüvegen” keresztül. Mi a kombinatorikus szemlélet? Ezt szokták diszkrét szemléletnek is nevezni. Ez a szóhasználat azonban eltér a diszkrét szó mindennapi használatától. A ”diszkrét” jelző valamilyen értelemben a ”folytonos” jelző ellentéte. Egy struktúra diszkrét, ha alkotóelemei elkülönültek, ha nincs köztük kapcsolat. (Ezeknek a mondatoknak nem kell és nem is lehet matematikai jelentést adni, mivel a benne szereplő fogalmakat nem definiáltuk. Jelentésüket akkor értjük meg teljességében, amikor elég sok példán keresztül ismerünk meg diszkrét és nem diszkrét jelenségeket, struktúrákat). Nézzünk néhány példát.

A legklasszikussabb diszkrét struktúra a halmaz, véges halmaz. Az egyik legfontosabb vele kapcsolatos fogalom az elemszáma (számossága). Ezzel el is jutottunk az első nagyon fontos kombinatorikai problémához: ”Adott egy véges halmaz. Határozzuk meg az elemszámát.” Az ilyen típusú kérdéseket összeszámlálási vagy megszámlálási problémáknak nevezzük. (Szeretnénk elkerülni a megszokottá vált, de félreérthető leszámlálási problémák szóhasználatot. Remélem, ezzel nem sértem meg azokat, akik a leszámlálási jelzőt a matematikai szaknyelv részének tekintik.)

Az alapkérdés nagyon egyszerűnek tűnik, de ilyen módon igen fogós problémák is felvethetők. H. Dörrie ”Diadalmas matematika” című munkájában klasszikus matematikai problémákat gyűjtött össze. Ezek közül több ebbe a kategóriába sorolható. Csak egy példát adunk: ”Valaki n levelet ír, és felírja n borítékra a levelekhez tartozó címzéséket. Hányféleképpen teheti a leveleket a nem hozzájuk tartozó címzést viselő borítékokba?” Az elcserélt levelek problémájának nevezett kérdésre H. Dörrie könyve két nagy matematikus, N. Bernoulli és L. Euler nevét is említi, ők egymástól függetlenül megoldották a problémát.

Összeszámlálási problémákkal foglalkozik a 3—8. fejezet. A 3—5. fejezet speciális típusú dolgok (részhalmazok, sorbaállítások, leképezések) összeszámlálásával foglalkozik. A 6—7. fejezet két összeszámlálási technikát ismertet: a lineáris rekurziót és a szitamódszert. A 8. fejezet vegyes problémákat tárgyal.

A kombinatorika egyik legismertebb problémája a négyszínprobléma. A kérdés térképek színezéseivel kapcsolatos. Gyakorló térképszínezők tapasztalati tényként észrevették, hogy az általuk kezelt összes térkép színezése (azzal a természetes feltétellel, hogy a szomszédos tartományok eltérő színt kapjanak) megoldható négy színnel. A probléma egyszerűségénél fogva igen népszerűvé vált, és igen sok matematikus dolgozott rajta. De hol van itt a diszkrét struktúra? A térkép inkább egy geometriai fogalomnak tűnik. Ez a kérdésfeltevés elvezet a gráf fogalmához. Rá kell jönnünk, hogy a feladat szempontjából csak a tartományok halmaza és a köztük lévő szomszédsági viszonyok számítanak. A probléma szempontjából az egyes tartományok alakja, területe, népessége teljesen lényegtelen.

A 9. fejezet a gráfelméleti alapfogalmakat ismerteti, és gyakorlásukra ad feladatokat. A 10—15. fejezet egy-egy gráfelméleti fogalmat vezet be, és a vele kapcsolatos kérdéseket vizsgálja. A 16. fejezet vegyes gráfelméleti problémákat ismertet.

Az egyik legfontosabb és legáltalánosabb kombinatorikai struktúra egy véges halmaz részhalmazainak egy rendszere. Nézzük a következő kérdést: Hány vezérre van szükségünk ahhoz, hogy egy sakktábla összes mezejét ütés alatt tartsuk? Egy vezér bizonyos mezőket üt. Ezek a mezők az összes 64 mező egy részhalmazát alkotják. A vezér 64-féle elhelyezéséhez így 64 halmazt rendelhetünk. Vezérek egy elhelyezése akkor tartja ütés alatt az összes mezőt, ha a megfelelő részhalmazok uniója a teljes halmaz (az összes 64 mező halmaza). Így a kérdést más módon is megfogalmazhatjuk: Adott egy 64 elemű halmaz 64 részhalmaza (lásd a fentieket). Legalább hány halmazt kell kiválasztanunk ahhoz, hogy a kiválasztott halmazok ”lefedjék” a teljes halmazt? A 17. fejezet témája a halmazrendszerek.

Az utolsó, 18. fejezetben az algoritmuselméleti problémákat gyűjtöttem össze. A számítógép, a digitális technika matematikai leírására a diszkrét modell a legalkalmasabb. Feladatgyűjteményünk nem vállalkozik az ezzel kapcsolatos matematikai fogalmak tisztázására (a technikai nehézségek miatt erre nem is vállalkozhat), de néhány rokon fogalom már középiskolában is tárgyalható.

⋆  ⋆  ⋆

A diszkrét matematika fogalmai nagyon egyszerűek, könnyen érthetők és természetesek egy fiatal diák számára. Remélem, azok a tanárok, akiknek lehetőségük van érdeklődő diákokkal foglalkozni, felhasználják ezt a feladatgyűjteményt arra, hogy tanulóikkal megszerettessék a problémamegoldást és a logikus gondolkodást.

Én is tanáraim útmutatásával szerettem meg a matematikát. Ezúton is köszönetet mondok mindazoknak akik tanítottak és szakkörvezetőim voltak. Mindazokat, amiket tőlük tanultam, szeretném továbbadni. Segítőkészségük nélkül ez a feladatgyűjtemény sem készült volna el.

Egy személyt azonban ki kell emelnem a sorból. Édesapám volt az, aki már fiatal koromban megszeretette velem a matematikát. A vele történt beszélgetések során a logikus gondolkozás és a tiszta fogalmazás fontossága szinte észrevétlenül belém ivódott. Remélem, hogy amit Tőle tanultam, azt feladatgyűjteményben legalább részben vissza tudtam adni. Segítőkészsége nélkül ez a feladatgyűjtemény sem készült volna el.

Ezúton is köszönöm Simonovits Miklós és Totik Vilmos észrevételeit, amelyek jelentős segítséget adtak munkámhoz.

Külön köszönet illeti Lipták Lászlót, aki rendkívüli figyelemmel átolvasta és értékes megjegyzésekkel látta el a feladatgyűjteményt. Tanácsai nagyban javították a könyv használhatóságát.

Köszönöm az OTKA F4024 és T016349 pályázatainak támogatását is.

Hajnal Péter

Szeged, 1997.