Kombinatorika - Az általános és középiskolai matematikai szakkörök számára 9789639326880, 9639326887 [PDF]

Zitiervorschau

Kombinatorika

Lovász László, Pelikán József, Vesztergombi Katalin

Kombinatorika az általános és középiskolai matematikai szakkörök számára

TYPOTEX Kiadó Budapest, 2003

Ez a mu˝ az illetékes kuratórium döntése alapján az tá˝ mogatásával a Felsooktatási Pályázatok Irodája által lebonyolított Tankönyvtámogatási Program keretében jelent meg.

c Lovász László, Pelikán József, Vesztergombi Katalin, Typotex;

2003

ISBN 963 9326 88 7 TiniTudomány sorozat ISSN 1588-3841 Témakör: középfokú matematika

Kedves Olvasó! ˝ Önre gondoltunk, amikor a könyv elokészítésén munkálkodtunk. Kapcsolatunkat szorosabbra fuzhetjük, ˝ ha belép a Typoklubba, ahonnan értesülhet új kiadványainkról, akcióinkról, programjainkról, és amelyet a www.typotex.hu címen érhet el. Honlapunkon megtalálhatja az egyes könyvekhez tartozó hibajegyzéket is, mert ˝ sajnos hibák olykor elofordulnak.

Kiadja a Typotex Elektronikus Kiadó Kft., az 1795-ben alapított ˝ Egyesületének tagja Könyvkiadók és Könyvterjesztok ˝ kiadó Votisky Zsuzsa Felelos Muszaki ˝ szerkeszto˝ Hesz Gábor Borítóterv Tóth Norbert Terjedelem 8,75 (A/5) ív Készült a Naszály Print Kft. nyomdájában ˝ vezeto˝ Hemala Mihályné Felelos

Tartalom

El˝oszó az új kiadáshoz Hogyan használjátok a könyvet?

7 9

1. Számoljuk össze!

11

2. Kombinatorika a számtanban

37

3. Kombinatorika a mértanban

57

4. Blokkrendszerek

105

Megoldások 1. Számoljuk össze! 2. Kombinatorika a számtanban 3. Kombinatorika a mértanban 4. Blokkrendszerek

123 123 128 132 137

El˝oszó az új kiadáshoz

Ezt a kis könyvet diákkorunkban írtuk, 1970-ben. Azóta több kiadást ért meg, lefordították németre és japánra is. Amikor a Typotex Kiadó megkeresett bennünket azzal, hogy újabb kiadását tervezi, nagy örömmel járultunk hozzá. Persze azóta sok víz folyt le a Dunán. Könyvünk témája, a kombinatorika (hívják diszkrét matematikának is) nagyot fejlo˝ dött, és a matematika egyik legtöbbet alkalmazott fejezetévé vált: a számítógép-tudomány erre a tudományágra épül. Ezért át kellett néznünk könyvecskénket abból a szempontból is, hogy id o˝ szer˝ue, helytálló-e az anyaga. Örömmel állapítottuk meg, hogy szinte semmit nem kell változtatni; ha ma írnánk a könyvet, nagyon hasonló matematikai témákat dolgoznánk fel. Így abban maradtunk, hogy változatlan formában kerüljön kiadásra. Egy fontos fejleményt azonban meg kell említenünk. A 66. oldalon megfogalmazunk egy híres, régi problémát, az ú.n. négyszintételt. Ez a könyv megírásakor megoldatlan volt, vagyis (nevével ellentétben) nem tétel, csak sejtés. Nos, ezt a sejtést néhány évvel kés˝obb (1976-ban) Appel és Haken amerikai matematikusok bebizonyították. Munkájuk nagy port vert fel, nemcsak azért,

8

El˝oszó az új kiadáshoz

mert ily módon ez a híres probléma meg lett oldva, de azért is, mert akkoriban egyedülálló módon, a bizonyítás jelento˝ s mértékben támaszkodott számítógépekre. Számítógépet nem használó bizonyítást azóta sem sikerült találni! Reméljük, hogy az új kiadás olvasói élvezettel forgatják majd a könyvecskét.

Hogyan használjátok a könyvet?

Könyvünket els˝osorban az általános iskolák 7. és 8. osztályos tanulóinak és középiskolásoknak szántuk. Hogy minél jobban tudjátok használni, néhány tanácsot szeretnénk adni. Észrevehetitek majd, hogy szöveg közben feladatok vannak. Amikor egy-egy feladathoz értek, álljatok meg az olvasásban, és addig ne menjetek tovább, amíg meg nem oldottátok a feladatot. Szöveg közben néha kérdéseket is fogtok találni; ezekre is próbáljatok meg válaszolni. Ha már megoldottátok a feladatot (vagy már hosszasabban sikertelenül gondolkoztatok rajta), csak akkor lapozzatok a megoldásokhoz. Ezek általában csak vázlatosak, a megoldás alapötletét tartalmazzák. Néha egyáltalán nem találtok megoldást: ha egy ilyen feladatot nem tudtok megoldani, ez azt mutatja, hogy nem olvastátok el elég figyelmesen az elo˝ z˝o részeket. Ilyenkor tanulmányozzátok át újra a megoldáshoz szükséges anyagrészeket! Kellemes olvasást kívánunk és reméljük, hogy hasznát veszitek a könyvnek.

1 Számoljuk össze!

– Hát ebben aztán semmi nehéz nincs! Számolni már az alsó tagozatban megtanulunk – szinte látjuk, hogy ezt gondoljátok magatokban. Mi most meg akarjuk mutatni nektek, hogy bár egyszer˝uen megszámolni valamit sokszor könnyebb, mint ügyesen összeszámolni, mert ehhez néha sokat kell gondolkozni, mégis így többre jutunk. Ez az út vezet a kombinatorika birodalmába. Ismerkedjünk meg azokkal a gyerekekkel, akik útitársaink lesznek! Andreához osztálytársai jönnek vendégségbe: Béla, Csaba, Dóra, Erzsi, Feri és Gábor, valamennyien szüleikkel. – Hányan is leszünk? – kérdi Andrea terítés közben, és már kezdi is sorolni: – Anyuka, Apuka, én, Erzsi, Dóra, Pista bácsi, Kati néni, Bözsi néni, . . . – Elég, elég! Hárman jönnek egy-egy helyro˝ l, így összesen hétszer hárman, azaz huszonegyen leszünk – mondja Anyuka, és ha Andreának nem az uzsonnán, hanem a fentieken járna az esze, máris meggy˝ozve érezhetné magát. Megérkeznek a vendégek, és a gyerekek kezet fogva köszöntik egymást. Andreának, úgy látszik, használt az elo˝ bbi eset, mert valahogy eszébe jutott:

12

1. Számoljuk össze!

– Hány kézfogást is jelent ez? Tortát kap, aki kitalálja. Kis hallgatás után megszólalt Dóra: – Én mindenesetre hatszor fogtam kezet. – Én is így számoltam – mondta Gabi. – Persze, mindannyian kezet fogtunk hat másikkal – csapott a homlokára Csaba. – Mivel heten vagyunk, ez összesen 7 · 6 = 42 kézfogás. – Túl soknak t˝unik ez nekem – mondta Erzsi. Feri izgatottan közbevágott: – Ahogyan Csaba számolja, úgy az is két kézfogásnak számít, ha két gyerek egymással fog kezet. – Pedig majdnem igaza van Csabának – mondta Béla – csak arról feledkezett meg, hogy minden kézfogásnak két résztvev o˝ je van; és a kézfogást mindkett˝ojüknél beszámoltuk. Ezért a 42-t még el kell osztani kett˝ovel, vagyis 21 kézfogást kapunk. – Üljetek asztalhoz! – szólt közbe Anyuka. – Mindenki kap a tortából. – Mindegy, hogy hova ültök, majd félóránként cserélünk, hogy minden ülésrend sorra kerüljön – mondta Andrea, és Gabi hozzátette: – Te persze az asztalf˝on maradsz, mert neked van a születésnapod. Szerencsére a gyerekek elfeledkeztek Andrea ez utóbbi kijelentésér˝ol, de mi most számoljunk utána, mennyi ideig kell ott maradniuk, hogy minden ülésrendre sor kerülhessen. Természetesen hat vendég ülésrendjei között nehezen tudunk kiigazodni; nézzük meg el˝oször, mi történne, ha kevesebb vendég volna (ekkor az asztal köré is kevesebb széket raknának). Ha csak Béla jönne, akkor csak egy ülésrend volna. Ha Béla és Csaba jönnek, akkor kétféleképpen ülhetnek le: ha egyiküket leültetjük az egyik székre, a másik már csak az üresen maradt helyre ülhet. Nézzük meg, három vendég esetén mi a helyzet! Számozzuk meg a székeket, ahogyan az 1. ábra mutatja, és foglaljuk ügyesen táblázatba az ülésrendeket! A táblázat készítése úgy célszer˝u, hogy el˝oször azokat az ülésrendeket írjuk fel, amelyekben mondjuk Dóra ül a 3-as széken, és folytassuk azzal, hogy Csabát, majd Bélát ültetjük a 3-as székre. Ekkor a következo˝ táb-

13

1. Számoljuk össze!

lázatot kapjuk: 1.

2.

3.

2

széken ül Béla Csaba

Csaba Béla

Dóra Dóra

Béla Dóra

Dóra Béla

Csaba Csaba

Csaba Dóra

Dóra Csaba

Béla Béla

3

1

1. ábra

Andrea

Hat ülésrendet kaptunk tehát. Mielo˝ tt továbbmennénk, nézegessük egy kicsit ezt a táblázatot! Hány csoport is van? Nyilván három, vagyis ahány vendég van, hiszen bármelyiket ültethetjük a 3-as székre. Egy-egy csoportban pedig annyi ülésrend van, ahányféleképpen a másik két gyereket a másik két helyre leültethetjük, vagyis kett˝o. Próbáljuk most elképzelni, milyen lenne a táblázat négy vendég esetén. Ha most aszerint csoportosítjuk a lehetséges ülésrendeket, hogy a 4-es széken ki ül, akkor nyilván négy csoportot kapunk. Egy-egy csoporton belül annyi sor, azaz annyi ülésrend lesz, ahányféleképpen a másik három vendéget az 1-es, 2-es és 3-as székre leültethetjük. De éppen az imént számítottuk ki, hogy ez hatféleképpen lehetséges. Négy vendég esetén tehát összesen 4 · 6 = 24 ülésrend adódik. Öt vendég esetén nyilván öt csoportban lesz 24 –24 ülésrend, így az összes ülésrendek száma 5 · 24 = 120. Végül esetünkben, amikor hat vendég van, hat csoportot alkothatunk az ülésrendekb˝ol aszerint, hogy ki ül a 6-os széken, és egy-egy ilyen csoportban annyi ülésrend lesz, ahányféleképpen öt gyereket öt helyre ízültethetünk, vagyis az el˝obbiek szerint 120. Eszerint 6 · 120 = 720 ülésrendre kellene sort keríteniük a gyerekeknek, ha teljesíteni akarnák Andrea kívánságát. Ez pedig 15 napig, azaz több mint két hétig tartana (ha közben nem aludnának)! Ez még elképzelhet˝o id˝otartam, de további vendégek már nagy bonyodalmat

14

1. Számoljuk össze!

okoznának: például, ha 11 vendég jönne, akkor a korábbi gondolatmenet ismétlésével azt kapnánk, hogy ekkor 39 916 800 ülésrend lehetséges. Ennyi ülésrend végigülése (félóránkénti cserével) akkor fejez˝odhetne be napjainkban, ha még a római birodalom idején kezd˝odött volna a vacsora! 1. feladat Hány ülésrend lenne, ha Andrea nemcsak az asztalf˝ore ülhetne? Úgy látszik, Béla nem elégedett meg a tortanyereménnyel, mert most éppen ezt javasolja: – Mi lenne, ha összeadnánk a pénzünket, vennénk egy csomó lottószelvényt, annyit, hogy biztosan legyen ötös találatunk? A nagy nyeremény lehet˝osége mindenkit fellelkesített, de sehogyan sem tudták kiszámítani, hogy hány szelvényt kell ehhez kitölteniük. Segítsünk nekik! Az emberek nagyon sok különbözo˝ módszert használnak a lottószelvényük kitöltésére. Lehet, hogy olyan is van, aki kimegy egy mezei futóversenyre, ahol 90-en indulnak, és az elso˝ öt helyezett rajtszámát tippeli. Számoljuk össze azt, hogy hányféle végeredménye lehet a versenynek, ha csak az elso˝ öt helyezettet vesszük figyelembe! Els˝o helyezett lehetett akárki a 90 közül. Bárki is lett az elso˝ helyezett, még mindig 89 leheto˝ ség van a második helyezésre: Ha tehát csak az els˝o és második helyezettet díjaznánk, akkor 90 · 89 lehetséges végeredményt kapnánk. Ha a harmadik helyezést is figyelembe vesszük, akkor az elo˝ z˝o 90·89 lehet˝oség mindegyike 88 további lehet˝oséget takar, tehát az els˝o három helyezett figyelembevétele esetén 90 · 89 · 88 végeredmény lehetséges. Nyilván látjátok már, hogyan lehet továbbmenni; s végeredményül azt kapjuk, hogy 90 futó versenyében az elso˝ öt helyezettre 90 · 89 · 88 · 87 · 86 lehet˝oséget kapunk. No, de mi köze ennek a lottózáshoz? Gondoljuk csak meg, hogy tippelhetjük éppen az elso˝ öt helyezett rajtszámát. Tehát a lehetséges végeredmények száma annyi, mint az elso˝ 90 számból kiválasztható számötösök száma. Ugyanez áll a lottószámokra is. Vagy talán nem egészen?! Beleestünk ugyanabba a hibába,

1. Számoljuk össze!

15

amibe régebben Csaba esett bele a kézfogások összeszámolásakor, mert hiszen a versenyben az 5, 9, 42, 69, 28 számötös más végeredményt jelent, mint a 69, 42, 28, 5, 9 számötös, viszont a lottónál a kett˝o ugyanaz. Vagyis a versenyötösök közé minden lottóötöst többször beszámítottunk. Azt kellene megmondanunk, hogy hányszor. Nyilván annyiszor, ahányféleképpen a lottóötös számait sorba lehet rakni. De azt már az elo˝ bb kiszámoltuk, hogy ez éppen 120 (csak nem a lottóötös öt számát, hanem öt vendéget raktunk sorba). Tehát a kitöltendo˝ lottószelvények száma, amelyek között biztosan van ötös találat: 90 · 89 · 88 · 87 · 86 = 43 949 268 (db). 5·4·3·2 2. feladat Hány különböz˝o lottószelvény lenne, ha csak két számot kellene megjelölni? 3. feladat Gondolkozzatok azon, hogy mi a kapcsolat a kézfogások száma és a különböz˝oképpen kitöltött lottószelvények száma között ! A nehéz fejtör˝o után a társaság táncolni kezdett. Ne is zavarjuk o˝ ket, hanem helyette gondolkozzunk el azon, hogy hány különböz˝o táncoló pár lehetséges. Ez igazán nem nehéz feladat: Olyan táncospár, melynek Andrea a hölgytagja, négy lehet (ez magyarán azt jelenti, hogy Andrea négy fiúval táncolhat). Ugyanígy Dóra is, Erzsi is négy-négy fiúval táncolhat, vagyis összesen 3 · 4, azaz 12 táncospár lehetséges. 4. feladat Hány táncospárt lehet kiválasztani, ha egy társaságban 10 fiú és 16 leány van? Hányat, ha egy képzeletbeli táncmulatságon 10 000 leány és 20 000 fiú vesz részt? Kifáradva a táncban, a gyerekek közül néhányan átmentek meg nézni, hogy mit csinálnak a szülo˝ k. Négyen éppen bridzseztek, és Dóra beállt kibicelni édesapja mögé. – Apu, a múltkor is ugyanez a lapod volt! – mondta Dóra.

16

1. Számoljuk össze!

– Nem hiszem, mert gondold csak meg, milyen sokféle lapot kaphatok én! – válaszolta édesapja. – Nem tudom megmondani, hányféle lapod lehet, mert nem ismerem a bridzs szabályait. – Ha tényleg ki akarod számítani, elég, ha annyit tudsz, hogy 52 lap van és 13 lapot kapok. Nem hisszük, hogy ezt Dóra ott helyben ki tudta volna számolni, de ti, ha figyelmesen olvastátok eddig a könyvet, akkor most jogosan mondhatjátok: – Hiszen ez ugyanaz, mint a lottó, csak itt most 52-bo˝ l kell 13-at kiválasztani. – Az ott elvégzett számolás mintájára lehetne itt is meghatározni a különböz˝o lapok számát. Határozzátok meg! (Végeredménynek 635 013 559 600 adódik.) Most búcsúzzunk el a társaságtól, és beszéljük meg az eddigiek tanulságait. 1. Reméljük, hogy sikerült meggyo˝ znünk benneteket: érdemes ügyesen számolni. Az eddigieknek volt egy nagy hiányosságuk, az hogy csak nagyon konkrét eseteket vizsgáltunk. Több helyen szerepelt ilyen mondat: „Ezt már lényegében kiszámítottuk”, pedig valami egészen mást számítottunk ki (például az öt lottószám különböz o˝ sorrendjeinek számáról megállapítottuk, hogy ugyanaz, mint az ötf˝onyi vendégsereg ülésrendjeinek a száma). Láthattuk azt is, hegy lényegében ugyanaz a feladat más-más számadatokkal is el˝ofordul (például a lottó és a kártya). Jó volna olyan módszereket megismerni, amelyekkel egyöntet˝uen tudjuk megoldani ezeket a látszólag különböz˝o feladatokat. Végül pongyolaságot követtünk el, amikor az ülésrendek kiszámításánál öt vendég esetén röviden csak annyit írtunk, hogy „nyilván öt csoportban lesz 24 –24 ülésrend”, és nem részleteztük, hogyan végezzük el a csoportosítást. Itt persze könnyen kiküszöbölhettük volna ezt a hiányosságot, hiszen csak az el˝otte lev˝o gondolatmenetet kellett volna megismételni, de mit csináltunk volna, ha 100 vagy akár 1000 vendégr o˝ l lett volna szó? Érezzük, hogy a gondolatmenet 1000-szeri ismét-

1. Számoljuk össze!

17

lésének egyetlen akadálya az ido˝ hiány lett volna, de azért erre a kérdésre még vissza kell térnünk. 2. Arra a kérdésre, hogy miért ugyanaz a lottószámok sorrendjeinek száma, mint az ülésrendek száma, nyilván ti is meg tudnátok felelni. Mindkét esetben „valamit” (a társaságot vagy a számötöst) el kellett rendezni, és ez a „valami” mindkét esetben 5 „másvalamib˝ol” állt. Meg kellett számolnunk, hány ilyen elrendezés lehetséges. Ez a „valami” szó bizonytalan érzést kelt, ezért használjuk inkább a matematikában elfogadott kifejezéseket helyette! Mindenféle összesség elnevezése a matematikában: halmaz. Esetünkben is halmazokról van szó: a társaság a gyerekek összessége, halmaza; a számötös a tippelt lottószámok halmaza. Azokat a „másvalamiket”, amikbo˝ l a halmaz áll, a halmaz elemeinek nevezik. Így például a gyerekek a társaság elemei, a tippelt számok a számötös elemei, vagy például a kártyalapok a kártyacsomagnak – vagyis a kártyalapok halmazának – az elemei. Egy halmaznak lehet, hogy csak egy eleme van; so˝ t beszélhetünk az üres halmazról is, aminek egyáltalán nincs eleme. Etto˝ l az utóbbitól nem kell megijedni, olyan szerepet játszik, mint a / Az üres halmaz eleszámok között a 0. Hasonlóan is jelöljük: 0. meinek a száma nyilván nulla. Egy halmazt megadhatunk azáltal, hogy felsoroljuk az elemeit; ekkor magát a halmazt úgy jelöljük, hogy leírjuk az elemeit, és ilyen kapcsos zárójelbe tesszük: {}. Például az el o˝ bbi társaság mint halmaz: {Andrea, Béla, Csaba, Dóra, Erzsi, Feri, Gabi} vagy rövidebben {Andrea és vendégei}. Els˝o kis problémánkat már le is tudjuk fordítani a matematika nyelvére: „Mennyi a ma este itt lev˝o emberek halmaza elemeinek a száma?” Ahhoz, hogy Andrea mamájának válaszát is (l. 11. oldal) „lefordíthassuk”, meg kell még néhány elnevezéssel ismerkednünk. El˝otte viszont oldjátok meg az alábbi feladatokat! 5. feladat Mondjatok olyan halmazokat, melyeknek elemei: a) épületek; b) emberek; c) tanulók; d) fák; e) számok; f) pontok.

18

1. Számoljuk össze!

6. feladat Mik az elemei a következ˝o halmazoknak: a) hadsereg; b) emberiség; c) kórus; d) könyvtár; e) állatvilág. 7. feladat Mondjatok olyan halmazt, amely a) 52; b) 13; c) 32; d) 100; e) 90; g) 2 000 000 elemb˝ol áll! 8. feladat Felírunk egy szokatlan halmazt: {Andrea, {1}}. Mik az elemei? 3. Ha a fenti feladatokat végiggondoltátok, akkor láttátok, hogy az „emberiség” az emberek halmaza, az „kórus” az iskola kórustagjainak a halmaza. Van-e valami köze a két halmaznak egymáshoz? Igen, mindkett˝onek az elemei emberek. Csakhogy az egyik az összes embert tartalmazza, míg az kórus csak bizonyos emberekb˝ol (az iskola kórustagjaiból) áll. Vagy vehetnénk a magyar népet: erre is igaz; hogy csak bizonyos emberekbo˝ l (a magyarokból) áll. Mindkét halmaz (és mondhatnánk még nagyon sok mást) része az emberiségnek. Sokszor lesz dolgunk olyan halmazzal, amely egy másik halmaz bizonyos elemeibo˝ l áll, vagyis része a másiknak. Ekkor az el˝obbi halmazt a másik halmaz részhalmazának nevezzük. Így az kórus, a magyar nép az emberiség részhalmazai. A „bizonyos” elemek lehet, hogy az összes elemet jelentik: így minden halmaz részhalmaza saját magának. Az is lehet, hogy egyetlen egy elem sem tartozik a „bizonyosok” közé, vagyis az üres halmaz minden halmaznak részhalmaza. 9. feladat Részhalmaz-e az elem? 10. feladat Soroljátok fel a következ˝o halmaz összes részhalmazait: {0, 1, 3}! Hány van? 11. feladat Mondjatok több olyan halmazt, amelyeknek {Andrea, Dóra, Erzsi} részhalmaza! 12. feladat Mondjatok olyan halmazt, amelynek az {1, 3, 4} halmaz és a {0, 3, 5} halmaz is részhalmazai! Keressétek meg a legkevesebb elem˝ut! Ha egy általános iskolát és egy gimnáziumot egyesítenek, akkor az új intézmény tanári kara mindazokból a tanárokból fog

1. Számoljuk össze!

19

összetev˝odni, akik vagy a gimnáziumban vagy az általános iskolában, esetleg mind a kett˝oben tanítottak. Általában két halmaz egyesítésének (vagy uniójának) nevezzük mindazoknak az elemeknek a halmazát, amelyek vagy az egyik halmaznak, vagy a másik halmaznak, vagy mindketto˝ nek az elemei. A fenti példában az új intézmény tanári kara az általános iskola és a gimnázium tanári karának az egyesítése. 13. feladat Melyik halmazt neveznétek a, b, c, a, b, d és b, c, d, e egyesítésének? Írjátok le, mi lesz az els˝o kett˝onek az egyesítése, azután ennek és a harmadiknak az egyesítése! Ugyanígy készítsétek el a második és a harmadik halmaz egyesítését, és az els˝onek ezzel való egyesítését! Fogalmazzátok meg, mit értetek kett˝onél több halmaz egyesítésén! 14. feladat Mi a kapcsolat az „egyesítés” és a 12. feladat között? 15. feladat Egy ötelem˝u és egy kilencelem˝u halmazt egyesítünk. Lehet-e az egyesítésük elemszáma: 4; 6; 9; 10; 14; 20? Mondjatok ezekre az esetekre példát! 16. feladat Egy n és egy m elem˝u halmazt egyesítünk (ahol n és m adott természetes számok, és mondjuk n < m). Mennyi lehet a kapott halmaz elemszáma? Két halmaz közös elemeinek halmazát a két halmaz metszetének (az elnevezés onnan származik, hogy két sík közös pontjai éppen a két sík metszésvonalát alkotják). 17. feladat Mi a metszete a {0, 1, 3} és {1, 2, 3} halmazoknak? 18. feladat Mi a metszete az osztály leánytanulói és fiútanulói halmazának? 19. feladat Mi a páros számok és a prímszámok halmazának a metszete? 20. feladat Mekkora lehet egy m és egy n elem˝u halmaz metszetének az elemszáma?

20

1. Számoljuk össze!

21. feladat Vegyük égy m és egy n elem˝u halmaz egyesítését és metszetét! Jelöljük az egyesítés elemszámát p-vel, a metszet elemszámát q-val ! Bizonyítsátok be, hogy p + q = m + n! 22. feladat Fogalmazzátok meg most már a matematika nyelvén azt, ahogyan Andrea mamája összeszámolta a vendégeket! 4. Legtöbbször azzal a problémával találkoztunk a bevezetésben, hogy hányféleképpen lehet egy halmaz elemeit sorba rakni. Jelöljük n-nel a tekintett halmaz elemeinek a számát! Kiszámítottuk a sorbarakások számát, ha n = 2, 3, 4, 5, 6. Ha még hozzávesszük azt, hogy 1 elemnek egyféle „sorrendje” lehetséges, ezt a táblázatot készíthetjük: n sorbarakások száma

1 1

2 2

3 6 = 2·3

4 24 = 2 · 3·4

5 120 = 2 · 3·4·5

6 720 = 2 · 3·4·5·6

A kérdés ez volt: hányféle módon rakhatunk sorba n elemet? Eddigi tapasztalataink szerint a választ ez a számolási szabály adja: 1-t˝ol n-ig összeszorozzuk a természetes számokat (mi ugyan csak 2-t˝ol szoroztuk össze a számokat, de hogy ne kelljen kivételt tenni, írjuk eléjük tényez˝oként az 1-et is!) Erre a szorzatra célszer˝u külön jelölést bevezetni: n!-sal jelöljük (olvasd: n faktoriális). Tehát 2! = 2, 3! = 6, 4! = 24, 5! = 120, stb. A faktoriálisokra teljesül a következ˝o egyenl˝oség: (n + 1) · n! = (n + 1)!

(1)

Ugyanis (n + 1)!-t úgy kapjuk, hogy az 1-to˝ l n-ig terjed˝o egész számok szorzatát még (n + 1)-gyel megszorozzuk. (1) akkor is használható, amikor az el˝obbi d˝oltbet˝us szabály nem ad felvilágosítást. Mit jelent például 1-t˝ol 1-ig összeszorozni a számokat? Ennek a szorzásnak nincs értelme. De (1)-ben beírhatunk n helyébe 1-et, és ezt kapjuk 2 · 1! = 2!

1. Számoljuk össze!

21

Itt a jobb oldal értéke 2, tehát az összefüggés csak úgy lehet igaz n = 1-re, ha 1! = 1. Hasonlóan, ha n = 0: 1 · 0! = 1! Amib˝ol látszik, hogy n = 0-ra csak úgy állhat fenn az összefüggés, ha 0! = 1. Számpéldáink alapján azt gyanítjuk, hogy egy n elem˝u halmazt n!-féleképpen lehet sorba rakni. n = 1-re is igaz ez, mert az egyelem˝u halmazt nyilván csak egyféleképpen lehet sorba rakni. De igaz-e n = 1000-re? Ha az ülésrendek számának meghatározásakor használt gondolatmenetet 1000-szer megismételnénk, érezzük, hogy n = 1000-re is megkapnánk, hogy 1000! a sorbarakások száma. De a gondolatmenetet ennyiszer elismételni hosszadalmas és unalmas volna, és ha befejeznénk, még mindig megkérdezhetnénk pl. n = 10 000-re. Mégis, ha valaki megbizonyosodott arról, hogy a gondolatmenetet valóban akárhányszor el lehet végezni, akkor meggy˝ozve érezheti magát afel˝ol, hogy a sorbarakások száma n!. Ezt a „meggyo˝ z˝odést” fogjuk most pontos matematikai formába önteni; el˝obb azonban megismerkedünk a kombinatorika legfontosabb bizonyítási módszerével, a teljes indukcióval. 5. Kezdjük egy feladattal! Új cukrászda nyílik egy iskola közelében. Els˝o nap Judit betéved, és vesz egy gombóc fagylaltot. A fagylalt nagyon ízlik, ezért másnap két iskolatársát is elhívja, és mindhárman vesznek egy-egy gombócot. Harmadnap két újabb iskolatársukat hívják el, tehát már öten mennek. A következo˝ napon magukkal viszik még két iskolatársukat; általában, mindennap két újabb iskolatársukat hívják el, így mindig ketto˝ vel többen mennek fagylaltozni, mint az elo˝ z˝o napon. Kérdésünk: Hány gombóc fagylaltot vettek összesen az elso˝ n nap alatt? Az els˝o napon egy gombócot vettek (csak Judit ment a cukrászdába); a második napon 3 gombócot; a harmadik napon 5 gombócot; a negyedik napon 7 gombócot, és így tovább, nyilván adódnak rendre a páratlan számok. Kérdésünk tehát: Mennyi az els˝o n páratlan szám összege?

22

1. Számoljuk össze!

Számítsuk ki ezt az összeget n néhány kis értékére! Az eredményeket táblázatba foglalva: n az összeg

1 1

2 1+3 = 4

3 1+3+5 = 9

4 1 + 3 + 5 + 7 = 16

Könny˝u észrevenni, hogy a négyzetszámokat kapjuk sorban. Ha ez továbbra is igaz, akkor a következo˝ összegnek 25-nek kell lennie. Számítsuk ki: 1 + 3 + 5 + 7 + 9 = 25. Hogyan tudnánk nnek minden értékére igazolni, hogy az els˝o n páratlan szám öszszege n2 ? Ha az els˝o n − 1 páratlan szám összegére már tudnánk ezt, akkor így okoskodhatnánk: az n-edik páratlan szám 2n − 1. Az els o˝ n páratlan szám összegét úgy is megkaphatjuk, hogy az elso˝ n − 1 páratlan szám összegéhez még hozzáadjuk az n-ediket, vagyis 2n − 1-et. Ha most – valahonnan – tudjuk, hogy az els o˝ n − 1 páratlan szám összege (n − 1)2, akkor könnyen kiszámíthatjuk az els˝o n páratlan szám összegét is: (n − 1)2 + (2n − 1) = (n − 1) · (n − 1) + (2n − 1) =

= n(n − 1) − (n − 1) + (2n − 1) = 2

(2)

2

= n − n − n + 1 + 2n − 1 = n .

Tehát ha (n − 1)-re az állításunk igaz, akkor n-re is az. De honnan tudnánk (n − 1)-re? Persze, az elo˝ z˝oeket végiggondolhatnánk n helyett (n − 1)-gyel, és így tulajdonképpen elég volna (n − 2)re tudni, hogy igaz az állítás; vagy akár – n helyett (n − 2)-vel végiggondolva a fentieket – (n − 3)-ra. Vagy elég volna (n − 4)re tudni, vagy. . . El˝obb-utóbb eljutunk 1-ig (pontosan: n−1 lépés után); és 1-re már tudjuk, hogy a fenti do˝ lt bet˝us állítás igaz. Ezzel beláttuk, hogy n-re is igaz. Egy kicsit máshogyan is elmondhatjuk a fenti gondolatmenetet: 1-re igaz a d˝olt bet˝us állítás, ezt ellen˝oriztük. Ekkor a (2)-ben végzett számolás n = 2-vel mutatja, hogy 2-re is igaz (ezt is ellen˝oriztük ugyan közvetlenül is, de erre nem is lett volna szükség). 3-ra is igaz az állítás, mert (2) szerint 2-ro˝ l már örökl˝odik

1. Számoljuk össze!

23

3-ra. Ugyanígy 3-ról örökl˝odik 4-re, 4-r˝ol 5-re, és így tovább, igaz minden n-re. Azt amit most végiggondoltunk, általánosságban így fogalmazhatjuk meg: Be akarjuk bizonyítani a természetes számoknak valamilyen tulajdonságát. Tudjuk, hogy az 1 számnak ez a tulajdonsága megvan. Azt is tudjuk, hogy a tulajdonság „öröklo˝ dik” n-r˝ol (n + 1)re, bármilyen természetes számot is jelöl az n; azaz ha n-nek megvan ez a tulajdonsága, akkor (n + 1)-nek is. A teljes indukció elve az, hogy ekkor minden számnak megvan ez a tulajdonsága. Ez az elv mindenki számára világos: 1-nek megvan a tulajdonsága, 1-r˝ol örökl˝odik 2-re, 2-r˝ol 3-ra és így tovább. Nézzük meg most, milyen kapcsolatban is van ez a sorbarakások számával? Mi lesz itt a tulajdonság? Az, hogy egy n elem˝u halmaz összes sorbarakásainak száma n!. Az 1-nek megvan ez a tulajdonsága, ezt már láttuk. Meg akarjuk nézni, hogy valóban örökl˝odik-e ez a tulajdonság n-r˝ol (n + 1)-re. Vagyis feltesszük, hogy az n számnak megvan ez a tulajdonsága (ezt a feltevést nevezzük indukciós feltevésnek), és bebizonyítjuk (ezt felhasználva), hogy az (n + 1)-nek is megvan ez a tulajdonsága. Csoportosítsuk ugyanis az n + 1 elem sorbarakásait aszerint, hogy melyik elem van az utolsó helyen. Így n + 1 csoportot kapunk. Egyegy csoportban annyi sorbarakás van, ahányféleképpen a maradék n elemet sorba tudjuk rakni, vagyis az indukciós feltevés szerint n!. Az n + 1 csoportban tehát összesen (n + 1) · n! sorbarakás van, de err˝ol tudjuk, hogy ez éppen (n + 1)!. Tehát a tulajdonság tényleg átörökl˝odött (n + 1)-re. A teljes indukció segítségével tehát bebizonyítottuk a következ˝o tételt: Tétel n elemet n!-féleképpen lehet sorba rakni. A sorbarakás helyett a matematikában szokásosabb rendezést mondani. Így, ha egy halmaz elemei sorba vannak rakva, akkor rendezett halmazról beszélünk. Ha egy rendezett halmaz elemeit átrendezzük, ehelyett idegen szóval azt is szokás mondani, hogy permutáljuk.

24

1. Számoljuk össze!

6. Most olyan kérdésre térünk át, amely már elég régen a „leveg˝oben lógott” : hány részhalmaza van egy n elem˝u halmaznak? Próbálkozzunk el˝oször kis, adott számokkal; halmazunk elemei mindegy, hogy micsodák; legkényelmesebb, ha természetes számoknak választjuk o˝ ket. Az {1} halmaznak két részhalmaza van: / {1}, {2}, {1, 2}. 0/ és {1}. Az {1, 2} halmaznak a részhalmazai: 0, Az {1, 2, 3} halmaznak már egy régebbi feladatban fel kellett sorolnotok a részhalmazait: / {1}, {2}, {3}, {1, 2}, {2, 3}, {1, 3}, {1, 2, 3}. 0, Foglaljuk táblázatba, hány részhalmaz adódik: n részhalmazok száma

1 2

2 4 = 2·2

3 8 = 2·2·2

Úgy gondoljuk, mindannyian megfigyeltétek a szabályosságot: Egy n elem˝u halmaz összes részhalmazainak számát úgy kapjuk, hogy a 2-t n-szer vesszük szorzótényezo˝ ül. Sokszor lesz dolgunk olyan szorzatokkal, melyeknek tényezo˝ i azonosak. Ha az a számot n-szer vesszük tényez˝oül, a szorzatot an -nel jelöljük (olvasd: „á az enediken” vagy: „á n-edik hatványa”). Tehát például 2 · 2 · 2 · 2 = 24 , 3 · 3 = 32 . Így a számpéldák alapján azt sejtjük, hogy: Tétel Egy n elem˝u halmaznak 2n részhalmaza van. Persze, ez az állítás csak akkor válik tétellé, ha be is bizonyítjuk. Ismét a teljes indukció bizonyítási módszeréhez folyamodunk. Milyen tulajdonságát is akarjuk bebizonyítani a természetes számoknak? Azt, amit fentebb tétel formájában írtunk le. Ha n = 1, akkor, mint az el˝obb kiszámoltuk, összesen 2 részhalmaz van. A 2-t 1-szer véve szorzótényezo˝ ül 2-t kapunk, vagyis 21 = 2, tehát az 1 számnak valóban megvan a tételben kimondott tulajdonsága. Azt kellene még megnéznünk, hogy a tulajdonság valóban örökl˝odik-e. Tegyük fel tehát, hogy az n elem˝u halmazokról már tudjuk, hogy összes részhalmazaik száma 2 n . Számoljuk össze – ezt felhasználva – egy n + 1 elem˝u halmaz összes részhalmazait. Az n + 1 elem˝u halmaz egyik elemét gondolatban

1. Számoljuk össze!

25

fessük be pirosra, a többit kékre. Az összes részhalmazokat mármost két csoportba oszthatjuk aszerint, hogy tartalmazzák-e ezt a piros elemet, vagy sem. Amelyek nem tartalmazzák, azok éppen a maradék n elemb˝ol álló halmaz összes részhalmazai, így számuk az indukciós feltevés szerint 2n . Ezek a tiszta kék részhalmazok. (Köztük van az üres halmaz is, mert abban sincs piros.) A másik csoportba tartozó részhalmazokat párosítsuk össze ezekkel! Mindegyik mellé azt tegyük oda, amelyikben ugyanazok az elemek vannak, meg még piros elem is. Világos, hogy így mindegyik tiszta kék részhalmazhoz egy pirosas részhalmazt teszünk, és a pirosas részhalmazokat mind elhelyezzük. Ezért a második csoportban is ugyanannyi részhalmaz van, mint az elso˝ ben, vagyis 2n . A két csoportban együttvéve tehát: 2n + 2n = 2 · 2n = 2n+1 elem van. Ezzel beláttuk, hogy a tételben kimondott tulajdonság örökl˝odik n-r˝ol n + 1-re, és ezért a teljes indukció elve szerint bebizonyítottuk a tételt. Nagyon sok dolgunk lesz még a teljes indukcióval; de az eddigiekb˝ol is megérezhettetek annyit a teljes indukciós bizonyítás módszeréb˝ol, hogy a tényleges bizonyítás elo˝ tt meg kell sejtenünk valahonnan, hogy mi lesz az eredmény. Ezt legtöbbször számpéldák alapján érjük el. 23. feladat Hány részhalmaza van az üres halmaznak? Mit érdemes ennek alapján 20 számon érteni? 24. feladat Bizonyítsátok be teljes indukcióval, hogy: 1 + 2 + · · ·+ n =

n(n + 1) . 2

25. feladat Bizonyítsátok be teljes indukcióval, hogy: 12 + 2 2 + · · · + n 2 =

n(n + 1)(2n + 1) . 6

26

1. Számoljuk össze! Bevesszük−e a részhalmazba az 1. elemet? a 2. elemet? a 3. elemet? igen

n ige

ig en

nem

nem

igen nem igen

ne m

n ige nem

nem igen nem

2. ábra. 26. feladat Bizonyítsátok be teljes indukcióval, és nélküle is, hogy n(n + 1) páros szám! 7. Nézzünk meg egy másik, nem teljes indukciós bizonyítást el˝oz˝o tételünkre: Azt kell kiszámítanunk, hogy hányféleképpen tudunk kiválasztani egy részhalmazt. Egy részhalmaz kiválasztásakor elo˝ ször is el kell dönteni, hogy az els˝o elemet bevesszük-e a halmazba. Akárhogyan is döntöttünk azonban efelo˝ l, a második elemmel kapcsolatban is el kell határoznunk, hogy bevesszük-e a tekintett részhalmazba. Ábrázoljuk ezeket a döntéseket! (2. ábra.) Az, hogy a részhalmazt megadjuk, azt jelenti, hogy mindezekre a kérdésekre felelünk; más szóval, hogy a bal oldali végpontból kiindulva végighaladunk az ábrán, és eljutunk egy jobb

1. Számoljuk össze!

1

0

1

1

27

0

3. ábra. oldali végpontba. A kérdés tehát csak ez: hány jobb oldali végpont van? Erre azonban könny˝u felelni: az elso˝ kérdés utáni oszlopban két pont van (mert a kérdésre két lehetséges válasz adható). Ezekután mindkét ág két újabb ágra bomlik, tehát a második kérdés utáni oszlopban kétszer annyi, vagyis 4 pont szerepel. A harmadik kérdés utáni oszlopban megint kétszer ennyi, vagyis 8 pont fog szerepelni. Ha – az ábrával ellentétben – n > 3, akkor is ugyanígy mehetünk tovább. Az n-edik kérdés után 2 n végpont lesz. Végül nézzünk meg egy harmadik bizonyítást is! Rakjuk sorba a tekintett halmaz elemeit valahogyan. Vegyünk most egy részhalmazt. Vegyük sorra a halmaz elemeit, és írjunk 1-est, ha a tekintett elem a részhalmazhoz tartozik, illetve 0-t, ha a tekintett elem nem szerepel a részhalmazban (3. ábra). A leírt számjegyeket tekinthetjük egy n-jegy˝u 2-es számrendszerbeli számnak. Lehet ugyan, hogy ez a szám valahány 0 számjeggyel kezd˝odik, ekkor az elején lev˝o 0-kat nem kell figyelembe venni. A részhalmazokat tehát megszámoztuk, mindegyik egy (2-es számrendszerbeli alakjában), legfeljebb n-jegy˝u számot kapott. Felhasználtunk-e minden, legfeljebb n jegy˝u számot? Igen, mert akármelyik számhoz el tudjuk készíteni a megfelelo˝ részhalmazt, egyszer˝uen úgy, hogy kivesszük azokat az elemeket, amelyeknek megfelel˝o számjegy 1-es. Kérdések: Melyik részhalmaz felel meg a 0 számnak? Mely számok felelnek meg az 1 elem˝u részhalmazoknak?

28

1. Számoljuk össze!

Az eddigiekb˝ol most már annyit tudunk, hogy pontosan annyi részhalmaz van, ahány legfeljebb n-jegy˝u 2-es számrendszerbeli szám van (a 0-t is beleértve). Ezek után csak azt kell megszámolnunk, hogy hány ilyen szám van. Éppen annyi, amekkora a legels˝o n + 1 jegy˝u szám. Melyik is ez? 2-es számrendszerbeli alakja: 100 . . .0 (n darab 0 van az l-es után). Ez 2n , tehát a legfeljebb n-jegy˝u számok: 0, 1, 2, 3, . . . , 2n − 1. Vagyis számuk 2n . Ezzel a bizonyítást befejeztük. 27. feladat Hány, legfeljebb n-jegy˝u szám van a 10-es számrendszerben? Általában p alapú számrendszeren? 8. Ha már itt tartunk, természetesen felveto˝ dik az a kérdés, hogy hány, pontosan n-jegy˝u szám van p alapú számrendszerben. Egy pontosan n jegy˝u szám kisebb, mint pn , de legalább pn−1 . Így számuk pn − pn−1 = p · pn−1 − pn−1 = (p − 1)pn−1. Ezt a feladatot úgy is megfogalmazhatjuk, hogy azokat az njegy˝u számokat kell összeszámolnunk, amelyeknek elso˝ jegye adott p − 1 számjegy valamelyike, a további jegyek pedig adott p számjegy közül kerülnek ki. Ezt a feladatot általánosabban is föl lehet vetni, a következ˝o formában. Számoljuk össze azokat az n elem˝u sorozatokat (rendezett halmazokat), melyeknek els˝o eleme egy bizonyos els˝o halmazba, második elemük egy második halmazba, és így tovább, n-edik elemük egy adott n-edik halmazba esik. Az elso˝ halmaz elemeinek számát jelöljük a1 -gyel, a másodikét a2 -vel, és így tovább, az n-edikét an -nel. Nézzük meg az el˝oz˝o két problémánkat így átfogalmazva! A 27. feladatban a sorozat minden eleme, vagyis az n-jegy˝u szám mindegyik jegye a {0, 1, . . . , p − 1} számhalmazba kellett hogy essen, ekkor tehát a1 , a2 , . . . , an mindegyike p. Eredményül azt kaptuk ebben az esetben, hogy az ilyen sorozatok száma pn = p · p · · · p (n darab tényez˝o van). Egy pontosan n-jegy˝u szám viszont olyan sorozatot jelent, amelynek elso˝ jegye az {1, 2, . . ., p − 1} halmazba, további jegyei a {0, 1, . . . , p − 1} halmazba esnek. Ekkor tehát a1 = p − 1, a2 = a3 = · · · = an = p. A végeredmény (p − 1) · p · · · p volt.

1. Számoljuk össze!

29

Ebb˝ol a két példából az a sejtésünk támadhat, hogy a tekintett sorozatok száma a1 · a2 · · · an . Be is bizonyítjuk ezt, méghozzá teljes indukcióval. Ha n = 1, akkor 1 elem˝u sorozatokat kell tekintenünk, és erre az elemre a1 lehet˝oség van. Ilyen sorozat tehát valóban pontosan a1 van. Tegyük fel most, hogy n − 1 elem˝u sorozatra az állítás igaz, vagyis, hogy azoknak a sorozatoknak a száma, melyeknek els o˝ eleme az els˝o halmazból, második eleme a másodikból, és így tovább, (n − 1)-edik eleme az (n − 1)-edik halmazból van, pontosan a1 · · · an−1 . Ez az indukciós feltevésünk. Meg akarjuk számolni a fent leírt elem˝u sorozatokat. E célból csoportosítsuk o˝ ket aszerint, hogy mi az utolsó elemük. Egy-egy ilyen csoportban az n-edik elem ugyanaz, tehát an darab csoport van. Mindegyik csoportban annyi sorozat szerepel, ahányféleképpen az els o˝ n − 1 elemb˝ol álló sorozatot választhatjuk a feltételeknek megfelel˝oen. Az indukciós feltevésünk szerint azonban a megfelel o˝ n − 1 elem˝u sorozatoknak a száma a1 · · · an−1 , így ennyi elem van egy-egy csoportban. Az an darab csoport így összesen a1 ·a2 · · · an darab sorozatot tartalmaz. Ezzel igazoltuk sejtésünket. 28. feladat A bevezetésben megbeszélt problémák közül melyiket oldottuk meg ezzel újra? 29. feladat Egy sportboltban négyfajta szín˝u futballmez, három különböz˝o szín˝u nadrág és kétfajta lábszárvéd˝o kapható. Hányféle felszerelést lehet ebb˝ol összeállítani? (Bármely kett˝onek legalább az egyik ruhadarabja különböz˝o legyen.) 30. feladat Hányféleképpen lehet kitölteni egy totószelvényt? (13 rovat, mindegyikbe az 1, 2, × jelek közül egyet kell írni.)

31. feladat Feldobunk egy piros és egy fehér dobókockát. Hány különböz˝o eredményt kaphatunk? (A piros 1-es, fehér 4-es dobás más, mint a piros 4-es, fehér 1-es.) Hányféle eredmény lehet, ha nem tudjuk megkülönböztetni a két kockát?

32. feladat Van 20 különböz˝o ajándéktárgyunk. Ezeket 12 gyerek között akarjuk szétosztani. Hányféleképpen tehetjük ezt meg?

30

1. Számoljuk össze!

(Nem kell, hogy minden gyerek kapjon valamit, akár egyetlen gyerek is megkaphatja mindegyik tárgyat.) 9. Egy futóversenyen n versenyzo˝ indul, de csak az els˝o k helyen végzett versenyz˝ok sorrendjét jegyzik. A bevezetésben 90 versenyz˝o és az els˝o 5 hely esetére kiszámítottuk, hogy hány lehetséges végeredmény van. Most egy másik, rövidebb utat fogunk követni az általános eset megoldására, de mindenkinek igen tanulságos lesz, ha annak mintájára, ahogy a bevezetésben csináltuk, végiggondolja az általános esetet. Azt már tudjuk, hogy ha az összes versenyzo˝ helyezését jegyeznénk, akkor n! lehet˝oség volna. De ezekb˝ol a lehet˝oségekb˝ol nem különböztetjük meg azokat, amelyek csak az utolsó n − k versenyz˝o sorrendjében különböznek egymástól. Csoportosítsuk az összes (azaz n! darab) végeredményt úgy, hogy az ilyeneket egy csoportba rakjuk. Most – az eddigiekto˝ l eltér˝oen – a csoportok számára vagyunk kíváncsiak. Mivel tudjuk, hogy a csoportokban együttvéve n! darab elem van, azt kell még megnéznünk, hogy hány elem van egy-egy csoportban. De ez éppen annyi, ahányféle sorrendben az utolsó n − k versenyzo˝ végezhet, vagyis (n − k)!. A csoportok száma tehát: n(n − 1) · · ·(n − k + 1)(n − k) · · ·2 · 1 n! = = (n − k)! (n − k) · · ·2 · 1 = n · (n − 1) · · ·(n − k + 1). Az, hogy itt futóversenyr˝ol és versenyz˝ok helyezésér˝ol beszéltünk, csak a fogalmazás szemléletességét segítette elo˝ . Ugyanígy tetsz˝oleges halmaz esetére is okoskodhatunk, és akkor az alábbi tételt kapjuk: Tétel Egy n elem˝u halmazból kiválasztható k elem˝u sorozatok száma: n · (n − 1) · · ·(n − k + 1).

Más szóval: egy n elem˝u halmaznak n · · · (n−k +1) darab rendezett k elem˝u részhalmaza van. Itt minden részhalmazt többször is beszámítottunk, mindig másképpen rendezve. So˝ t pontosan is

1. Számoljuk össze!

31

meg tudjuk mondani, hogy hányszor számítottuk be: ahányféleképpen rendezhet˝o, vagyis k!-szor. A k elem˝u sorozatok száma tehát k!-szorosa a k elem˝u részhalmazok számának; más szavakkal: Tétel Egy n elem˝u halmaz k elem˝u részhalmazainak száma: n! n · (n − 1) · · ·(n − k + 1) = . k! k!(n − k)! Ez utóbbi kérdés már a fejezet elején is többször elo˝ fordult (például a kézfogások számánál, a lottónál, a kártyajátékoknál). Nem meglep˝
o ezért, hogy az eredményre külön jelölést is bevezettek: nk -val (olvasd: n alatt a k) jelölik. Tehát:   n n! = . k (n − k)!k!
Így például a lottószelvények száma: 90 , a kézfogások száma 5
7 2 , és így tovább.
89
89
33. feladat Bizonyítsátok be, hogy 90 5 = 5 + 4 .
n
34. feladat Bizonyítsátok be, hogy nk = n−k . 35. feladat Bizonyítsátok be, hogy         n n n n 2n = 1 + + + ···+ + . 1 2 n−1 n

Próbáljatok ezekre a feladatokra olyan megoldást is találni,
amelyben nem számoltok, hanem abból indultok ki, hogy nk a k elem˝u részhalmazok számát jelenti.

10. A 32. feladatban (konkrét számok helyett bet˝ukkel felírva) azt kérdeztük, hogy hányféleképpen lehet szétosztani n ajándéktárgyat k gyerek között. Itt megengedtük azt az igazságtalanságot, hogy akár mindegyik ajándéktárgyat ugyanaz a gyerek kapja. Hogy ezt kiküszöböljük, írjuk elo˝ , hogy az egyes gyerekeknek hány ajándéktárgyat kell kapniuk: az elso˝ n1 -et, a második n2 -t, és

32

1. Számoljuk össze!

így tovább a k-adik nk -t. Természetesen ezt úgy értjük, hogy minden ajándéktárgyat kiosztunk, vagyis n1 + n2 + · · · nk = n. Hányféleképpen valósíthatjuk meg a kiosztást? Végezzük a kiosztást a következ˝oképpen: Rakjuk sorba az ajándéktárgyakat. Az els˝o gyereknek odaadjuk az els˝o n1 darabot. A második megkapja a maradékból az elso˝ n2 darabot. Ugyanígy folytatva tovább, a (k − 1)-edik megkapja az ekkor még meglev o˝ ajándékok közül az els˝o nk−1 darabot. A k-adik gyereknek jut a maradék, ami nyilván nk darab. Ha az eredeti sorbarakást változtatjuk, akkor a fentieket követve minden kiosztást megkapunk. De hányszor? Ha valahogyan ki vannak osztva az ajándékok, megkérhetjük a gyerekeket, hogy rakják össze az ajándékaikat, méghozzá úgy, hogy elo˝ ször az els˝o gyerek leteszi a saját tárgyait valamilyen sorrendben, a második gyerek utánarakja az övéit, és így tovább. Ha ebbo˝ l a sorrendb˝ol indulnánk ki, minden gyerek a saját tárgyait kapná vissza. Azt kell tehát megszámolnunk, hányféleképpen rakhatják vissza a gyerekek a fent leírt módon az ajándékaikat, hiszen ennyiszer kapjuk meg a kiosztást különbözo˝ sorrendekb˝ol kiindulva. Az els˝o gyerek n1 ! sorrend közül választhat ajándékainak visszarakásakor, a második n2 ! sorrend közül és így tovább. Az együttes visszarakások száma ezek szerint n1 ! · n2! · · · nk !. Visszatérve mármost az eredeti kérdésre, azt a sorbarakást, amelyb˝ol kiindultunk, n!-féleképpen választhatjuk. A kapott kiosztások azonban nem lesznek mind különbözo˝ ek, hanem mindegyik n1 ! · n2! · · · nk !-szor lép fel. Tehát számuk: n! . n1 ! · n 2 ! · · · n k ! 36. feladat Vezessétek le a fenti eredményt abból kiindulva, hogy egy kiosztást úgy kapunk, hogy az n elemb˝ol kiválasztunk n1 -et, a maradék n − n1-b˝ol n2 -t és így tovább! 37. feladat Mit kapunk az alábbi speciális esetekben: a) n = k, n1 = n2 = · · · = 1;

1. Számoljuk össze!

33

4. ábra. b) n1 = n2 = · · · = nk−1 = 1, nk = n − k + 1; c) k = 2?

38. feladat Hányféleképpen tudunk egy sakktáblán 8 bástyát elhelyezni úgy, hogy egyik se üsse a másikat, feltéve, hogy a bástyák egyformák (megkülönböztethetetlenek)? Egy ilyen lehetséges elhelyezést mutatunk a 4. ábrán. 39. feladat Hányféleképpen végezhet˝o el ugyanez, ha 4 piros és 4 zöld bástyánk van? 40. feladat Hány elhelyezés lehetséges akkor, ha mind a 8 bástya különböz˝o (például más-más készletb˝ol van)? 11. Biztosan ismeritek az anagrammakészítést; meg kell adni egy szót (például stílusosan azt, hogy KOMBINATORIKA), és ennek a bet˝uib˝ol értelmes mondatot vagy kifejezést kell összerakni. Kérdés mármost, hány anagrammát lehet alkotni egy szóra? Ha anagrammákat kezdetek gyártani, rögtön észreveszitek a kérdés pontatlanságát: nem fogtok egyetérteni abban, hogy mikor értelmes egy kapott mondat. Abban még mindenki egyetért, hogy a Népszabadság olvasója valóban felkiálthat így: NO , MA TABI -

34

1. Számoljuk össze!

KROKI . Ezen krokik szerz˝ oje mondhatja: ROKONAIM TABIK. De ahhoz már külön állatmesét kell kitalálni, hogy szerepelhessenek MAKI - BARITONOK. Hogy az ilyen vitáknak elébe vágjunk, fogadjunk el minden anagrammát jónak; tehát azt se követeljük meg, hogy értelmes vagy akár kiejtheto˝ szavakból álljon. Persze így nem érdekes az anagrammakészítés; viszont annak a kérdésnek ekkor már van értelme, hogy hány anagramma készítheto˝ egy adott szóból. Tehát:

41. feladat Hány anagramma készíthet˝o a szóból?

KOMBINATORIKA

Csináljatok most anagrammát a NO , MA TABI - KROKI mondatra! Jogos a közbevágás: Ugyanazokból a bet˝ukb o˝ l kell anagrammát faragni, mint az el˝obb, és így ugyanazokat az anagrammákat lehet készíteni! Más szóval, ez ugyanaz a feladat. Így most már világos, hogy nem minden 13 bet˝us szöveg ad új anagrammafeladatot. Tehát meg lehet kérdezni: 42. feladat Hány 13 bet˝us szöveg van, és hány különböz˝o anagrammafeladatot kapunk bel˝olük? Ha az utóbbi kérdésre nem tudjátok a választ, olvassátok el a következ˝o pontot és azután próbálkozzatok újra! 12. Most nem ajándéktárgyakat, hanem pénzt akarunk kiosztani a gyerekek között. Reméljük, hogy már eléggé megszoktátok a bet˝us (algebrai) jelöléseket ahhoz, hogy egybo˝ l így fogalmazhassuk a feladatot: n forintot akarunk szétosztani k gyerek között. Csak arra vigyázunk, hogy mindegyikük egész számú forintot kapjon, és legalább egyet (el akarjuk kerülni az egyik régebbi feladatban elkövetett igazságtalanságot). Hányféleképpen tehetjük ezt meg? Miel˝ott belekezdenénk a feladat megoldásába, gondoljuk csak meg, hogy mi a különbség az ajándékosztás és a forintosztás között. Az ajándékosztásnál nemcsak azt kell megmondanunk, ki hány ajándékot kap, hanem azt is, hogy melyek ezek az ajándékok. Forintosztásnál viszont csak az az érdekes, hogy ki hány

1. Számoljuk össze!

35

forintot kap. Más szóval az ajándékok megkülönböztetheto˝ k, míg az egyes forintok nem. Most, mikor a könyvet írjuk, éppen meleg nyár van, ezért természetes, hogy a gyerekek fagylaltot akarnak venni a pénzükön. Legegyszer˝ubb, ha mindjárt fagylaltjegyeket osztunk ki közöttük. Gombócos fagylaltjegyeink vannak egy hosszú szalagban, letépünk ebb˝ol egy n hosszúságú darabot (vagyis n jegyet) s ezt akarjuk szétosztani a k gyerek között. A szalagot tehát k részre kell széttépnünk. Az els˝o gyereknek adjuk az els˝o darabját, a másodiknak a másodikat és így tovább. Azt kell tehát eldöntenünk, hogy melyik perforálásoknál tépjük el a szalagot. Ha k részre akarjuk széttépni a szalagot, akkor k − 1 helyen kell eltépnünk. Mivel az n jegyb˝ol álló szalag n − 1 helyen van perforálva, a szalagot annyiféleképpen téphetjük k részre, ahányféleképpen az n − 1 perforálásból kiválaszthatjuk azt a k − 1 helyet, ahol eltép
jük a szalagot. Ezt pedig már tudjuk, hogy n−1 -féleképpen tek−1 hetjük meg. Az, hogy megoldás közben fagylaltjegyekro˝ l beszéltünk, a megoldás értékét nem csökkenti, viszont okoskodásunkat szemléletessé tette. Nem akarunk ugyan igazságtalanok lenni, de a matematikai teljesség kedvéért határozzuk meg az „igazságtalan” szétosztások számát; vagyis az olyan szétosztásokat is megengedjük, amikor valamelyik (vagy akár több) gyerek egy fityinget se kap. Ismét n forintunk van, és ezt k gyerek között akarjuk szétosztani. A feladatot vissza tudjuk vezetni az elo˝ z˝ore a következ˝o trükkel: Kölcsönkérünk valakit˝ol k forintot, majd az összes pénzt (azaz n + k forintot) szétosztjuk a k gyerek között az elo˝ z˝o módon, úgy, hogy mindegyik kapjon valamit, utána visszakérünk minden gyerekt˝ol 1 forintot, és visszaadjuk a kölcsönkért k forintot. Így végeredményben n forintot osztottunk szét a gyerekek között. S˝ot azt is megállapíthatjuk, hogy az n forint minden lehetséges kiosztásához így is eljuthatunk, éspedig egyféleképpen. Tehát annyiféleképpen tudjuk szétosztani az n forintot a k gyerek között, ahányféleképpen az n + k forintot az elo˝ z˝o, igazságosabb módon
szétoszthattuk közöttük. Mint az imént láttuk, ez éppen n+k−1 k−1 -féleképpen történhet.

36

1. Számoljuk össze!

43. feladat Hányféleképpen lehet n forintot szétosztani k gyerek között úgy, hogy mindegyik kapjon legalább 2 Ft-ot? Próbáljátok meg általánosítani a feladatot! 44. feladat k gróf kártyázik. Eredetileg mindegyiknek p peng˝oje van. A játék végén összeszámolják, hogy ki hány peng˝ot nyert vagy vesztett. Hány lehetséges kimenetel adódhat? (Egyikük sem kér kölcsön játék közben, tehát legfeljebb a saját p peng˝ojét veszti el.) 45. feladat n forintot osztunk szét k fiú és l lány között úgy, hogy a lányok mindegyike kapjon legalább 1 forintot. Hányféleképpen lehetséges ez?

2 Kombinatorika a számtanban

1. Nézzétek meg újra a 33. feladatot az elo˝ z˝o fejezetben! Ez volt az állítás:       90 89 89 = + (1) 5 5 4

Nem lehetne-e ezt a feladatot általánosítani? Talán igaz marad az (1)-gyel jelölt egyenl˝oség akkor is, ha 90, 89, 5, 4 helyett más számokat írunk be. Persze akármit nem írhatunk be helyettük, hiszen az valószín˝uleg lényeges, hogy a 89 éppen eggyel kisebb, mint 90, a 4 pedig eggyel kisebb, mint az 5. Egy kis kísérletezés után megvan az ötlet: Nem igaz-e mindig, hogy       n n−1 n−1 = + (2) k k k−1 hacsak n és k olyan természetes számok, hogy n > k? Azt már tudjuk az (1) egyenl˝oségb˝ol, hogy ha n = 90 és k = 5, akkor ez igaz. De igaz-e általában? Igaz. Ezt a következo˝ képpen láthatjuk be: Tegyük fel, hogy egy zsákban van n db golyónk, köztük pontosan egy fekete. Hányféleképpen választhatunk ki k db golyót a

38

2. Kombinatorika a számtanban

zsákból? Erre a kérdésre
a választ már az elo˝ z˝o fejezetb˝ol tudjuk: n elemb˝ol k db nk -féleképpen választható ki. Másrészt, ha kiválasztunk k db golyót, két eset lehetséges: vagy köztük van a fekete golyó, vagy nincs. Hány olyan kiválasztás van, ami tartalmazza a fekete golyót? Minden ilyen kiválasztást úgy kaphatunk, hogy az n − 1 nem fekete golyó közül kiválasztunk k − 1 darabot, és hozzávesszük a fekete golyót. És ha különbözo˝ (k − 1)-eseket veszünk ki a nem fekete golyók közül, természetesen különböz o˝ k-asok adódnak a fekete golyó hozzávétele után. Tehát a fekete golyót tartalmazó k-as annyi van,
ahányféleképpen n − 1 elemb o˝ l kiválasztható k − 1, azaz n−1 van, ami nem k−1 . És hány olyan k-as
n−1 tartalmazza a fekete golyót? Természetesen k db, hiszen az n − 1 nem fekete golyóból kell k darabot kiválasztani. Tehát az
n−1
adódott, hogy n golyó közül k-t n−1 + -féleképpen lehet k k−1 kiválasztani. Ebb˝ol már következik a (2) egyenl˝oség helyessége. 2. A most talált egyenl˝oségnek mindjárt látni fogjuk egy érdekes alkalmazását is. Csináljunk egy háromszög
alakú sémát, amilyet az 1. ábra mutat! „Nulladik sorába” a 00 szám kerül,




els˝o sorába az 10 és 11 számok, második sorába 20 , 21 és 22 ,


és így tovább, általában az n-edik sorba n0 , n1 , . . . , nn . Méghozzá mindegyik sort fél hellyel balra csúsztatjuk az elo˝ z˝ohöz képest, úgyhogy egy piramis-, vagy más szóval háromszög alakú sémát kapunk (1. ábra). Ezt a „piramist” Pascal-háromszögnek nevezik. Nevét Pascalról (ejtsd: Paszkál) a XVII. században élt francia matematikusról kapta.

Mennyi a 00 értéke? Tudjuk, hogy a definíció szerint nk = 0
0! n! o fejezetben már meg(n−k)!k! . Tehát 0 = 0! 0! = 1, mivel az els˝ állapítottuk, hogy 0! = 1. Ugyanígy meghatározhatjuk sorban a
Pascal-háromszögben szerepl˝o nk számokat, és akkor a 2. ábrán n
látható Pascal-háromszöget kapjuk, ahol az k számok nem ebben a formában szerepelnek, hanem az értékük van feltüntetve. Általában ebben a formában szerepel a Pascal-háromszög (2. ábra).

2. Kombinatorika a számtanban

39

.. .


0 0



1 .. 1 0 .
1

2 2 2

..

.

0 4
0

3
0

4
1

3
1

1

2

2

3


.. 3
.
2
33
4 4 4 .. .

4

..

.

1. ábra. 1 1 1 1 1 1 1

1

3 4

5 6

1 2 3 6

10 15

1 4

10 20

1 5

15

1 6

1

2. ábra. 1. feladat Bizonyítsuk be, hogy akármeddig folytatjuk is a Pascal-háromszöget, minden sorban 1 lesz a két széls˝o elem. 2. feladat Bizonyítsuk be, hogy a Pascal-háromszög szimmetrikus a csúcsán keresztül húzott függ˝oleges egyenesre. (Az 1. ábrán szaggatott vonallal jelöltük.) Nézzük most a 2. ábrán látható Pascal-háromszög negyedik sorát: 1 4 6 4 1 (ne felejtsük el, hogy a sorok számozását nullával kezdtük!). Ebben a sorban pl. a második elem egyenlo˝ a felette álló két elem összegével: 4 = 1 + 3. Ugyanígy a sor harmadik eleme is egyenl˝o a felette álló két elem összegével: 6 = 3 + 3. Ha más eseteket is kipróbálunk, mindig ugyanazt tapasztaljuk: A Pascal-háromszögben minden, nem a szélén álló elem (ami fölött tehát két másik elem áll) egyenlo˝ a felette álló két szám összegével.

40

2. Kombinatorika a számtanban

Ezt az állítást azonban még be kell bizonyítani. Vegyünk ebbo˝ l a célból egy tetsz˝oleges elemet a Pascal-háromszögbo˝ l: az n-edik sor k-adik elemét. Az, hogy ez nincs a szélen, azt jelenti, hogy k 6= 0 és k 6= n. E fölött az elem fölött állnak: az (n − 1)-edik sor (k − 1)-edik és k-adik eleme. Azt akarjuk bizonyítani, hogy e két elem összege éppen egyenl˝o az n-edik sor k-adik elemével, tehát, hogy       n−1 n−1 n + = , k−1 k k hacsak 0 < k < n. De ezt már bebizonyítottuk, hiszen ez éppen a (2) egyenl˝oség! A Pascal-háromszögnek ezt a tulajdonságát akkor a legérdemesebb felhasználni, ha folytatni akarjuk a 2. ábrán látható Pascal-háromszöget. Nem kell ugyanis mást csinálnunk, mint a két széls˝o helyre 1-et írni, a sor többi helyére pedig az illeto˝ hely felett álló két szám összegét. Most már ti is könny˝uszerrel folytatni tudjátok a Pascal-háromszöget akármeddig. 3. A Pascal-háromszögnek sok érdekes tulajdonsága van, pl. az, hogy az n-edik sorában álló számok összege 2n . Ezt már bebizonyítottuk, nézzétek csak meg az I. fejezet 35. feladatát! Az ottani bizonyítás egy halmaz részhalmazainak megszámolásával történt. Most egy második bizonyítást fogunk látni ugyanerre az állításra, teljes indukcióval: A nulladik sorban álló elem egy van: 1 és valóban 20 = 1. Az els˝o sorban is valóban: 1 + 1 = 21 . Tegyük fel, hogy már tudjuk: az n-edik sorban álló elemek összege 2n . Nézzük az (n + 1)-edik sort! Itt (a két széls˝o egyest kivéve) minden elem helyébe beírhatjuk, hogy egyenl˝o a felette (az n-edik sorban) álló két elem összegével. Hogy könnyebben el tudjuk képzelni ezt, példaképpen tekintsük a Pascal-háromszög 5. és 6. sorát (azaz legyen pl. n = 5). Akkor ezt kapjuk: 1 + 6 + 15 + 20 + 15 + 6 + 1 = 1 + (1 + 5)+ + (5 + 10) + (10 + 10) + (10 + 5) + (5 + 1) + 1.

(3)

2. Kombinatorika a számtanban

41

Így tehát az (n + 1)-edik sor elemeinek az összege helyett az n-edik sor elemeib˝ol képzett összeget kapunk, amelyben az nedik sor minden eleme kétszer szerepel: egyszer azon a jogcímen, hogy o˝ a t˝ole jobbra lefelé lev˝o elem fölötti szám a Pascalháromszögben, egyszer pedig azon a jogcímen, hogy o˝ a t˝ole balra lefelé álló elem fölötti szám. Azazhogy mégsem! Az n-edik sor két széls˝o 1-esét csak egyszer-egyszer vesszük számba: a bal oldali 1-est akkor, amikor a t˝ole jobbra lefelé álló számot bontjuk fel összegre, a jobb oldali 1-est pedig akkor, amikor a to˝ le balra lefelé lev˝o számot bontjuk fel összegre. Csakhogy ezt a hiányt éppen kipótolja az, hogy az (n + 1)-edik sorban is van két széls o˝ 1-es, amit idáig nem vettünk számba. Tehát tényleg igaz, hogy az (n + 1)-dik sor elemeinek összege éppen kétszerese az n-edik sor elemei összegének. Szemléltetésképpen nézzük ismét az n = 5 esetet. Ekkor a (3) egyenl˝oség így folytatható: 1 + (1 + 5) + (5 + 10) + (10 + 10) + (10 + 5) + (5 + 1) + 1 = = (1 + 1) + (5 + 5) + (10 + 10) + (10 + 10) + (5 + 5) + +(1 + 1) = 2 · (1 + 5 + 10 + 10 + 5 + 1).

Visszatérve az általános esethez: beláttuk már, hogy az (n + 1)-edik sor elemeinek összege kétszerese az n-edik sor elemei összegének. Viszont azt már az indukciós feltevésbo˝ l tudjuk, hogy az n-edik sorban álló elemek összege 2n . Tehát az (n + 1)edik sorban álló elemek összege: 2 · 2n = 2n+1 . Ezzel befejeztük annak az állításnak teljes indukciós bizonyítását, hogy a Pascalháromszög n-edik sorában álló elemek összege 2n . Ez az állítás még így is írható:       n n n + + ···+ = 2n . (4) 0 1 n Kés˝obb még egy harmadik módon is be fogjuk látni a (4) alatti azonosságot.

3. feladat Hányféleképpen lehet a 3. ábrán látható alakzatról (felülr˝ol lefelé haladva) leolvasni a KOMBINATORIKA szót? (Milyen kapcsolat van e feladat és a Pascal-háromszög között?)

42

2. Kombinatorika a számtanban K O M B N

N A

B I

I A

I N

A T

O R

B

I

A

O

M B

N

T

T

O M

A T

O R

I

N A

T O

R I

K

I N

A T

O R

I K

A

3. ábra. 4. feladat Vegyünk a Pascal-háromszög jobb szélér˝ol egy 1-est, azután az ett˝ol balra lefelé lev˝o elemet, majd az ett˝ol balra lefelé lev˝o elemet, ett˝ol is a balra lefelé lev˝o elemet, egészen egy bizonyos utolsó elemig. Igaz-e, hogy ha ezeket az elemeket mind összeadjuk, összegként mindig az utolsó elemt˝ol jobbra lefelé lev˝o elem adódik? (Például 1 + 3 + 6 + 10 = 20.) 4. Fejezzük most ki az (x + y) kifejezés különbözo˝ hatványait! (x + y)2 = (x + y) · (x + y) = x2 + xy + yx + y2 = x2 + 2xy + y2. (x + y)3 = (x + y) · (x + y)2 = (x + y) · (x2 + 2xy + y2) = = x3 + 2x2 y + xy2 + yx2 + 2xy2 + y3 =

= x3 + 3x2 y + 3xy2 + y3 . Ugyanígy számolhatunk tovább, és kapjuk: (x + y)4 = x4 + 4x3 y + 6x2y2 + 4xy3 + y4 . (x + y)5 = x5 + 5x4 y + 10x3y2 + 10x2y3 + 5xy4 + y5

stb.

Ugye észrevettétek már, hogy az együtthatók ugyanazok a számok, mint amik a Pascal-háromszögben szerepelnek? De nem véletlen-e ez?

2. Kombinatorika a számtanban

43

Nézzük meg (x + y)n kifejtését! Tudjuk, hogy (x + y)n n darab (x + y) kifejezés szorzata. Ha a beszorzást tényleg elvégezzük, ilyen tagok fognak szerepelni: xn , xn−1 y, xn−2 y2 , . . . , xyn−1 , yn . Melyik hányszor fog szerepelni? Hányszor szerepel például az xn−k yk ? xn−k yk -hoz úgy juthatunk, hogy az n db (x + y) szorzótényez˝o közül k darabból az y-t választjuk, a többibo˝ l az x-et, és ezeket szorozzuk össze. Az xn−k yk tag annyiszor fog el˝ofordulni, ahányféleképpen ki tudjuk választani az n db (x + y) tényez o˝ közül azt a k
darabot, amib˝ol majd az y-t vesszük ki. De ezt, mint jól n n−k yk tag tudjuk, k -féleképpen lehet kiválasztani. Így tehát az x n
ofordulni. Mivel ez minden 0 és n közé eso˝ k-ra k -szor fog el˝ igaz, végeredményben ezt kaptuk:       n n n n−1 n n−2 2 n (x + y) = x + x y+ x y + ···+ 0 1 2     n n n + xyn−1 + y = n−1 n     n n−1 n n−2 2 = xn + x y+ x y + ···+ 1 2   n + xyn−1 + yn. n−1 A most bebizonyított állítás igen fontos, és gyakran kerül alkalmazásra. Külön neve is van: binomiális tétel. (Ugyanis egy kéttagú összeg, idegen szóval binom hatványáról szól.
A binomiális tételben való el˝ofordulásuk miatt szokták az nk számokat gyakran binomiális együtthatóknak nevezni.) Alkalmazzuk most a binomiális tételt úgy, hogy x és y helyébe egyaránt 1-et írunk. Így ezt kapjuk:       n n n n 2 = + + ···+ . 0 1 n Egy újabb (immár harmadik) bizonyítást nyertünk a (4) egyenlo˝ ségre!

44

2. Kombinatorika a számtanban

5. feladat Bizonyítsátok be, hogy           n n n n n = 0. − + − ± · · · + (−1)n n 0 1 2 3 (Az összeg minden második tagja pozitív, a többi negatív el˝ojellel szerepel. Feltesszük, hogy n > 0.) Be tudnátok-e látni az állítást páratlan n esetén a binomiális tétel felhasználása nélkül? 5. Számos kombinatorikai egyenlo˝ ség bebizonyítására két út is kínálkozik: egyrészt a binomiális tételen keresztül, másrészt azzal az ötlettel, hogy megpróbálunk valami olyan mennyiséget találni, amit kétféleképpen is ki lehet számítani, és egyik kiszámítási mód a bizonyítandó egyenlo˝ ség egyik oldalán álló, a másik kiszámítási mód pedig a másik oldalon álló mennyiségre vezet. Ezzel ugyanis a két mennyiség egyenlo˝ sége rögtön bizonyítást nyer. A kétféle módszert egy példán mutatjuk be: Lássuk be, hogy  2    2  2  2 2n n n n n = . + ···+ + + n n 2 1 0

(5)

Els˝o bizonyításunkhoz induljunk ki az (1 + x)n(1 + x)n = (1 + x)2n azonosságból. Ha a jobb oldalt a binomiális tétel szerint kifejt
jük, látjuk, hogy xn együtthatója 2n n lesz. Másrészt, ha a bal oldal mindkét tényez˝oje helyébe a binomiális tétel szerint a vele egyenl˝o kifejezést írjuk:         n n n 2 n n (1 + x)n = + x+ x + ···+ x , 0 1 2 n akkor mi lesz összeszorzás után xn együtthatója? xn a szorzatban keletkezhet úgy, hogy az elso˝ tényez˝ob˝ol az x-et nem tartalmazó, a másodikból pedig az xn -t tartalmazó
ta
got vesszük. Az ehhez tartozó két együttható szorzata: n0 · nn .

2. Kombinatorika a számtanban

45

Azután úgy is keletkezhet a szorzatban xn , hogy az els˝o tényez˝ob˝ol az x-et, a másodikból az xn−1 tagot vesszük.
-t tartalmazó n
Ekkor az együtthatók szorzata n1 · n−1 . Keletkezhet továbbá a szorzatban xn úgy, hogy az els˝o tényez˝ob˝ol x2 -t, a másodikból xn−2 -t vesszük, továbbá, hogy az elso˝ b˝ol x3 -t, a másodikból xn−3 -t vesszük stb., végül úgy, hogy az elso˝ b˝ol xn -t, a másodikból pedig az x-et nem tartalmazó tagot vesszük. Mindezeknek az együtthatóknak az összege szükségképpen egyenlo˝ a más módon
talált 2n -nel. Tehát n               n n n n n n 2n · + · + ···+ · = . (6) 0 n 1 n−1 n 0 n

n Figyelembe véve még, hogy nk = n−k , és ezt a bal oldalon minden szorzat második tényez˝ojénél felhasználva, kapjuk:  2    2  2 2n n n n = , + ···+ + n n 1 0 amit bizonyítani kellett. Ugyanezt a feladatot másképpen is megoldhattuk volna: Képzeljünk el egy zsákot, amiben n fehér és n piros golyó van. Hányféleképpen
lehet ebb˝ol a 2n db golyóból kihúzni n db golyót? Tudjuk: 2n n -féleképpen. Csoportosítsuk a lehetséges kiválasztásokat (kihúzásokat)! Egy csoportba kerüljenek azok, amelyekben ugyanannyi a kihúzott fehér golyók
száma, mondjuk k. (k lehet 0, 1, 2, . . . , vagy n.) Természetesen 2n o ezen cson egyenl˝ portok elemszámainak összegével. Hány kiválasztás jut pl. abba a csoportba, amiben a k fehér golyót (és ezért n − k piros golyót) tartalmazó kiválasztások szerepelnek? Annyi, ahányféleképpen ki lehet választani a fehér golyóból k darabot
és n piros golyóból n − k darabot. n fehér golyóból k darabot nk -féleképpen lehet kiválasztani, n piros golyóból
n n − k darabot n−k -féleképpen. Mivel k db fehér golyó akármilyen kiválasztásával összepárosíthatjuk az n − k db piros golyó akármilyen kiválasztását, végeredményben azt kapjuk, hogy az

46

2. Kombinatorika a számtanban

összes olyan kiválasztások száma, ahol k db fehér és n − k db piros golyót választottunk:     n n · . k n−k Ha tehát vesszük az egyes csoportok elemszámainak összegét, végeredményben ezt kapjuk:               n n n n n n 2n · + · + ···+ · = . 0 n 1 n−1 n 0 n Ez ugyanaz, mint a (6) azonosság, és most már a bizonyítást ugyanúgy fejezhetjük be, mint az elo˝ bb. Az alábbi azonosságok bizonyításához az e fejezetben leírt módszerek egyike vagy másika használható:            n+m n m n m n m 6. feladat = + +· · ·+ k 0 k 1 k−1 k 0 (k ≤ n és k ≤ m).         n n n n 7. feladat +2 +3 + ···+ n = n · 2n−1. 1 2 3 n          l l +1 l +2 n n+1 8. feladat + + + ···+ = . l l l l l +1 9. feladat 1 · 2 + 2 · 3 + 3 · 4 + · · ·+ (n − 1) · n =

(n − 1)n(n + 1) . 3

6. Van-e Budapesten két olyan ember, akinek ugyanannyi hajszála van? Azt gondolhatnátok, hogy erre a kérdésre nem lehet válaszolni, hiszen például te sem tudnád megmondani, ugye, hogy hány hajszálad van. Annyit mégis biztosan tudunk (mondjuk, hogy az orvosok megállapították), hogy nincs olyan ember, akinek 250 000-nél több hajszála lenne. Választ tudunk-e adni most már a kérdésre? Igen. Ugyanis Budapestnek kb. 2 millió lakosa van. Ha nem lenne két ember, akinek ugyanannyi hajszála van, akkor legfeljebb egy olyan ember lenne, akinek 0 hajszála

2. Kombinatorika a számtanban

47

van, legfeljebb egy olyan, akinek 1 hajszála, és így tovább, végül legfeljebb egy olyan, akinek 250 000 hajszála (persze az is lehet, hogy egy se). (Olyan pedig biztosan nincs, fenti megállapításunk szerint, akinek több mint 250 000 hajszála van.) De akkor Budapesten legfeljebb 250 001 ember élhetne. Mivel tudjuk, hogy ennél többen élnek, azért biztos, hogy van két ember, akinek ugyanannyi hajszála van. Megoldásunkat így is megfogalmazhatnánk: Képzeljünk el 250 001 db óriási skatulyát (akkorákat, mint például a Népstadion). Az els˝onek a felirata ez: „Azok a budapesti lakosok, akiknek 0 hajszáluk van.” A másodikba kerülnek azok, akiknek 1 hajszáluk van stb. Az utolsóba azok kerülnek, akiknek 250 000 hajszáluk van. Ha most az összes budapesti lakost betesszük az o˝ t megillet˝o skatulyába, kb. 2 millió embert helyeztünk el, de csak 250 001 skatulya van. Biztosan lesz tehát olyan skatulya, ahol 1nél több ember van. Ez az állítás olyan magától érteto˝ d˝o, hogy akár általánosságban is megfogalmazhatjuk: „Ha van n darab skatulyánk, és több mint n db tárgyat beteszünk ezekbe a skatulyákba, akkor biztosan van olyan skatulya, amelyikbe 1-nél több tárgy jutott.” Ezt az állítást hívják skatulyaelvnek. Annak ellenére, hogy ilyen egyszer˝u állítás, és mindenki azonnal látja, hogy igaz, mégis érdemes külön nevet adni neki, mert sokszor felhasználásra kerül, és nagyon sok bizonyításnak éppen a skatulyaelv az alapgondolata. A kés˝obbi fejezetekben sok példát fogunk még látni, de lássunk most mindjárt egyet: Adott n db természetes szám: a1 , a2 , . . . , an . Lássuk be, hogy kiválasztható bel˝olük egy (nem üres) részhalmaz úgy, hogy a részhalmazba tartozó számok összege osztható n-nel! (Emlékezzünk vissza az el˝oz˝o fejezetre: lehet, hogy ez a részhalmaz mind az n db számot tartalmazni fogja!) Vegyük az alábbi n db számot: b1 = a 1 b2 = a 1 + a 2

48

2. Kombinatorika a számtanban

b3 = a 1 + a 2 + a 3 .. . bn = a 1 + a 2 + a 3 + · · · + a n . Ha van ezek között a számok között n-nel osztható, akkor máris igazoltuk az állításunkat. Ha nincs, akkor osszuk el a b1 , b2 , . . . , bn számok mindegyikét maradékosan n-nel! Milyen maradékokat kaphatunk? 1-et, vagy 2-t, vagy 3-at, . . . , vagy végül (n − 1)-et. De n szám van. Tehát a skatulyaelv szerint biztosan lesz a b1 , b2 , . . . bn számok között két olyan, ami ugyanazt a maradékot adja n-nel osztva. Mondjuk, hogy két ilyen szám b i és b j (i < j). Akkor a különbségük, b j − bi osztható n-nel. De b j − bi = ai+1 + ai+2 + · · · + a j . Találtunk tehát az a1 , a2 , . . . , an számoknak egy olyan részhalmazát: ai+1 , ai+2 , . . . , a j -t, hogy az ezen részhalmazhoz tartozó számok összege osztható n-nel. Ezt akartuk bizonyítani. 10. feladat Tegyük fel, hogy 1 és 2n − 1 között (a határokat is megengedve) adott n db természetes szám! Bizonyítsuk be, hogy van köztük kett˝o, amelyiknek nincs 1-nél nagyobb közös osztója (a matematikusok úgy mondják: relatív prímek)! 7. A hatvanas években, Magyarországon egy 40 tanulóból álló osztályban a tanulók közül sokan gy˝ujtötték kedvenc beat zenekaraik fényképét. Az Illés-együttes fényképe 18 tanulónak, az Omegáé 16 tanulónak, a Metroé pedig 12 tanulónak volt meg. 7 olyan tanuló volt, akinek az Illés- és az Omega-együttes, 5 olyan, akinek az Illés- és a Metro-együttes, végül 3 olyan, akinek az Omega- és a Metro-együttes fényképe is megvolt. Olyan tanuló, aki mindhárom együttesr˝ol szerzett fényképet, 2 volt. Kérdés: hány olyan tanuló volt az osztályban, akinek a három együttes egyikér˝ol sem volt fényképe? Els˝o látásra így okoskodhatunk: 40 tanuló van az osztályban, ebb˝ol „lejön” 18 meg 16 meg 12, akiknek megvan az Illés-,

2. Kombinatorika a számtanban

49

Omega-, ill. a Metro-együttes fényképe. Marad tehát 40 − (18 + 16 + 12) = −6. A negatív eredmény máris figyelmeztet bennünket, hogy gondolatmenetünk hibás; de hol tévedtünk? Ott, hogy kétszer is leszámítottuk azokat, akiknek 2–2 együttes fényképe is megvan. Ezt helyrehozhatjuk, ha ismét hozzáadjuk o˝ ket az összeghez; azt kapjuk tehát, hogy 40 − (18 + 16 + 12) + (7 + 5 + 3). De vigyázzunk, nehogy megint az elo˝ z˝o hibába essünk! Mi van azzal a két tanulóval, akinek mindhárom együttesro˝ l van fényképe? Ezeket háromszor is levontuk az elején, de aztán háromszor is hozzáadtuk o˝ ket az összeghez, így még egyszer le kell o˝ ket számítani: 40 − (18 + 16 + 12) + (7 + 5 + 3) − 2 = 7 Ebben a képletben már nem tudunk hibát felfedezni, mint az el˝oz˝oekben, akárhogy is nézzük. De éppen az elo˝ z˝o tapasztalatok óvatosságra intenek, úgy, hogy precíz bizonyítást kell adnunk. A fenti „beszámítások” és „leszámítások” tulajdonképpen azt jelentik, hogy a tekintett tanuló +1-gyel, illetve −1-gyel hozzájárult a végs˝o képlethez. A fenti képlet tehát úgy jött létre, hogy minden egyes tanulóhoz egy +1-ekbo˝ l és −1-ekb˝ol álló összeget készítettünk el, és ezeket az összegeket még összeadtuk. De nézzük meg, hogyan is készítjük el ezeket az összegeket! Ha egy olyan tanulóról volt szó, akinek nincs fényképe semelyik együttesr o˝ l sem, akkor o˝ t a 40-be beszámítottuk, de máshova nem – tehát a hozzá elkészített összeg egyetlen +1-esbo˝ l áll. Nézzünk most egy olyan tanulót, akinek mondjuk k darab együttesro˝ l van fény˝ is beszámítottuk természetesen a képe (k itt 1, 2 vagy 3 lehet). Ot 40-be, ez a hozzá tartozó összegben egy +1-est jelent. De utána leszámítottuk éppen k-szor, tehát az összegben
k darab −1-es következik. Utána beszámítottuk újra éppen 2k -ször (persze csak
ha k = 2 vagy 3), ez jelent 2k darab +1-est. Végül (ha k = 3)
leszámítottuk ismét 3k -szor (ez persze 1, de így jobban fog látszani a dolog lényege). Számítsuk ki ezt az összeget!   1 Ha k = 1, akkor 1 − = 0; 1

50

2. Kombinatorika a számtanban

    2 2 Ha k = 2, akkor 1 − + = 0; 1 2       3 3 3 Ha k = 3, akkor 1 − + − = 0; 1 2 3 (hogy az ilyen típusú összeg értéke mindig 0, azt már az 5. feladatból tudjuk). Mivel az összeg 0 az olyan tanulókra, akiknek megvan valamelyik együttes fényképe, és 1 az olyanokra, akiknek nincs, ezért a 40 db összeg összege éppen azt adja meg, hány olyan tanuló van, akinek nincs fényképe egyik együttesro˝ l sem. Nézzük meg most, hogy az összegek összege, másként csoportosítva a tagokat, tényleg azt a képletet adja-e, amit elo˝ ször kaptunk. Ez nyilván így lesz: elo˝ ször is lesz 40 darab (+1)-es, aztán az Illés-fényképtulajdonosok révén 18 darab (−1)-es, az Omega-, ill. Metro-fényképtulajdonosok révén 16, ill. 12 darab (−1)-es. Továbbá az olyan tanulók révén, akiknek az Illés- és az Omega-együttes fényképe is megvolt, adódik 7 darab +1-es, ugyanígy 5, ill. 3 darab +1-est adnak az összegek összegéhez az Illés–Metro-, ill. Omega–Metro-fényképtulajdonosok. Végül az a két tanuló, akinek mind a három együttes fényképe megvolt, még egy-egy (−1)-essel járul hozzá az összegek összegéhez. Így ez valóban: 40 − (18 + 16 + 12) + (7 + 5 + 3) − 2. Ezt a formulát – és a hasonló, csak más, és esetleg több számadatból létrejöv˝o formulákat – szitaformulának nevezik, mivel úgy számolunk össze bizonyos tárgyakat, hogy a többi, bennünket nem érdekl˝o tárgyat „kiszitáljuk”. 11. feladat Egy fiúosztályban 18 fiú szeret sakkozni, 23 futballozni, 21 kerékpározni és 17 kirándulni. Azok száma, akik sakkozni és futballozni szeretnek, 9. Sakkozni és kerékpározni 7-en, sakkozni és kirándulni 6-an, futballozni és kerékpározni 12-en, futballozni és kirándulni 9-en, végül kerékpározni és kirándulni 12-en szeretnek. 4 olyan fiú van, aki sakkozni, futballozni és ke-

2. Kombinatorika a számtanban

51

rékpározni is szeret, 3 olyan, aki szeret sakkozni, futballozni és kirándulni is. 5-en szeretnek sakkozni, kerékpározni és kirándulni, és 7-en szeretnek futballozni, kerékpározni és kirándulni. Olyan fiú, aki sakkozni, futballozni, kerékpározni és kirándulni egyaránt szeret, 3 van. Tudjuk azt is, hogy mindenki szeret sakkozni, futballozni, kerékpározni vagy kirándulni. Hány fiú van az osztályban? 8. A fentebbi módszer egy fontos alkalmazásaként oldjuk meg a következ˝o problémát: Hány olyan szám van 1200-ig, amely relatív prím 1200-hoz? Mivel 1200 = 24 · 3 · 52 , azoknak a számoknak van közös osztójuk 1200-zal, melyek a 2, 3, 5 közül legalább az egyikkel oszthatók. Mi tehát arra vagyunk kíváncsiak: hány olyan szám van, mely 1200-nál kisebb, és a 2, 3, 5 számok egyikével sem osztható. Könnyen kiszámíthatjuk, hogy 1200-ig van 1200 2 1200 3 1200 5

darab 2-vel osztható szám (minden második szám páros), darab 3-mal osztható szám, darab 5-tel osztható szám.

Azok a számok, melyek 2-vel és 3-mal oszthatók, nem mások, mint a 6-tal osztható számok. Ezért 1200-ig van 1200 6 1200 10 1200 15

darab 2-vel és 3-mal osztható szám, és hasonlóan darab 2-vel és 5-tel osztható szám, darab 3-mal és 5-tel osztható szám.

Végül a 2, 3, 5 mindegyikével éppen a 30-cal osztható számok oszthatók, így 1200-ig van 1200 30

darab, a 2, 3, 5 mindegyikével osztható szám.

Ha most ezekkel az adatokkal a szitaformula segítségével kiszámítjuk a keresett számot, az eredmény: 1200 1200 1200 1200 − − + + 2 3 5 2·3 1200 1200 1200 + + − = 320. 2·5 3·5 2·3·5

1200 −

52

2. Kombinatorika a számtanban

Ha az el˝obbi egyenl˝oség bal oldalán álló kifejezésb˝ol kiemeljük az 1200-at, a megmaradó rész szorzattá bontható (számoljatok utána!):   1 1 1 1 1 1 1 1200 · 1 − − − + + + − = 2 3 5 2·3 2·5 3·5 2·3·5       1 1 1 = 1200 · 1 − · 1− · 1− . 2 3 5 Legyen n egy természetes szám. Jelöljük ϕ(n)-nel1 az n-nél nem nagyobb, hozzá relatív prímszámok számát (annak, hogy itt a „kisebb” helyett a „nem nagyobb” szerepel, csak akkor van jelent˝osége, ha n = 1; maga az n szám csak ekkor lehet relatív prím saját magához. Így ϕ(1) = 1). Ez a ϕ(n) szám általában is hasonlóan számítható ki; erre vonatkozik az alábbi feladatok közül az els˝o. 12. feladat Legyenek az n természetes szám összes különböz˝o törzstényez˝oi: p1 , p2 , . . . , pk . Bizonyítsátok be, hogy ekkor:       1 1 1 ϕ(n) = n · 1 − · 1− ··· 1 − . p1 p2 pk 13. feladat Egy n természetes szám minden egyes d osztójához kiszámítjuk ϕ(d)-t, és összeadjuk a kapott számokat. Mi lesz az eredmény? 14. feladat Összeadjuk az összes n-nél kisebb, hozzá relatív prímszámokat. Mit kapunk? 9. Egy n fokú lépcs˝on akar valaki felmenni. Mindig vagy egy, vagy két fokot lép. Hányféleképpen mehet fel a lépcso˝ n? Ha n = 1, akkor nyilván csak egyféleképpen mehet föl. Ha n = 2, akkor már két lehet˝osége van: vagy kétszer lép egyet, vagy 1

A ϕ bet˝u (olvasd: fi) az f bet˝u görög megfelelo˝ je.

2. Kombinatorika a számtanban

53

egyszerre kett˝ot. Három lépcs˝ofok esetén három lehet˝osége van: háromszor egyet lép, vagy el˝oször kett˝ot, aztán egyet, vagy el˝oször egyet, aztán kett˝ot. Most tippeljen mindenki, hogy hányféleképpen lehet felmenni egy n fokú lépcso˝ n! Aki azt tippelte, hogy n-féleképpen, az nem találta el a helyes választ! Már n = 4 esetén is ötféleképpen lehet felmenni: vagy négy egyes, vagy két kettes lépéssel, vagy pedig úgy, hogy egyszer kett˝ot, kétszer pedig egyet lépünk, de ezt az utolsó esetet háromféleképpen lehet megvalósítani: vagy elo˝ ször lépünk két egyest, azután egy kettest, vagy elo˝ ször lépünk egy kettest, utána két egyest, vagy pedig egy egyest, majd egy kettest, végül ismét egy egyest lépünk. Nevezzük azt a számot, ami megmutatja, hogy hányféleképpen lehet felmenni ily módon az n fokú lépcso˝ n, Fn -nek! Fn -et szeretnénk meghatározni. Osszuk az n lépcso˝ n való megengedett felmenéseket két csoportba! Az egyik csoportba tartozzanak azok a felmenések, ahol utoljára egyest lépünk, a másik csoportba pedig azok a felmenések, ahol utoljára kettest lépünk. Nyilvánvalóan Fn annyi, mint a két csoport elemszáma együttvéve. Hány elem van az els˝o csoportban? Annyi, ahányféleképpen fel tudunk menni (mindig egyest vagy kettest lépve) az n − 1-edik lépcso˝ fokra, majd onnan egy egyest lépve az n-edik lépcso˝ fokra, azaz annyi, ahányféleképpen fel tudunk menni (mindig egyest vagy kettest lépve) az n − 1-edik lépcso˝ fokra, azaz Fn−1 . Hasonlóan láthatjuk be, hogy a második csoportban Fn−2 lehetséges felmenés van. Összesen tehát Fn−1 + Fn−2-féleképpen lehet felmenni, mindig egyest vagy kettest lépve, az n-edik lépcso˝ fokra. Ezt kaptuk tehát: Fn = Fn−1 + Fn−2. Ha már tudjuk, hogy F1 = 1 és F2 = 2, akkor ennek a képletnek a segítségével egymás után meghatározhatjuk az Fn számokat: F3 = F2 + F1 = 2 + 1 = 3, F4 = F3 + F2 = 3 + 2 = 5, F5 = F4 + F3 = 5 + 3 = 8 és így tovább. Készítsetek ti magatok táblázatot Fn értékeir˝ol kis n természetes számok esetén! Megállapodunk még abban, hogy legyen F0 = 1 (azzal az indokolással,

54

2. Kombinatorika a számtanban

hogy 0 fokú lépcs˝on egyféleképpen lehet „felmenni”: úgy, hogy egyáltalában nem lépünk). Az így definiált Fn számokat Fibonacci-féle számoknak nevezzük. Nevüket Fibonacci (ejtsd: fibonáccsi) középkori olasz matematikusról kapták, aki el˝oször vizsgálta o˝ ket. A Fibonacci-számokra sok érdekes összefüggés teljesül. Például igaz ez: F2n+1 = F0 + F2 + F4 + · · · + F2n. Ezt teljes indukcióval láthatjuk be. n = 0 esetén teljesül: F1 = F0 . Tegyük fel, hogy már tudjuk, hogy egy n-re teljesül, és be akarjuk látni, hogy akkor (n+1)-re is teljesül, azaz, hogy F2n+3 = F0 + F2 + · · · + F2n + F2n+2. De az indukciós feltevés szerint F0 + F2 + · · · + F2n + F2n+2 = (F0 + F2 + · · · + F2n) + F2n+2 = F2n+1 + F2n+2. Másrészt a Fibonacci-számok definíciója szerint F2n+1 + F2n+2 = F2n+3, és ezzel a kívánt állítást bebizonyítottuk. 15. feladat Fn+2 − 1 = F0 + F1 + · · · + Fn .

16. feladat 1 − F2n = F0 − F1 + F2 − F3 ± · · · + F2n − F2n+1. 17. feladat Fn · Fn+1 = F02 + F12 + · · · + Fn2 . 18∗. feladat Bizonyítsátok be, hogy  √ !n+1 1  1+ 5 − Fn = √ 2 5

 √ !n+1  1− 5 .  2

(Megjegyzés: A fenti képletet Fn -re könny˝u igazolni teljes indukcióval – ha már valahonnan megsejtettük, hogy a Fibonacciszámok így fejezhet˝ok ki. De magára a képletre rájönni, azt megsejteni sokkal nehezebb.) 19. feladat Egy vadász mindennap annyi vadat l˝o, mint a megel˝oz˝o két napon együttvéve. Az els˝o nap 10, a második nap 9 vadat l˝ott. Hány vadat l˝ott az n-edik napon? 20. feladat Írjuk le a Pascal-háromszöget úgy, hogy a sorkezd˝o egyeseket egymás alá írjuk (4. ábra)! Összeadjuk a vastagon behúzott egyenesekre es˝o számokat. Milyen számokat kapunk eredményül? Miért?

2. Kombinatorika a számtanban

1 1 1 1 1 1 1

55

1 2 1 3 3 1 4 6 4 1 5 10 10 5 1 6 15 20 15 6 1 4. ábra.

21. feladat Bontsuk fel a sakktáblát az 5.a ábrán látható módon négy részre, és rakjuk össze a részekb˝ol az 5.b ábrán látható téglalapot! Egy 64 cm2 terület˝u négyzetb˝ol egy 65 cm2 terület˝u téglalapot készítettünk átdarabolással! Hol a hiba? Próbáljuk meg ugyanezt az 5-ször 5-ös sakktáblával is elvégezni! Milyen kapcsolata van mindennek a Fibonacci-számokkal?

b)

5. ábra. a)

3 Kombinatorika a mértanban

Lehet, hogy els˝o pillanatra meglep˝odtök: mi köze a kombinatorikának a geometriához? Pedig ez a fejezet hosszabb, mint az el˝oz˝o! Nemcsak a geometria vet fel sok olyan kérdést, melyhez kombinatorikai ismereteinket fel tudjuk, és fel is kell használnunk, hanem igen sokszor fordítva: kombinatorikai feladatokat, problémákat geometriailag ábrázolva oldunk meg. 1. Kezdjük mindjárt egy olyan feladattal, mely egy híres vetélked˝o, a TV „Ki miben tudós” versenyének dönto˝ jében szerepelt 1966-ban: Vegyünk egy konvex n-szöget, és tegyük fel, hogy semelyik három átlója nem megy át egy ponton. Hány metszéspontja van az átlóinak? (A csúcsokat nem számítjuk metszéspontnak, és persze az átlóegyeneseknek a sokszögön kívüli metszéspontjait sem. Tehát az 1. ábrán a befeketített pont metszéspont, de a bekarikázott pontok nem.) Els˝o pillantásra úgy fognánk neki a feladatnak, hogy megszámoljuk egy-egy átlón a metszéspontokat, és ezeket összegezzük. El˝oször végezzük el az összeszámlálást, mondjuk egy hatszög esetén (2. ábra).

58

3. Kombinatorika a mértanban

1. ábra.

ACEF A

F

E B

D

ABCD C ACDE 2. ábra.

Vegyünk el˝oször egy olyan átlót, mely két másodszomszédos csúcsot köt össze, mondjuk A-t és C-t. Ezt az átlót a B-bo˝ l kiinduló átlók metszik, vagyis három metszéspont van rajta. Ilyen átló hat darab van, tehát összesen 6·3 = 18 metszéspontot vettünk ezzel számba. Most vegyünk egy átellenes csúcsokat összeköto˝ átlót, mondjuk AD-t. Ezen, mint az ábráról könnyen leolvashatjuk, négy met-

3. Kombinatorika a mértanban

59

széspont van. Ilyen átló három van, tehát ezekbo˝ l kapunk 3 · 4 további metszéspontot. Igaz-e tehát az, hogy az összes metszéspontok száma 18 + 12 = 30? Vigyázzunk! Az AC és BD átlók metszéspontját például akkor is számoltuk, amikor az AC átlón fekv o˝ metszéspontokat vettük számba, de akkor is, amikor a BD átlón fekv˝oket; és ugyanígy van ez a többi metszésponttal is: mindegyiket kétszer is számoltuk. Tehát az eredményt még el kell osztani kett˝ovel, és így 15 metszéspontot kapunk. Látható, hogy már ilyen kis n esetén is milyen sokat kellett számolnunk, el lehet képzelni, meddig tart ez az általános esetben (bár a számolás elvégezhet˝o; próbáljátok meg)! Ha ügyesebbek vagyunk, és kombinatorikai ismereteinkre támaszkodunk, sokkal rövidebben is célhoz érünk. Jelöljünk egy metszéspontot úgy, hogy odaírjuk a rajta áthaladó átlók végpontjait; tehát ABCD-vel az AC és BD átlók metszéspontját, és ACDE-vel az AD és CE átlókét, és így tovább. Jó-e ez a jelölés, vagyis nem jelöltünk-e különbözo˝ pontokat ugyanúgy? Jó, hiszen az A, B, C, D bet˝uket például csak az ABCD konvex négyszög átlóinak, vagyis az AC és BD átlóknak a metszéspontjához írtuk. Ennél többet is megfigyelhetünk: bármelyik négy csúcsot fel kellett használnunk az átlómetszéspontok megjelölésére; az ACEF négyes pl. az AE és CF átlók metszéspontját jelöli (2. ábra). Ha mármost fel akarjuk sorolni az összes átlómetszéspontot, nem kell mást tennünk, mint felírni az összes csúcsnégyeseket; az átlómetszéspontok száma tehát nem más, mint a csúcspontok halmazából kiválasztható
négyelem˝u részhalmazok száma, vagyis: Ha n = 6, akkor ez 64 , amit kicsit gyorsabban tudunk kiszámí
tani, ha felhasználjuk, hogy egyenlo˝ 62 -vel:   6 6·5 = 15. = 2·1 2

1. feladat Hány átlója van egy konvex n-szögnek?

60

3. Kombinatorika a mértanban

14

,1

cm

2. Ugyanezen a Ki miben tudós versenyen szerepelt egy másik érdekes feladat; ennek megoldása során egy másik régebbi ismer˝osünkkel, a skatulyaelvvel fogunk találkozni. Egy 70 cm oldalú négyzet alakú céltáblára leadunk 50 lövést: „elég jól” lövünk, mert minden lövésünk eltalálja a céltáblát. Bizonyítsuk be, hogy van két lövés, mely egymáshoz 15 cm-nél közelebb csapódott be1 . Megoldás: Tegyük fel, hogy céltáblának egy rossz sakktáblát használunk, melyr˝ol egy széls˝o sor és egy széls˝o oszlop letörött; így a sakktáblán csak 49 mezo˝ maradt. A sakktáblát összesen 50 lövés érte, tehát valamelyik mezo˝ re legalább kett˝o kellett hogy essen (itt alkalmazható a skatulyaelv!). Azt állítjuk, hogy ez lesz az a kett˝o, amelyik 15 cm-nél közelebb van egymáshoz. Rajzoljuk le külön ezt a négyzetet! (3. ábra.) Az oldala nyilván 10 cm, átlója pedig megközelít˝oleg 14,1 cm. Nem lehet ennél nagyobb távolságra a két lövedék sem. (De ezt bizonyítsátok be ti magatok!) Végeredményben többet is kaptunk valamivel, tudniillik, hogy nemcsak 15 cm-nél, hanem 14,2 cm-nél is közelebb van egymáshoz két lövedék.

10 cm 3. ábra.

1

Kicsit módosítottuk a számadatokat.

10 cm

3. Kombinatorika a mértanban

61

2. feladat Általánosítsátok a fenti feladat feltételeit! 3. Régi ismer˝osünk a teljes indukció is; ezt is igen sokszor használjuk a geometriában. Mindjárt egy példa erre: Rajzoljunk köröket (n számút) a síkra, és a kapott síkrészeket színezzük ki két színnel úgy, hogy két síkrészt különböz o˝ szín˝ure festünk, ha van közös határívük (ha csak közös határpontjuk van, akkor lehetnek azonos szín˝uek; a 4. ábrán egy ilyen színezést láthatunk három kör esetére). Azt kell bebizonyítani, hogy ilyen színezés mindig elvégezheto˝ ; ez nem nyilvánvaló, mert ha egy tartományt mondjuk kékre festünk, a vele szomszédosakat pirosra kell festenünk, ezek szomszédait pedig kékre, és például nem tudjuk (most még), hogy az utóbbiak között nincsen-e két szomszédos. Lássuk tehát a bizonyítást! Teljes indukciót fogunk használni. n = 1 kör esetére az állítás nyilvánvaló: a kör belsejét az egyik színnel, a körön kívüli részt a másik színnel színezzük ki. Meg kell még néznünk, hogy öröklo˝ dik-e a színezhet˝oség n-r˝ol (n + 1)-re. Vegyünk tehát n+1 kört, de egyelo˝ re csak n darabot rajzoljunk fel közülük, és az ekkor kapott részeket színezzük ki „jól”,

kék piros 4. ábra.

62

3. Kombinatorika a mértanban

5. ábra.

azaz úgy, hogy a szomszédosak különbözo˝ szín˝uek legyenek. Hogy ezt megtehetjük, az éppen az indukciós feltevés. Rajzoljuk most be az utolsó, (n + 1)-edik kört, és módosítsuk a színezést a következ˝oképpen: a körön kívül a színezés maradjon változatlan, a belsejében lev˝o síkrészek színét viszont változtassuk az ellenkez˝ojére (5. ábra). Nézzük meg most, hogy a kapott színezés tényleg eleget tesze kívánságainknak, vagyis, hogy a határívek két oldalán ellenkez˝o szín˝u tartományok állnak-e. A régi határívekre ez igaz, mert vagy mindkét rész színe marad, vagy mindketto˝ nek a színe megváltozott, így mindenképpen különbözo˝ ek maradtak. Az új határíveken pedig biztosan különbözo˝ , hiszen ezeket éppen az ellenkez˝ojére változtattuk. Tehát a „kétszín˝uség” öröklo˝ dik n-r˝ol (n + 1)-re. A fentiekkel ugyan befejeztük a bizonyítást, de érdemes még egy kicsit elid˝ozni ennél a problémánál. Fölrajzol nekünk valaki egy ilyen körrendszert, rámutat az egyik síkrészre, és megkérdezi, hogy milyen színnel kell ezt kiszínezni. Ez persze attól függ, hogy milyen színnel kezdjük a színezést. Rendben van – feleli o˝ –, a legküls˝o síkrészt fessük kékre. Ekkor már tudunk válaszolni a kérdésére: a legküls˝ovel szomszédos részeket pirosra festjük, ezek szomszédait kékre és így tovább. Elo˝ bb-utóbb eljutunk a kérdezett részhez; de nem lehetne-e ennek a színét egyszer˝ubben

3. Kombinatorika a mértanban

63

kék piros

6. ábra. is megmondani? Kövessük nyomon a tekintett rész színét, miközben egyenként hozzávesszük a köröket. Amíg egy kör sincs, addig az egész sík kék. Amikor egy-egy kört hozzáveszünk, akkor egy bizonyos síkrész színe marad, ha a körön kívül van, és megváltozik, ha a kör belsejében. Végeredményben a síkrész színe annyiszor változik, ahány körnek a belsejében van. Így a végs o˝ színe: piros, ha páratlan sok körnek van a belsejében, és kék, ha páros sok körnek van a belsejében (6. ábra). Észrevehetjük, hogy ebb˝ol kiindulva, újabb bizonyítást adhatunk az eredeti feladatra. Fessünk ugyanis egy részt aszerint pirosra vagy kékre, hogy páratlan vagy páros sok kör belsejében van benne. Azt, hogy az így kapott színezés „jó”, bizonyítsátok be ti magatok. 3. feladat Bizonyítsuk be, hogy ha egyeneseket húzunk a síkban, a keletkez˝o részek két színnel kiszínezhet˝oek!

64

3. Kombinatorika a mértanban

4. feladat Hogyan lehetne egy síkrész színét egyenesek esetén is megmondani az összes rész kiszínezése nélkül?

4. Kérdés persze, hogy mikor van szükség arra, hogy síkrészeket színezgessünk. Nos, éppen ez a feladat merül fel például a térképészetben: Ha az el˝oz˝o feladatban szerepl˝o síkrészeket egy képzeletbeli térkép országainak tekintjük, a térképet az áttekinthet˝oség érdekében úgy kell kiszínezni, hogy a szomszédos országok különböz˝o szín˝uek legyenek. Az elo˝ bb tehát éppen azt láttuk, hogy ilyen színezés készítheto˝ , ha a térkép olyan speciális alakú, mint a mienk. Ha el˝oveszünk egy térképet, az persze jóval bonyolultabb alakú lesz, és a kiszínezéséhez is több színre lesz szükség. Igen egyszer˝u például négy országot rajzolni úgy, hogy bármelyik érintkezzék bármelyikkel egy szakasz mentén, tehát ha ezt „jól” ki akarjuk színezni (vagyis úgy, hogy a szomszédos országok különböz˝oek legyenek), akkor mind a négy országot különböz˝o szín˝ure kell festenünk (7. ábra).

7. ábra. Nézzünk most egy „valódi” térképet, például Magyarország megyéinek térképét. Az iskolai térképeken hat színt használnak a

3. Kombinatorika a mértanban

65

piros kék sárga zöld 8. ábra. kiszínezéséhez, bár négy szín is elegendo˝ volna, mint az a 8. ábrán látható2 . Persze meg lehet kérdezni, hogy három szín nem volna-e elegend˝o; de könnyen beláthatjuk, hogy nem. Kezdjük el ugyanis pirossal, kékkel és sárgával színezni a térképet (mindegy, hogy milyen három színt mondunk), azt kell belátni, hogy elo˝ bb-utóbb elakadunk. Kezdjük a színezést Jász-Nagykun-Szolnok megyénél, mondjuk piros színnel. Ekkor a Szolnok megyével szomszédos megyék csak kék és sárga szín˝uek lehetnek. Pest megye legyen, mondjuk, kék. Ekkor Hevest már sárgára festhetjük csak, Borsod-Abaúj-Zemplént kékre, Hajdú-Bihart sárgára, Békést kékre, Csongrádot sárgára, és megakadtunk, mert BácsKiskun megyének már van piros (Szolnok), kék (Pest) és sárga (Csongrád) szomszédja, tehát nem festhetjük ezen színek egyikére sem (8. ábra). Nem véletlen, hogy két különbözo˝ térkép esetében is négy szín kellett; és volt elég a színezéshez. Amilyen térképet eddig rajzoltak, mindegyikhez elég volt négy szín; ezért a matematikusok 2 A térképészek azért használnak több színt a kelleténél, hogy a térkép áttekinthet˝obb legyen.

66

3. Kombinatorika a mértanban

már több mint száz éve nagyon valószín˝unek tartják (szakkifejezéssel: sejtik), hogy négy szín minden térképhez elegendo˝ ; tehát a jöv˝oben készítend˝o térképekhez is, s˝ot azokhoz is, amiket fel se lehetne rajzolni, annyi országot ábrázolnak. Azt, hogy öt szín mindig elegendo˝ , sikerült bebizonyítani3, de hogy négy szín is elég lenne, azt nem. Ez a híres négyszínsejtés (egyesek annyira hisznek benne, hogy egyenesen négyszíntételnek hívják), melynek bizonyításával matematikusok hosszú sora próbálkozott – hiába. Illetve nem egészen hiába, mert megoldásához segédeszközök egész sorát dolgozták ki, melyek más területeken igen sok alkalmazásra találtak. E segédeszközök közül a legfontosabbakkal, a gráfokkal hamarosan megismerkedünk; a négyszínsejtés megoldására tett kísérleteket persze nem tudjuk itt ismertetni veletek, mert azok köteteket tesznek ki. 5. feladat Bizonyítsuk be, hogy egy olyan térkép, amelynek minden csúcspontjában4 páros számú ország találkozik, két színnel kiszínezhet˝o. – Ha nem sikerül a bizonyítás, olvassátok el a következ˝o három pontot és próbálkozzatok újra! 5. Nézzünk most egy olyan feladatot, amelynek elso˝ pillantásra semmi köze nincs a geometriához: Bizonyítsuk be, hogy egy 51 tagú társaságban biztosan van olyan ember, akinek páros számú ismer˝ose van. (Az ismeretség ilyenkor mindig kölcsönös ismeretséget jelent. Lehetnek a társaságban olyanok is, akik nem ismerik egymást, so˝ t akár olyan is, aki senkit sem ismer.) A feladat azért nehéz, mert újszer˝u. Ilyenkor általában úgy próbálunk tájékozódni, hogy konkrét eseteket nézünk. Ez azonban most igen nehéz, mert mindjárt felmerül, hogyan is adjunk meg egy 51 tagú társaságot? Adjunk nevet mindenkinek, és utána soroljuk fel, hogy kik ismerik egymást. Ez már önmagában is 3 A bizonyítást elolvashatjátok Rademacher–Toeplitz: Számokról és alakzatokról cím˝u könyvében. 4

zik.

Azokat a pontokat hívjuk csúcspontoknak, ahol ketto˝ nél több ország találko-

3. Kombinatorika a mértanban

67

reménytelenül hosszadalmas, és ekkor még meg kell számolni, hogy kinek hány ismer˝ose van. . . Ha kisebb társaságról lenne szó, akkor jobb lenne a helyzet; de vajon milyen számot mondhatunk az 51 helyett, hogy egyáltalán igaz maradjon az állítás? 50-et biztosan nem, mert ha pl. mind az ötven ismeri egymást, akkor mindenkinek 49 ismer˝ose van, vagyis páratlan sok számú. De ugyanezért nem helyettesíthetjük az 51-et 48-cal vagy 30-cal, s˝ot általában semmilyen páros számmal. De hátha a páratlan számokkal már helyettesíthetjük az 51-et? Próbáljuk meg bebizonyítani, hogy páratlan számú emberb˝ol álló társaságban mindig van olyan ember, akinek páros számú ismer˝ose van a társaságban. Most már megnézhetünk egy adott társaságot. Legyenek a tagjai mondjuk: Arisztid, Edömér, Szvetozár, Tasziló és Ubul. Edömér mindenkit ismer, Arisztid és Tasziló ismerik egymást, és Tasziló ismeri Ubult is. Ekkor: Arisztid Edömér Szvetozár Tasziló Ubul

2 másikat ismer, 4 másikat ismer, 1 másikat ismer, 3 másikat ismer, 2 másikat ismer.

Végeredményben háromnak (Arisztidnek, Ubulnak és Edömérnek) van páros számú ismero˝ se; erre a társaságra tehát igaz, amit állítottunk. Még mindig nagyon hosszadalmas egy konkrét eset átnézése, és egyáltalán nem áttekinthet˝o. Ezen azonban tudunk segíteni, ha ügyesen ábrát készítünk. Igen kézenfekvo˝ a társaság tagjait pontokkal ábrázolni, és két pontot összekötni egy szakasszal, ha a két ember ismeri egymást. Ekkor a 9. ábrát kapjuk. Az ilyen ábrát gráfnak nevezik. Egy gráfot tehát úgy kapunk, hogy lerajzolunk néhány pontot, és ezek közül bizonyos párokat (nem szükségképpen mindet) összekötünk egy-egy szakasszal. Az eredetileg lerajzolt pontokat nevezik a gráf csúcsainak vagy pontjainak vagy szögpontjainak, az összeköt˝o szakaszokat a gráf éleinek. Ha grá-

68

3. Kombinatorika a mértanban

A(-risztid)

E(-dömér) U(-bul)

T(-asziló)

S(-zvetozár)

9. ábra. fot rajzoltok, nem kell az éleket vonalzóval húznotok, nem kell azzal tör˝odnötök, hogy ezek egyenesek legyenek. Csak az a fontos, hogy két csúcs össze van-e kötve vagy sem. A társaságot tehát gráffal ábrázolhatjuk kényelmesen. Szerepel még a feladatunkban az, hogy hány ismero˝ se van valakinek. Ezt a gráfról úgy olvashatjuk le, hogy megszámoljuk, hány él indul ki a csúcsból. Ezt a számot a pont fokának nevezzük. Így A foka 2 (A másodfokú), E foka 4 (E negyedfokú), S foka 1 (S els˝ofokú), T foka 3, U foka 2. Ha most megérkezik Hümér, aki senkit sem ismer a társaságból, akkor az ábrán egy újabb H pontot kell hozzávennünk a gráfhoz, melyet azonban egyik régivel sem kötünk össze. H foka tehát 0 lesz. Feladatunkat a gráfelmélet nyelvén tehát így fogalmazhatjuk meg: Egy páratlan sok csúcsú gráfban van páros fokú pont. Gráfokat könnyen tudunk rajzolni, így most már semmi akadálya, hogy konkrét példákat vizsgáljunk meg. A 10. ábrán felrajzoltunk több konkrét gráfot és tapasztalatainkat táblázatba foglaltuk: gráf

a)

b)

c)

d)

e)

páros fokú pontok száma

1

5

3

3

7

69

3. Kombinatorika a mértanban

a)

b)

d)

c)

e)

10. ábra. Észrevehetjük: nemcsak hogy van páros fokú pont, de mindig páratlan sok van. Próbálkozzunk meg tehát annak bizonyításával, hogy: Páratlan sok csúcsú gráfban a páros fokú pontok száma páratlan. Miel˝ott azonban ebbe belekezdenénk, nézzünk meg néhány olyan gráfot is, amelynek páros számú csúcsa van; bizonyosan ezekr˝ol is kiderül valami érdekes (11. ábra). Készítsünk táblázatot!

a)

gráf

a)

b)

c)

d)

e)

páros fokú pontok száma

2

0

4

2

6

b)

c)

11. ábra.

d)

e)

70

3. Kombinatorika a mértanban

Itt most azt figyelhetjük meg, hogy: Páros sok csúcsú gráfban a páros fokú pontok száma páros. Látjuk, hogy ebben az esetben elo˝ fordulhat, hogy egyáltalán nincs páros fokú csúcs. A páros fokú csúcsok száma ilyenkor is páros, mert a 0 páros szám. Mást mutatnak a példák akkor, ha páratlan, és mást, ha páros számú csúcsa van a gráfnak. Helyesebben: mást mutatnak, ha a páros fokú csúcsok számát nézzük. És ha a páratlan fokú csúcsok számát néznénk? Ezt úgy kapjuk, hogy az összes csúcsok számából kivonjuk a páros fokúak számát. De akár páratlan számból vonunk ki páratlan számot, akár párosból párosat, az eredmény mindig páros szám lesz. Vagyis a páratlan fokú csúcsokra ezt kapjuk: Tétel Minden gráfban páros sok páratlan fokú pont van. Persze csak akkor mondhatjuk a fenti állítást tételnek, ha be is bizonyítjuk. Több konkrét esetben láttuk ugyan, hogy igaz, de ti is tudjátok, hogy ez még nem bizonyítás. Érdekes, hogy eddig mindig csak nehezítettük a feladatot, egyre többet mondó állításokkal helyettesítettük az eredetit, mégis a legutóbbi formát lesz a legkönnyebb igazolni. El˝oz˝o problémánknál, a színezésnél úgy jártunk el, hogy az ábrát fokozatosan építettük fel, egyenként húztuk be a köröket. Megállapítottuk, hogy a bizonyítandó tulajdonság minden egyes újabb kör behúzásakor öröklo˝ dik. Járjunk el most is hasonlóan, az éleket egyenként rajzolva be. Kiinduláskor minden pont foka 0, tehát a páratlan fokú pontok száma nulla, vagyis páros szám. Nézzük meg, hogy ha már valameddig eljutottunk, egy újabb él behúzása mennyivel változtatja meg a páratlan fokú pontok számát. Ez nyilván attól függ, hogy milyen fokú pontokat köt össze. Ha behúzása el˝ott mindkét pont foka páros volt, akkor behúzása után mindkett˝o páratlan fokú lett, tehát a páratlan fokú pontok száma 2-vel n˝ott. Ha mindkett˝o páratlan volt, akkor páros fokúak lettek, így a páratlan fokú pontok száma ketto˝ vel csökkent. Végül, ha egyikük páros fokú, a másik páratlan fokú volt, akkor

3. Kombinatorika a mértanban

71

A

U

E

S

T

12. ábra. fokuk páratlanra, illetve párosra változott, tehát a páratlan fokú pontok száma ekkor változatlan maradt. Összefoglalva, az új él behúzása a páratlan fokú pontok számát 2-vel növeli vagy csökkenti, vagy változatlanul hagyja. Tehát ha az él behúzása el o˝ tt páros sok páratlan fokú pont volt, akkor utána is páros sok maradt. Ezzel a bizonyítást be is fejeztük. (Tulajdonképpen teljes indukciót használtunk; gondoljátok meg, miért! Az egyes pontok fokának változását az élek behúzgálása során, elso˝ gráfunk esetében a 12. ábrán követhetitek nyomon; a páratlan fokú pontokat bekarikáztuk, és az utoljára behúzott élt mindig megvastagítottuk.) 6. feladat Fogalmazzátok át gráfokra, és bizonyítsátok be az alábbi állítást: Minden társaságban van két ember, akinek ugyanolyan sok ismer˝ose van a társaságban. 6. Az el˝oz˝o pontban bizonyított tételre érdemes egy másik bizonyítást is megnézni. Ez a bizonyítás úgy indul, hogy egy lát-

72

3. Kombinatorika a mértanban

szólag nem is idevágó kérdést teszünk fel: Hogyan lehet egy gráf éleit összeszámolni? Erre igen könny˝u válaszolni: vegyük sorra a szögpontokat, és számoljuk meg a belo˝ lük kiinduló éleket. Más szóval adjuk össze a fokszámokat. Csak arra kell még vigyázni, hogy így minden élt mindkét végpontjában beszámoltunk, tehát az eredményt el kell osztani kett˝ovel. Amit most kaptunk, az önmagában is érdekes, megérdemli, hogy külön tételként megfogalmazzuk. Tétel Egy gráfban a fokszámok összege kétszerese az élek számának. A tételb˝ol következik, hogy a fokszámok o˝ sszege páros, hiszen egy egész számnak (az élek számának) kétszerese. Ha ebb o˝ l az összegb˝ol elhagyjuk a páros tagokat, akkor is páros marad, tehát a páratlan fokszámok összege páros. De ez csak úgy lehet, ha páros sokan vannak. Így újra bebizonyítottuk az 5. pontban kimondott tételt. 7. Gráfokat nemcsak társaságok ábrázolásakor kaphatunk. Ugyanígy ábrázolhatunk velük más kapcsolatokat is, például azt, hogy melyik vállalat melyik másikkal áll kereskedelmi kapcsolatban. Van, amikor a gráf mindjárt lerajzolva jelenik meg: például úthálózatok, vasúthálózatok térképén, vagy egy rádió elektromos hálózatának rajzán (az egyes alkatrészeket, tranzisztorokat, ellenállásokat vehetjük pontoknak, az összeköto˝ huzalokat éleknek). S˝ot, az országokat vagy megyéket feltünteto˝ térképek is gráfok: csúcspontjaik azok a pontok, amelyekben három vagy annál több ország (vagy megye) találkozik, éleik az ezeket összeköto˝ határszakaszok.5 Ha egy gráfot lerajzolunk, akkor elo˝ fordulhat, hogy élei metszik egymást (az els˝o gráfunk esetében is ez történt). Ezt a met5 Tulajdonképpen ki kellene zárnunk bizonyos térképeket; nem szerepelhet olyan ország, mint San Marino, mely teljes egészében egy másik ország belsejében fekszik, de olyan sem, mint Mongólia, melynek csak két szomszédja van, hiszen ekkor két pontot két él kötne össze. Ez a nehézség elt˝unik azonban, ha az eredeti csúcsokon kívül még néhány, a határokon fekvo˝ pontot is csúcsnak tekintünk (ezek természetesen másodfokúak).

3. Kombinatorika a mértanban

73

A

U

E

T

S 13. ábra.

széspontot természetesen nem tekintjük csúcsnak. Legjobb úgy képzelni, hogy az egyik él ilyenkor a másik él fölött halad el (ha térbeli ábrát készítünk például drótokból, akkor ez a bonyodalom fel sem lép). Ábráinkon a „valódi" csúcsokat megkülönböztetésül befeketítjük. Visszatérve azonban az elso˝ gráfra, láthatjuk, hogy ügyesebb ábrával elkerülhetjük a keresztezo˝ dést (13. ábra). Ha a gráfot így, keresztez˝odés nélkül sikerül lerajzolni (mint tudjuk, nem kell egyenes éleket használnunk), akkor azt mondjuk, hogy a gráf síkba van rajzolva. Vannak olyan gráfok, melyeket le lehet rajzolni a síkba, de olyanok is, melyeket nem. Például a 14. ábra gráfjai, illetve a 15. ábra gráfja; arról, hogy az utóbbi

14. ábra.

74

3. Kombinatorika a mértanban

15. ábra. gráf nem rajzolható síkba, egyelo˝ re próbálgatással gy˝oz˝odjetek meg, de erre még visszatérünk. 8. Egy iskolabálon 300 tanuló vett részt. Persze ilyenkor nem ismer mindenki mindenkit. Mondjuk, hogy minden fiú pontosan 50 lányt és minden lány pontosan 50 fiút ismer. Azt állítjuk, hogy tudnak egyszerre úgy táncolni, hogy mindenki ismero˝ sével táncoljon. Társaságról és ismeretségekr˝ol lévén szó, elkészíthetjük az el˝oz˝oekhez hasonlóan a társaságot ábrázoló gráfot (legalábbis képzeletben). Észrevehetjük viszont, hogy az, hogy két fiú ismeri-e egymást, sehol sem játszik szerepet. Így a fiúk közötti ismeretségeket nem is kell a gráfon bejelölnünk. Ugyanígy a lányokat összeköt˝o éleket sem húzzuk be. Célszer˝u ábrázolásmód tehát az lesz, hogy fölülre rajzoljuk a lányoknak megfelelo˝ csúcsokat, alulra a fiúknak megfelel˝o csúcsokat, és csak fels˝o pontot alsóval összeköt˝o élt rajzolunk be, ha a megfelelo˝ tanulók ismerik egymást. Így egy speciális fajta, úgynevezett páros gráfot kapunk. Egy ilyen páros gráfot rajzoltunk fel a 16. ábrán (természetesen kisebb társaságnak megfelel˝ot). A megvastagított élek mutatják, hogy például kik táncolhatnak egyszerre egymással. Próbáljuk megfogalmazni a gráfok nyelvén feladatunkat! Van tehát egy páros gráfunk, melynek 300 szögpontja van. Minden pontjának a foka 50. Ennyit tudunk, és ezt kell bebizonyítanunk: be tudjuk úgy párokba osztani a pontokat, hogy az egy párba es o˝

3. Kombinatorika a mértanban

75

16. ábra. pontok össze legyenek kötve. Más szóval, ki tudunk úgy jelölni éleket, hogy minden pontban éppen egy végzo˝ djék közülük (ekkor egy-egy ilyen él végpontjai lesznek egy párba osztva). Egy ilyen élrendszert els˝ofokú faktornak szoktak nevezni. Várhatjuk, hogy a gráf pontjai számának nem lesz szerepe, és annak sem, hogy mekkora a pontok foka, csak annak, hogy minden pont ugyanolyan fokú. Végeredményben azt fogjuk bebizonyítani, hogy: Tétel Ha egy páros gráf minden pontjának ugyanannyi a foka, és legalább 1, akkor kiválasztható bel˝ole egy els˝ofokú faktor. Érdemes megfigyelni, hogy ha ehhez az elso˝ fokú faktorhoz tartozó éleket elhagyjuk, akkor megint egy olyan páros gráfot kapunk, melyben minden pont foka ugyanannyi (eggyel kevesebb, mint az el˝obb). Ha ez a fokszám nem 0, akkor a megmaradt gráfból – a fenti tétel szerint – megint kiválaszthatunk egy elso˝ fokú faktort és így tovább. Így végül is annyi elso˝ fokú faktort kapunk amennyi eredetileg a pontok foka volt. Színezzük ki az egyik faktorhoz tartozó éleket egy bizonyos színnel, a másik faktor éleit egy másik színnel, a harmadik elso˝ fokú faktor éleit egy harmadikkal és így tovább (17. ábra). Azt kapjuk, hogy: Tétel Ha egy páros gráfban minden pont foka ugyanaz a k szám, akkor az éleit k színnel ki tudjuk színezni úgy, hogy egy pontból sem indul ki két azonos szín˝u él (következésképpen minden pontból minden szín˝u él kiindul).

76

3. Kombinatorika a mértanban

17. ábra. Ez a tétel, azonkívül, hogy érdekes és komoly állítás, azért is érdekes számunkra, mert a gráfelmélet egyik kifejleszto˝ jét˝ol és legkiválóbb m˝uvel˝ojét˝ol, a magyar K˝onig Dénest˝ol származik. 7. feladat Bizonyítsuk be, hogy ha egy páros gráf minden pontjának ugyanaz a foka, akkor ugyanannyi pontja van „fent” , mint „lent”. 8. feladat Igaz lesz-e az el˝obbi két tétel, ha úgy változtatjuk meg, hogy „páros gráf” helyett csak „gráfot” írunk? Az el˝oször kimondott tétel bizonyításához a következo˝ pont végén térünk vissza. 9. Egy szigeten 6 indián törzs lakik, mindegyiknek 100 négyzetmérföld a vadászterülete. Elhatározzák, hogy eddigi totemállataik helyett ezentúl tekn˝osbékát fognak tisztelni. Mivel a szigeten mindenütt el˝ofordul tekn˝osbéka, összesen 6 faj, minden törzs a területén el˝oforduló fajok valamelyikét akarja totemnek választani, méghozzá úgy, hogy minden törzsnek különböz o˝ totemje legyen. Sikerül-e ez nekik, ha még azt is hozzátesszük, hogy az egyes tekn˝osbékafajok 100–100 négyzetmérföldnyi területen vannak elterjedve? (18. ábra.) Hogy a feltételeket világosabban lássuk, nézzük meg, miért kellett a legutolsó mondatot hozzátenni. Ha egy tekno˝ sbékafaj mondjuk 200 négyzetmérföldnyi területen fordulna elo˝ , akkor megtörténhetne, hogy két különbözo˝ indián törzs is csak ezt az

3. Kombinatorika a mértanban

1

77

UTA HO K

DELAVÁROK SZ

IÚ

K

4

IROKÉ

3

ZEK

5 2 K CSO APA

NA VA JÓ

6

K

indián határ teknõs határ

18. ábra. egy tekn˝osbékafajt találná a vadászterületén, ezért nem választhatnának különböz˝o totemet. Feltételeinkb˝ol az is kiderül, hogy a sziget 600 négyzetmérföld terület˝u. Az indiánok vadászterülete összesen 600 négyzetmérföld, és ezen kívüli területek nem lehetnek, mert a tekno˝ sbékák az egész szigetet benépesítik, és egy-egy faj csak 100 négyzetmérföldet foglal el. Próbáljuk meg feladatunkat alkalmas gráffal ábrázolni. Pontokkal jelöljük a tekn˝osfajokat és az indián törzseket. Bennünket az érdekel, hogy mely indián törzsek területén mely tekno˝ sfajok élnek, ezért összekötünk éllel egy tekno˝ spontot egy indiánponttal, ha a tekn˝osfaj el˝ofordul az illet˝o indián törzs vadászterületén. Ha a tekn˝osfajokat ábrázoltuk a fels˝o sorban, az indián törzseket az alsó sorban, akkor rögtön látszik, hogy egy páros gráfot ka-

78

3. Kombinatorika a mértanban

1

2

3

4

5

6

U

A

S

N

I

D

19. ábra.

punk. Mit is kellene bebizonyítanunk? Azt, hogy a gráfban van els˝ofokú faktor, mert ekkor minden indián törzsnek azt a tekno˝ sfajt kell választani, amellyel ebben az elso˝ fokú faktorban össze van kötve (19. ábra). Ismét ugyanahhoz a kérdéshez jutottunk; mikor van egy gráfban els˝ofokú faktor? Az el˝oz˝o pontban kimondott tétel szerint (melyet még nem bizonyítottunk be!) ehhez elég, ha az összes pont foka ugyanannyi. De ez túlságosan ero˝ s megszorítás. Az újabb feladatból kiindulva egy ennél jobb, vagyis kevesebbet követel˝o feltételt is találhatunk. Nézzük meg, milyen tulajdonságai vannak a kapott gráfnak. Minden alsó pontból indul ki él, mert a tekno˝ sbékák az egész szigetet benépesítik. Nem lehetséges az sem, hogy két indián törzs vadászterületén együttvéve is csak egy tekno˝ sbékafaj éljen. A gráfra nézve ez azt jelenti, hogy két alsó pont együttvéve legalább két fels˝o ponttal össze van kötve. De ugyanígy nézhetnénk 3, 4, 5 vagy 6 indián törzset is, mindig azt tapasztalhatnánk, hogy területükön legalább annyi tekn˝osfaj él, ahány törzset vettünk. Más szóval a gráfnak az alábbi tulajdonsága van: bárhogyan is véve ki néhány alsó pontot, ezek együttvéve legalább ugyanannyi fels˝o ponttal vannak összekötve.

3. Kombinatorika a mértanban

79

Ha most eltekintünk a feladatban szereplo˝ konkrét számoktól, akkor a következ˝o tételt kell bizonyítanunk (mely lényegében szintén K˝onig Dénest˝ol származik, és a gráfelmélet egyik legfontosabb tétele): Tétel Ha egy páros gráfban fönt és lent egyaránt a pont van, továbbá tetsz˝oleges számú alsó pont együttvéve legalább ugyanannyi fels˝o ponttal össze van kötve, akkor a gráfban van els˝ofokú faktor. Észrevehetjük, hogy ha egy páros gráfban van elso˝ fokú faktor, akkor a gráfot feje tetejére állítva is lesz benne. De mi történik a feltételünkkel, ha a gráfot feje tetejére állítjuk, vagyis az alsó pontokat tekintjük fels˝oknek, és megfordítva? Könny˝u látni, hogy a fölfordított gráfra ugyanez a feltétel teljesül. Ehhez be kell látnunk, hogy az eredeti gráfban fölül k darab pontot kiválasztva, legalább k olyan alsó pont van, amely össze van kötve ezek valamelyikével. Színezzük ki ugyanis ezeket az alsó pontokat pirossal, és a többit kékkel. A kék pontok együttvéve is legfeljebb n − k darab fels˝o ponttal lehetnek összekötve. Mivel „alulról felfelé” teljesül a feltétel, ezért a kék pontok száma legfeljebb n − k, s így a piros pontoké legalább k (20. ábra). Térjünk most rá a tétel bizonyítására!

kék

k

{

{

n-k

piros 20. ábra.

80

3. Kombinatorika a mértanban

Bizonyítás: A fent megfogalmazott tulajdonságra olyan sokszor kell hivatkozni, hogy legegyszer˝ubb, ha a bizonyítás során az ilyen gráfokat röviden „jó" gráfoknak nevezzük. Van tehát egy „jó” gráfunk, és be akarjuk bizonyítani, hogy van elso˝ fokú faktora. Ha egy kétpontú – tehát egy alsó és egy felso˝ pontból álló – gráf „jó”, ez éppen annyit jelent, hogy a két pontja össze van kötve. Így egy els˝ofokú faktor azt jelenti, hogy gráfunkat szét lehet darabolni „jó” kétpontú gráfokra; a szétdarabolás annyit jelent, hogy úgy osztjuk szét a pontokat, hogy csak az ugyanoda kerül˝o pontok közötti éleket tartjuk meg. Úgy fogunk mármost eljárni, hogy a gráfot két „jó” részre vágjuk, majd ezeket a részeket ismét, „jó” részekre bontjuk, és ezt az eljárást addig folytatjuk, amíg el nem jutunk csupa kétpontú „jó” gráfhoz, ekkor a megmaradt élek adják éppen a keresett elso˝ fokú faktort. De meg tudjuk-e ezt csinálni? Az igenlo˝ válaszhoz csak azt kell bebizonyítanunk, hogy: ha egy páros gráf „jó”, és több, mint két pontja van, akkor szétvágható két „jó” gráfra. Próbálkozzunk el˝oször egy igen egyszer˝u szétvágással: veszünk egy fels˝o A pontot és egy alsó B pontot, melyek össze vannak kötve, ez lesz az egyik gráf, a többi pont és a köztük men o˝ élek a másik. Az els˝o gráffal semmi probléma nincsen: ez „jó”. De „jó”-e a másik? Ez nem biztos, lehet olyan k darab alsó pontja, mely k-nál kevesebb fels˝o pontjával van összekötve. Eredetileg ez a k darab pont is legalább k darab felso˝ vel volt összekötve; ez csak akkor lehet, ha a k-adik éppen az A pont volt. Tehát ha az él levágása nem vezetett sikerhez, akkor annyit értünk el, hogy találtunk k pontot alul, melyek együttvéve pontosan k ponttal vannak összekötve. Azt is tudjuk, hogy ez a k pont nem az összes alsó pont, mert például B nem tartozik közéjük (21. ábra). Fessük mármost pirosra az el˝obb említett k alsó pontot és a velük összekötött k fels˝o pontot, kékre pedig a többi pontot! Azt

3. Kombinatorika a mértanban

{

B

k-1

{

A

81

k 21. ábra.

állítjuk, hogy a piros pontok és a kék pontok külön-külön „jó” gráfot alkotnak. Vegyük el˝oször is a piros pontokat! Válasszunk ki közülük néhány alsót, mondjuk j darabot! Azt kellene belátnunk, hogy ezek együttvéve legalább j darab fels˝o piros ponttal vannak összekötve. Ez azonban nyilvánvaló, mert ezek az eredeti gráfban is csak piros pontokkal voltak összekötve és legalább j darabbal. A kék pontokra ugyanígy adódik az állítás, csak feje tetejére kell állítani a gráfot (tudjuk, hogy a gráf ekkor is „jó” marad). Ezzel a bizonyítást be is fejeztük. 9. feladat Bizonyítsuk be, hogy ha egy páros gráfban minden pont foka ugyanannyi, akkor a páros gráf „jó”. (Ezzel a 8. pontban szerepl˝o tételt is bebizonyítjuk, hiszen a jó gráfoknak van els˝ofokú faktoruk.) Az el˝oz˝o feladat mutatja, hogy a feltétel, amelyet találtunk, elég általános, mert a 8. pontban szereplo˝ gráfokra is bizonyítja, hogy van els˝ofokú faktoruk. De vajon nem találhatunk-e még általánosabbat? Könny˝u bebizonyítani, ha egy páros gráfban van els˝ofokú faktor, akkor az „jó” (ennek bizonyítása számotokra a 9 feladat). A matematikusok ezt úgy mondják, hogy a talált feltétel szükséges és elegend˝o.

82

3. Kombinatorika a mértanban

b)

a) 22. ábra.

10. A páros gráfok után most ismerkedjünk meg más különleges gráffajtákkal. Legegyszer˝ubb gráfok azok, amelyekben bármely két pont össze van kötve egy éllel. Az ilyen gráfot teljes gráfnak hívjuk. Rajzoljunk pontokat egy sorba és a szomszédosakat kössük össze. Az így kapott gráfot útnak nevezzük. Ha az elso˝ pontot még az utolsóval is összekötjük, akkor kört kapunk. Ha ugyanezeket a gráfokat másként, például keresztezo˝ désekkel rajzoljuk le, ez mint tudjuk, nem változtat rajtuk lényegesen, ezért továbbra is útnak, illetve körnek hívjuk o˝ ket (22. ábra). 10. feladat Hány éle van egy n pontú teljes gráfnak; egy n pontú útnak és egy n pontú körnek? 11. feladat Nézzük meg, hogy eddigi ábráink közül melyik teljes gráf, út vagy kör! Igen fontosak az összefügg˝o gráfok. Szemléletesen mindenki látja, hogy ez mit jelent, de igen könnyen meg is fogalmazhatjuk: Összefügg˝o az a gráf, melyben bármelyik pontból bármelyik pontba eljuthatunk éleken haladva. Még pontosabban: Összefügg˝o a gráf, ha bármely két pontjához található benne olyan út, melynek ezek a cégpontjai.

3. Kombinatorika a mértanban

83

a) A

B C b) A

B C c) A

B C 23. ábra. Itt tisztáznunk kell valamit. Ha egy A pontot egy B ponttal összeköt egy út, a B pontot egy harmadik C ponttal egy másik út, akkor az A pontból eljuthatunk C -be úgy, hogy az elso˝ úton elmegyünk B-be, és innen a második úton C-be. Ekkor azonban nem biztos, hogy úton haladtunk, mert a második út metszheti az els˝ot akár többször is, mint például a 23.a és b ábrán kivastagított két út. De eljuthatunk úton is A-ból C-be, ha nem teszünk felesleges kitér˝ot B-be. Legegyszer˝ubb, ha az elso˝ úton addig haladunk, míg a második út valamely pontjához érünk, és áttérünk a másik útra, és azon haladunk C-ig. (A 23.a, illetve b ábrán kivastagított utakból ily módon a 23.c ábrán látható utat kapjuk.)

84

3. Kombinatorika a mértanban

12. feladat Egy összefügg˝o gráfban van egy kör. Ennek a körnek egyik élét elhagyjuk a gráfból. Bizonyítsátok be, hogy a visszamaradó gráf is összefügg˝o! 11. Az, hogy egy gráf összefüggo˝ , igen sokszor fontos szempont, ha a gráfelméletet gyakorlatban akarjuk alkalmazni. Például egy ország telefonhálózata jó, ha összefüggo˝ . Igen természetes, hogyan is lehet a telefonhálózatot gráfokkal szemléltetni: pontokkal ábrázoljuk a városokat, és két pontot összekötünk, ha közvetlen telefonösszeköttetés van közöttük. Ennek a gráfnak tehát összefügg˝onek kell lenni. Persze más tulajdonságokat is megállapíthatunk a gráfról, ha a telefonhálózattól további jó tulajdonságokat követelünk meg, például, hogy két város között két teljesen független úton is kapcsolatot lehessen teremteni (biztonsági okokból), vagy azt, hogy legfeljebb háromszori kapcsolással bármely városból bármelyikbe telefonálni lehessen és így tovább. Mi most egyszer˝uség kedvéért ilyen kívánalmakat nem támasztunk. Számunkra tehát a telefonhálózat egyetlen lényeges tulajdonsága az, hogy összefügg˝o legyen. Ezt természetesen a lehet˝o legkevesebb éllel akarjuk elérni. Vagyis nem akarunk fölösleges élt. A 12. feladatban láttuk, hogy egy ilyen gráfban nem lehet kör, mert ennek tetszo˝ leges élét tekintve ez fölösleges él volna, hiszen ezt elhagyva is összefügg o˝ maradna a gráf. Számunkra tehát most azok a gráfok érdekesek, melyekben nincs kör és összefüggo˝ ek. Az ilyen gráfokat fa alakú gráfoknak vagy röviden fáknak nevezzük. Az elnevezés eredetét megértjük, ha megnézzük a 24. ábrán felrajzolt fákat. A fák egyik leglényegesebb tulajdonsága, hogy bennük bármely két pontot pontosan egyféleképpen köthetünk össze úttal. Bizonyítsuk ezt most be! A gráf összefüggo˝ , ezért bármely két pontja összeköthet˝o úttal, csak azt kell tehát kizárnunk, hogy ez többféleképpen is megtehet˝o legyen. Ehhez a másik tulajdonságot használjuk fel, méghozzá úgy, hogy megmutatjuk, hogy ha

3. Kombinatorika a mértanban

85

24. ábra.

C A B D 25. ábra. két pontot két különböz˝o úttal összeköthetnénk, akkor a gráfból ki tudnánk választani egy kört (lásd a 25. ábrát). Induljunk el az A pontból, s menjünk addig a pontig, ahol a két út elágazik. Ezt a pontot az ábrán C-vel jelöltük. Most Cb˝ol kiindulva haladjunk a szaggatott vonallal jelölt úton addig a D pontig, ahol a „folytonos” út újra találkozik a „szaggatottal”. Innen a folytonos vonallal felölt úton térjünk vissza C-be. Ekkor éppen egy kört jártunk be. Kérdések: Jó-e akkor is a bizonyítás, ha a két útnak nincs más közös pontja, mint a végpontok? Találkoztunk-e már olyan gróftípussal, amelyik fa? 13. feladat Bizonyítsátok be, hogy ha egy gráfban bármely két pont pontosan egyféleképpen köthet˝o össze úttal, akkor a gráf fa.

86

3. Kombinatorika a mértanban

14. feladat Egy gráfban nincs kör, de akárhogyan is húzok be egy új élt, már lesz benne kör. Bizonyítsátok be, hogy ekkor a gráf fa! 15. feladat Bizonyítsátok be, hogy minden fában van els˝ofokú pont! 16. feladat Egy valódi fa úgy növekszik, hogy mindig egy újabb kis gallyat hajt. Növeljünk föl mi is hasonlóképpen egy gráfot, úgy, hogy mindig egy újabb pontot veszünk hozzá, és ezt összekötjük egy régivel (ez lesz az új „gally”). Fát kapunk-e így? Minden fát felnövelhetünk-e így? 12. Hány éle van egy fának? Attól függ, hogy hány pontja van, ez természetes. De az már meglep˝o, hogy mástól nem is függ: bár n pontú fa sokfajta van, bármely n pontú fának n − 1 éle van. Ennek bizonyításához ötletet adhat, ha visszatérünk ahhoz a feladathoz, mellyel kapcsolatban a fákat bevezettük. Az egyik városban történt eseményro˝ l értesíteni akarják az összes többit. Ezért a város értesíti a vele közvetlen kapcsolatban lev˝o városokat, ezek továbbítják a hírt a velük kapcsolatban lev˝o városoknak és így tovább. Így a hír mindenhová eljut, mert a hálózat összefügg˝o. Minden városba csak egy úton jutott el az üzenet, és az üzenetek továbbításához minden telefonvonalat felhasználtunk. Így az üzenet továbbítása annyi telefonálásba került, ahány telefonvonal (él) van. De minden telefonálással egy újabb város tudta meg a hírt, tehát a hír forrásával együtt eggyel több város (szögpont) van, mint ahány telefonvonal (él). 17. feladat Bizonyítsátok be ugyanezt a 16. feladatra támaszkodva! 13. Tegyük fel, hogy a telefonvonalak még nincsenek felépítve, hanem éppen most kell a hálózatot megterveznünk. El o˝ ször is azt kell eldöntenünk, hogy mely városok között építünk közvetlen vonalat. Mit˝ol tesszük ezt függ˝ové? Tegyük fel, hogy csak

3. Kombinatorika a mértanban

87

attól, hogy mennyibe kerül (a gyakorlatban persze más szempontok is vannak, de ez mindenképpen fontos). Úgy akarjuk tehát a hálózatot megtervezni, hogy a leheto˝ legolcsóbban kivitelezhet˝o legyen. Els˝o ránézésre azt mondhatnánk, hogy mindegy, mely városok között fektetünk le közvetlen vonalat, hiszen mindenképpen n − 1 vonalat kell lefektetnünk, ezt már tudjuk az el o˝ z˝o pontból. De az egyes vonalak nem egyenlo˝ összegbe kerülnek! Vannak, amelyek olcsóbbak, mások drágábbak, aszerint, hogy a városok közelebb vagy messzebb vannak-e egymástól, van-e közöttük hegyvidék és így tovább. Feladatunk tehát: Keressük meg azt a fát az adott pontok között, amelyhez tartozó élek összköltsége a lehet˝o legkevesebb. Ez sem nehéz! – mondhatjátok. – Csak végig kell próbálgatni a lehetséges fákat, melyik a legjobb. Hol itt a matematika? Azzal az állítással, hogy ez nem nehéz, mi vitába szállunk. Az ilyen végigpróbálgatás nehézsége abban van, hogy igen sok esetet kell megkülönböztetni. Itt – közbeveto˝ leg – felmerül az a kérdés is tehát; hogy hány fa rajzolható az adott n pont közé. Erre az utóbbi kérdésre válaszolni igen nehéz, komoly feladat, így most mi csak a végeredményt közölhetjük: nn−2 . Hogy fogalmat alkothassatok róla, milyen nagy szám ez, megjegyezzük, hogy 10 város esetén 108 , vagyis 100 000 000 (százmillió) különbözo˝ lehet˝oség van arra, hogy a telefonhálózatot megépíthessük. Ennyi különböz˝o lehet˝oség végigszámolása reménytelen feladat. Ezért más módot kell találnunk a legjobb fa megkeresésére – és éppen ebben van itt a matematika. Van egy közismert példázat az optimista és a pesszimista emberr˝ol. Mindegyik kap egy tál cseresznyét. Az optimista kiveszi el˝oször a legjobbat, majd a maradékból a legjobbat és így tovább, mindig a legjobb cseresznyét eszi meg a még meglevo˝ k közül. A pesszimista ezzel szemben kikeresi a legrosszabbat, és azt eszi meg, és ugyanígy jár el mindig. Így az optimista mindig a leheto˝ legjobb cseresznyét eszi meg, a pesszimista mindig a leheto˝ legrosszabbat – bár ugyanolyan mino˝ ség˝u cseresznyés tálat kaptak. Nézzük meg, mit csinálna egy optimista vállalkozó az esetünkben. Optimista lévén, pénz nélkül is elvállalja a feladatot.

88

3. Kombinatorika a mértanban

Megvárja, míg összegy˝ulik elég pénze ahhoz, hogy megépítse a legolcsóbb összeköttetést, és ekkor ezt megépíti. Utána ismét vár, amíg elég pénze nem lesz ahhoz, hogy a következo˝ legolcsóbbat megépíthesse, és megépíti ezt és így tovább. Persze olyan városok közötti vonalat sohasem épít meg, melyek már – közvetve vagy közvetlenül – kapcsolatban vannak egymással. Így végül is egy megfelel˝o telefonhálózatot épít ki – csak az a kérdés, ez a lehet˝o legolcsóbb-e? Lehetséges, hogy a kezdeti túlzott takarékosság kés˝obb megbosszulja magát – vagy nem? Eláruljuk, hogy ez nem következhet be, s így eljárása érdemtelenül sikerhez vezet. Ezt hamarosan be is bizonyítjuk. 14. El˝obb azonban meg kell indokolnunk, miért volt „érdemtelen” az el˝obbi épít˝o sikere. Azért, mert szerencséje volt a feladattal. Ha egy kissé módosítjuk a feladatot, a módszerével egészen rossz eredményt ért volna el: A telefonhálózatot biztonsági okokból úgy kell építeni, hogy bármely két város két, egymástól teljesen független úton is összeköthet˝o legyen (így hiba esetén sem sz˝unik meg a kapcsolat). Ehhez már nem elegend˝o n − 1 vonal megépítése; n vonallal azonban megvalósítható a feladat: egyetlen körre kell felf˝uzni mind az n pontot. Feladat tehát: kiválasztani azt a kört, mely az összes várost tartalmazza, és az éleinek megfelelo˝ telefonvonalak építési költsége a lehet˝o legkevesebb. Optimista épít˝onk most a következ˝oképpen járna el. Megépítené a legolcsóbb vonalat, majd a maradékból a legolcsóbbat, és így tovább, de vigyázna persze közben, hogy ne építsen fölösleges vonalat, tehát ha egy városból már két vonal kiindul, akkor harmadikat már nem épít, és olyan vonalat sem, amely hamarabb bezárná a kört. Így megkap ugyan egy megfelelo˝ hálózatot, de korántsem a legjobbat. Kövessük nyomon a munkáját a 26. ábrán. A bal oldali ábrán az egyes élekre írt számok az építési költséget jelentik, mondjuk millió Ft-ban. E mellé lerajzoltuk azt a kört, amelyik a legolcsóbb, és mellé azt, amelyiket építo˝ nk kap meg. Láthatjuk, hogy neki 1 millió forinttal többe került az építkezés! (Erre az utóbbi feladatra nem is olyan könny˝u megoldást

3. Kombinatorika a mértanban

89

5

3

3

3 2

3

3+3+3+3=12 (legjobb)

2+3+3+5=13 (amit a vállalkozó megépít)

26. ábra. találni, ha sok város van. Vannak ugyan használható módszerek, de ezekhez számítógépet kell igénybe venni.) Mi most inkább visszatérünk az els˝o feladat megoldására. 15. Be akarjuk bizonyítani tehát, hogy az optimista eljárás megadja a legolcsóbb fát, más szóval, hogy bármely másik fa megvalósítása legalább ennyibe kerül. Jelöljük azt a fát, amit az eljárás szolgáltat F-fel, és egy másik fát G-vel. Álljunk meg, amikor F megszerkesztése során el˝oször választunk G-hez nem tartozó élt. Legyen ez az él a. Ha az a élt a G fához hozzávesszük, G-ben keletkezik egy kör. De ezt megszüntethetjük úgy, hogy valamelyik másik élét elhagyjuk. Az egész kör nem tartozik F-hez, így elhagyhatjuk olyan élét, mondjuk b-t, amelyik nem tartozik F-hez. Így G-t helyettesítettük egy H fával (27. ábra; vastagon húztuk ki a már kiválasztott vonalakat). Most jön a dönt˝o megfigyelés: az elhagyott b él legalább anynyiba kerül, mint a, mert ha olcsóbb volna, akkor a helyett b-t vettük volna hozzá a szerkesztési eljárás során a már kiválasztott élekhez. Itt meg kell még gondolnunk, hogy h hozzávételével nem keletkezhetett kör, mert ez a kör G-beli kör lenne, hiszen F-nek a el˝ott választott élei, és b is G-beliek. Így tehát a H fa olcsóbb, vagy legfeljebb annyiba kerül, mint G. Ha most a H fával csináljuk meg ugyanazt, H-t helyettesíthetjük egy még olcsóbb fával és így tovább. A kapott fák egyre több élben egyeznek meg F-fel, végeredményben tehát F-hez jutunk.

90

3. Kombinatorika a mértanban

4 2

a

1

b 3

5 G F 27. ábra.

Közben a költség egyre csökkent, vagy legalábbis nem növekedett, eszerint tehát G költsége legalább annyi kell hogy legyen, mint F költsége. Így az optimista építo˝ nek szerencséje van, a lehet˝o legkevesebbet fizeti. 18. feladat A pesszimista vállalkozó így okoskodott volna: a végén biztosan a legdrágább vonalat kellene építenem, ha nem volnék el˝ovigyázatos; ezért a legdrágább vonalat eleve kihúzom a megépíthet˝o vonalak listájából. Ezekután kihúzom a második legdrágábbat is, majd a harmadikat és így tovább. De vigyáznom kell, hogy a megmaradt vonalak még összefügg˝o hálózatot alkossanak. Ezért ha odáig jutok, hogy a soron következ˝o legdrágább vonal elhagyása után már nem maradna összefügg˝o a még megépíthet˝o hálózat, akkor ezt nem húzhatom ki, hanem meg kell építenem. Miután megépítettem, áttérhetek a soron következ˝o legköltségesebb vonalra, megnézhetem, hogy elhagyható-e, és eszerint elhagyom vagy megépítem és így tovább. A pesszimista vállalkozó a meglev˝o vonalak közül mindig a legdrágábbat építi meg tehát! És mégis – ennek bizonyítása a ti feladatotok – ugyanannyi lesz a költsége, mint az „optimistának”, más szóval, o˝ is a legolcsóbb lehet˝oséget találta meg.

3. Kombinatorika a mértanban

91

19. feladat Tudnátok-e még további eljárást kieszelni a legolcsóbb fa megszerkesztésére? 20. feladat Mit csinál a pesszimista vállalkozó, ha a 14. pontban szerepl˝o feladatot kell megoldania? Ha módszerét (fogalmazzátok meg, mi is ez a módszer ebben az esetben!) a 26. ábra gráfjára alkalmazza, akkor a legolcsóbb kört kapjuk. Tudnátok-e úgy módosítani az ábrát, hogy a pesszimista ne a legolcsóbbat kapja? Csináljatok olyan példát, hogy a két vállalkozó mindegyike pórul járjon! 16. Eddig már nagyon sok tulajdonságát láttuk a gráfoknak, de jogosan kérdezitek, hogy mi közük a négyszínsejtéshez. Most röviden kitérünk erre. Van egy igen kézenfekv˝o lehet˝oség arra, hogy a négyszínsejtést gráfokkal kapcsolatba hozzuk: Egy térkép felfogható gráfként, ha csúcsoknak tekintjük azokat a pontokat, ahol legalább három ország találkozik és élekként az ezeket összeköto˝ határszakaszokat6. Így egy síkba rajzolható gráfot kapunk. A keletkez˝o síkrészeket, vagyis az országokat kell kiszínezni négy színnel úgy, hogy a szomszédos országok különbözo˝ színnel legyenek kiszínezve. Így azonban nem sokkal jutunk közelebb a feladat megoldásához, mert a gráfnak nemcsak pontjai és élei szerepelnek, hanem a keletkez˝o országok is. Máshogyan is ábrázolhatjuk gráffal a problémát. Egy-egy országnak feleljen meg egy-egy pont, legcélszer˝ubb, ha a térképen az országok f˝ovárosát összekötjük éllel. Az éleket úgy rajzoljuk, hogy a közös határszakaszt messék, és az egy fo˝ városból szétágazó élek egymást ne keresztezzék (ilyenek általában a szomszédos f˝ovárosokat összeköt˝o vasútvonalak). Így egy gráfot kapunk (28. ábra). És most egy nagyon fontos megfigyelés következik: Ez a gráf is síkba van rajzolva! A térkép kiszínezése azt jelenti, hogy a gráf pontjait kell négy színnel kiszínezni úgy, hogy az éllel 6 A már említett kivételekto ˝ l most tekintsünk el (ezekro˝ l könnyen belátható, hogy érdektelen esetek a négyszínsejtés szempontjából).

92

3. Kombinatorika a mértanban

28. ábra. összekötött pontok különbözo˝ szín˝uek legyenek. A négyszínsejtés tehát így fogalmazható meg: Bármely síkba rajzolható gráf pontjait ki lehet színezni négy színnel úgy, hogy bármely él két végpontja különböz˝o szín˝u legyen. 21. feladat Tekintsük a fenti második gráf éleit, mint egy másik térkép országhatárait! Készítsük el ennek a térképnek a f˝ovárosaiból kapott gráfot a fentiekhez hasonlóan! Mi ez a gráf? 17. Térjünk most vissza egy régebbi geometriai feladatunkra. A 3. feladatban azt kellett bizonyítani, hogy ha egyeneseket rajzolunk a síkra, akkor a keletkez˝o síkrészek kiszínezhet˝ok két színnel. Átsiklottunk azonban egy sokkal természetesebb kérdés felett; hány síkrész keletkezik összesen? Ez természetesen függ attól. hogy hogyan helyezzük el az egyeneseket. Például két pár-

3. Kombinatorika a mértanban

93

3 1 1

2

3

4

1

6 2

5

2 3

4

3

4

2 7 1

a)

b)

5

6 d)

c)

29. ábra. 1

2

3 9

1 2

4

2

4

2

3

8

7 6

4

10 5

5 1

3 11

7

6

30. ábra. huzamos egyenes három részre, két metszo˝ egyenes viszont négy részre osztja a síkot (29. ábra). Egy másik példa: három egyenes esetén ha egy ponton mennek át, akkor 6 részt kapunk, viszont ha nem mennek át egy ponton, akkor 7-et. Ezekután meglepo˝ megállapítást teszünk: ha az a) és c) esetet kizárjuk, akkor már mindegy, hogyan helyezzük el az egyeneseket. Olyan egyeneseket tekintünk tehát, melyek között nincs két párhuzamos, és semelyik három nem megy át egy ponton. Az ilyen egyeneseket röviden általános helyzet˝u egyeneseknek fogjuk nevezni. Pontosan megfogalmazva tehát a feladatunk: n általános helyzet˝u egyenes hány részre osztja a síkot? Rajzoljuk föl egyenként az egyeneseket, és nézzük meg, hogyan n˝o eközben a részek száma (30. ábra). Táblázatot készítve:

94

3. Kombinatorika a mértanban egyenesek száma

1

2

3

4

síkrészek száma

2

4

7

11

Nézegessük egy kicsit ezt a táblázatot. Látjuk, hogy az új egyenes behúzása el˝oször 2-vel, majd 3-mal, majd 4-gyel növelte a síkrészek számát. Ebb˝ol az a sejtésünk támad, hogy az n-edik egyenes n-nel növeli a keletkezo˝ részek számát. Bizonyítsuk ezt be! Mit˝ol is n˝o az országok száma egy új egyenes behúzásakor? Attól, hogy bizonyos országokat ez az egyenes kettévág, és éppen annyival, ahányat kettévág. Hány régi országon halad át ez az új egyenes? Végighaladva az egyenesen, mindig akkor jutunk egy újabb országba, ha keresztezünk egy másik egyenest. Az egész egyenesen n − 1 keresztez˝odés van, ami azt jelenti, hogy az egyenes a országon halad át. Tehát csakugyan n-nel no˝ az országok száma. (Azt, hogy az egyenesek általános helyzet˝uek, úgy használtuk ki, hogy az új egyenes az összes régit keresztezi, és ezek a keresztez˝odések mind különböz˝oek.) Még nem vagyunk készen, még csak azt tudjuk, hogy mennyivel n˝o az országok száma az n-edik egyenes behúzása után. Az országok száma tehát 2, 2 + 2, 2 + 2 + 3, 2 + 2 + 3 + 4 és így tovább, n egyenes esetén 2 + 2 + 3 + 4 + · · · + n. Ezt egy kicsit másképpen írva: 1 + 1 + 2 + 3 + 4 + · · ·+ n, vagyis a keletkezo˝ országok száma éppen 1-gyel nagyobb, mint a természetes számok összege n-ig. Ezt pedig már egy régebbi feladatban kiszámítottuk; az országok száma végeredményben: n(n + 1) + 1. 2 Elmondunk egy másik megoldást is, amely közvetlenebbül, de csalafintábban számolja össze az országokat. Képzeljük az egyeneseket egy táblára rajzolva, méghozzá felfelé jobbra és balra végtelenbe nyúló táblára. Ábránkat úgy helyezzük el, hogy az egyenesek összes metszéspontja a táblára essen, és ne szerepeljen vízszintes egyenes (31. ábra). Nézzük most az egyes országok legalsó pontját. Azok az országok, amelyeknek ilyen nincs, a tábla alsó szélén keresztül a

3. Kombinatorika a mértanban

95

31. ábra. végtelenbe nyúlnak. Amelyeknek van, azoknak csak egy van, mert nem lehet vízszintes alsó határszakaszuk. Ha megnézünk egy metszéspontot, itt négy ország találkozik, és ez a metszéspont egynek (a legfels˝onek) a legalsó pontja, a többinek biztosan nem. Az eddigiekb˝ol azt olvashatjuk ki, hogy olyan ország, amelynek van legalsó pontja, éppen annyi van, ahány metszés
pontja van az n egyenesnek. Az ilyen metszéspontok száma n2 . Maradnak még azok az országok, amelyeknek nincs legalsó pontjuk. A tábla alsó szélét az n egyenes n + 1 részre osztja, és egy-egy ilyen részen keresztül egy-egy ilyen ország nyúlik ki, tehát n + 1 ilyen ország van. Összegezve az
eredményeket, azt kapjuk, hogy a keletkezett országok száma n2 + n + 1. 22. feladat Ugyanannyit kaptunk-e, mint el˝obb?

18. Az el˝oz˝oekben lényegében azt számítottuk ki, hogy speciálisan szerkesztett síkba rajzolt gráf hány részre osztja a síkot. (Csúcsoknak tekinthetjük a metszéspontokat, éleknek az egyeneseknek ezek közé es˝o szakaszait. Tekintsünk el most attól, hogy „végtelenbe nyúló” élek is el˝ofordultak. Igen fontos az az eredmény, melyet Euler, a XVII. század legnagyobb matematikusa ta-

96

3. Kombinatorika a mértanban

lált, és melynek segítségével az országok számát bármely összefügg˝o síkba rajzolt gráfnál kiszámíthatjuk, ha az élek és a csúcsok számát ismerjük. A híres Euler-féle összefüggés a következo˝ : országok száma + csúcsok száma = élek száma + 2. Ennek az összefüggésnek a levezetését egy kis történettel fogjuk szemléletessé tenni. Ez a keret nem von le semmit a bizonyítás matematikai értékéb˝ol. Tekintsük gráfunkat ismét térképnek. Célszer˝ubb azonban, ha az éleket ezúttal nem országhatároknak, hanem gátaknak tekintjük, az élek találkozási pontjait o˝ rtornyoknak. A közrezárt területek tehát nem országok, hanem medencék. Legkívül van a tenger, a többi medence viszont száraz. Miért célszer˝ubb ez a felfogás? Azért, mert a 32. ábrán látható móló országhatárnak nem fogható fel (mert mindkét oldalán ugyanaz az ország volna), de gátnak igen. A szigetet ellenség támadja meg, ezért védo˝ i az egész szigetet az óceán vizével árasszák el, bizonyos gátak felrobbantása árán. A véd˝ok reménykednek abban, hogy a támadás visszaverése után visszatérhetnek, ezért igyekeznek a leheto˝ legkevesebb gátat felrobbantani. A következ˝o módon végzik a robbantást. Egyszerre csak egy gátat robbantanak fel, és csak olyat, amelyiknek egyik oldalát víz mossa, a másikat azonban nem. Ilyenkor az óceán beömlik az él másik oldalán lev˝o mindeddig száraz medencébe. Meg kell itt jegyeznünk, hogy a medencét határoló többi gát sértetlen még ekkor, ezért a víz csak ezt az egy lapot önti el. Az ábrán megjelöltük, hogy melyik gátakat és milyen sorrendben robbantjuk. Jelöljük az o˝ rtornyok (csúcsok) számát c-vel, a gátak (élek) számát e-vel, a medencék (országok) számát l-lel (ez a szokásos jelölés, kés˝obb majd megmagyarázzuk, hogy miért). Mire a sziget l − 1 medencéje megtelik vízzel, éppen l − 1 robbantást kell végezni. Milyen gráf marad a robbantások után? Elo˝ ször is nem lesz benne kör, mert egy ilyen kör belseje száraz maradt volna. Má-

3. Kombinatorika a mértanban

97

1 3

2 móló

32. ábra. sodszor összefügg˝o maradt a gátrendszer, mert minden felrobbantott gát egy körnek volt az éle (azon medence határának, melyet a víz a felrobbantása révén önt el), és tudjuk a 11. feladatból, hogy ilyen él elhagyása nem szünteti meg az összefüggo˝ séget. A kapott gráf tehát összefügg˝o és nincs benne kör, tehát fa. Most felhasználjuk azt a fontos összefüggést, hogy egy fának eggyel kevesebb éle van, mint ahány csúcsa. A mi fánknak c csúcsa van, tehát c − 1 éle. Összegezve az eddigieket, fel kellett robbantani l − 1 élt, és maradt c − 1 él. Az élek száma tehát e két szám összege, képletben kifejezve: (c−1)+(l −1) = e. Ha itt felbontjuk a zárójeleket, és mindkét oldalhoz 2-t adunk, azt kapjuk, hogy: l +c = e+2 és éppen ez az, amit bizonyítanunk kellett. 23. feladat Számoljátok össze, hány részre osztja n egyenes a síkot, abból kiindulva, hogy az egyeneseket egy nagy kör alakú szi-

98

3. Kombinatorika a mértanban

33. ábra. geten épült gátaknak tekintitek. Segítségül nézzétek meg a 33. ábrát (ha ezt a feladatot megoldjátok, akkor ez már a harmadik módszer lesz ugyanennek a feladatnak a megoldására). 19. Régi adósságunk annak a ténynek a bizonyítása, hogy az ötpontú teljes gráf (teljes ötszög) nem rajzolható síkba. Meglepo˝ módon ezt az Euler-összefüggés segítségével fogjuk megtenni. Megmutatjuk, hogy képtelenséghez vezet az a feltételezés, hogy síkba rajzolható volna a teljes ötszög. Feltételezzük tehát, hogy a teljes ötszöget lerajzoltuk a síkba keresztezo˝ dés nélkül. (Sajnos, ábrát nem tudunk mellékelni, mert éppen azt akarjuk bebizonyítani, hogy ez lehetetlen.) Számítsuk
ki, mennyi lenne a síkrészek száma. Csúcs van öt, él van 52 = 10, és az Euler-féle összefüggés szerint a keletkezo˝ részek száma: 10 + 2 − 5 = 7. E 7 rész mindegyikét legalább három él határolja, így ha részenként számoljuk össze az éleket, azt kapjuk, hogy legalább 3·7 2 = 10,5 él van. (Azért kellett 2-vel osztanunk, mert minden élt két lapnál is beszámoltunk.) Így az a feltevésünk, hogy a teljes ötszög síkba rajzolható, ahhoz a képtelen következményhez vezetett, hogy 10 > 10,5. Ezek szerint a teljes ötszög nem lehet síkba rajzolható.

3. Kombinatorika a mértanban

99

24. feladat Síkba rajzolható-e az a gráf, melyet úgy kapunk, hogy a teljes ötszögb˝ol elhagyunk egy élt? 25. feladat Van három ház és három kút. Vezethetünk-e minden házból minden kúthoz egy-egy utat úgy, hogy ezek az utak ne keresztezzék egymást? 26. feladat Egy szigeten c o˝ rtorony van megépítve. Hány gátat lehet építeni legfeljebb úgy, hogy minden gát két o˝ rtornyot kössön össze? 27. feladat Hány részre osztják az átlói a konvex n-szöget, ha semelyik három átló nem halad át egy ponton? 20. Még egy látszólag jelentéktelen kérdés hátra van. Miért jelöltük l-lel az országok számát? Nos, ez a lap szó kezdo˝ bet˝uje. Euler ugyanis egyáltalán nem térképeket vizsgált, amikor az összefüggéshez eljutott, hanem olyan testeket, melyeket síklapok határoltak – kockát, gúlát, hasábot. Számítsuk ki néhány testnél a lapok, élek, csúcsok számát: Lapok

Élek Csúcsok száma

Kocka

6

12

8

Háromoldalú gúla

4

6

4

Háromoldalú hasáb

5

9

6

Ötoldalú hasáb

7

15

10

Ötoldalú gúla

6

10

6

Könnyen meggy˝oz˝odhetünk róla, hogy mindegyik esetben fennáll: lapok száma + csúcsok száma = élek száma + 2. Ez nagyon hasonlít az Euler-féle összefüggéshez, azzal a különbséggel, hogy itt országok helyett lapok szerepelnek. A hasonlóság nem véletlen, ezt az összefüggést a másikból igen könnyen

100

3. Kombinatorika a mértanban

34. ábra. kaphatjuk meg a következ˝oképpen: Képzeljük el, hogy a test gumiból van. Fúrjunk egyik lapjába egy lyukat, és „fújjuk fel”, mint valami léggömböt. A leggyakoribb testek ilyenkor gömbbé fúvódnak fel (például a kocka, vagy a gúla). Vigyázzunk azonban, lehetnek olyan testek is, melyek nem fújhatók fel gömbbé. Például a 34. ábrán látható „képkeret” egy mento˝ övhöz hasonló tárggyá fúvódik fel. A fenti összefüggés csak a gömbbé felfújható testekre érvényes! (Megnyugtatásul közöljük, hogy például a konvex testek mind ilyenek.) Ezekután ragadjuk meg a kapott gumigömböt a fúrt lyuk szélénél és nyújtsuk, amíg az egész egy nagy sík lappá nem nyúlik szét. Ezt terítsük le a síkra. Ha a test éleit mondjuk feketével kihúztuk, akkor most egy térképet fogunk látni a síkon, melynek csúcsai a test csúcsai, élei a test élei, országai a test lapjai. Ezért az Euler-féle összefüggés térképekre vonatkozó alakjából éppen a fenti, testekre vonatkozó alakját kapjuk. (Egyébként Euler maga is ilyen formában mondta ki a tételt.) 21. Nagyon sok kérdést lehet találni a geometriában, melynek megválaszolásához kombinatorikai módszerek kellenek. Ezek a kérdések sokszor nehezebbek, mint a „szokásos” mértani feladatok. Már említettük a négyszínsejtést, mint megoldatlan problémát. Most megismertetünk benneteket egy másik megoldatlan

3. Kombinatorika a mértanban

a)

101

b) 35. ábra.

kérdéssel, amely talán még az elo˝ z˝onél is egyszer˝ubben fogalmazható meg. Nézzük el˝oször is a következ˝o feladatot: Bizonyítsuk be, hogy akárhogyan is adunk meg a síkban öt pontot úgy, hogy semelyik három nincs egy egyenesen, van köztük négy, melyek egy konvex négyszög csúcsait alkotják. Hogy a továbbiakban rövidebben fogalmazhassunk, bizonyos pontokat általános helyzet˝ueknek mondunk, ha közülük semelyik három sincs egy egyenesen. Emlékeztetünk arra, hogy egy sokszöget akkor nevezünk konvexnek, ha minden szöge konvex. Négyszög esetén ez ugyanazt jelenti, mint az, hogy a két átlója metszi egymást (35. ábra). Itt a) konvex, b) konkáv négyszög. Képzeljük el, hogy általános helyzet˝u pontok vannak egy táblán felrajzolva. Verjünk helyükbe szögeket, és feszítsünk gumit köréjük. A gumi egy konvex sokszöget határol, amelynek a csúcsai a felrajzolt pontok küzül valók, és a többi felrajzolt pont a belsejébe esik (36. ábra). Ezt a sokszöget a pontok konvex burkának nevezzük. 36. ábra Rátérve most feladatunkra, nézzük meg, milyen lehet a mi öt pontunk konvex burka. Ha ez ötszög, akkor bármelyik négy pont egy konvex négyszög négy csúcsa. Ha a konvex burok négyszög, akkor az maga a kívánt négyszög. Marad

102

3. Kombinatorika a mértanban

A

E D

C

B 37. ábra.

tehát az az eset, ha a konvex burok háromszög. Jelöljük a háromszög csúcsait A-val, B-vel, C-vel, a másik két adott pontot D-vel és E-vel! D és E az ABC háromszögön belül fekszenek, a DE egyenes tehát két pontban metszi a háromszög kerületét. Mondjuk, ez a két pont az AB és AC oldalon van (ha nem így volna, átbet˝uzhetnénk a háromszög csúcsait). Most már ti is könnyen meggondolhatjátok, hogy a B, C, D és E pontok egy konvex négyszög csúcsai (37. ábra). A matematikában néha olyan tételeket lehet felhasználni bizonyítás közben, melyekr˝ol els˝o pillanatra nem is gondolnánk, hogy van valami közük a bizonyítandó dologhoz. Gondolná-e bármelyik˝otök, hogy az el˝obb bizonyított feladatot meg lehet oldani arra hivatkozva, hogy az ötpontú teljes gráfot nem lehet síkba rajzolni (ezt a 19. pontban bizonyítottuk be)? Tehát visszatérve az adott öt ponthoz, kössük össze bármelyik ketto˝ t egy egyenes szakasszal. Mivel az így kapott gráf nem rajzolható síkba, ezért ezen szakaszok közül valamely kett˝o metszi egymást. Ennek a két szakasznak a négy végpontja olyan négyszöget alkot, melynek átlói metszik egymást, vagyis konvex négyszöget. Nem t˝uzzük ki feladatként, mert az eddigieknél jóval nehezebb, de azért megpróbálkozhattok vele (ne keserítsen el benneteket, ha nem sikerül)

3. Kombinatorika a mértanban

103

Bizonyítsuk be, hogy kilenc általános helyzet˝u pont közül mindig kiválasztható egy konvex ötszög. 28. feladat Rajzoljatok föl nyolc pontot úgy, hogy ne lehessen kiválasztani közülük konvex ötszöget! Igen bonyolultan, de bebizonyították azt is, hogy 17 általános helyzet˝u pontból mindig kiválasztható konvex hatszög. Ezek után természetszer˝uleg felvet˝odik a kérdés, hogy hány általános helyzet˝u pont szükséges ahhoz, hogy mindig ki lehessen választani közülük konvex n-szöget. Más szóval: Legfeljebb hány pontot lehet megadni a síkban, hogy ne lehessen közülük kiválasztani konvex n-szöget? Ha a már ismert esetekb˝ol táblázatot készítünk, nem nehéz megsejteni; mi a legvalószín˝ubb válasz: n

2

3

4

5

6

1

2

4

8

16

(Az n = 2, 3 eseteket eddig nem említettük, mert ezek nem érdekesek, de a teljesség kedvéért kiegészítettük velük a táblázatot. A kétszög nem más, mint a szakasz, így minden kétszög és minden háromszög konvex.) Észrevehetjük, hogy a konvex n-szöget nem tartalmazó pontok maximális száma kétszeresére no˝ , ha n-et 1-gyel növeljük, legalábbis ezekben az esetekben. Kézenfekvo˝ feltételezni, hogy ez a továbbiakban is így lesz, vagyis hogy ez a szám 2n−2. Ezt azonban mindmáig nem sikerült bebizonyítani.

4 Blokkrendszerek

1. Láttunk már példát arra, hogy egy társaságban az ismeretségek matematikailag ábrázolhatók és vizsgálhatók, gráfok segítségével. Másféle társadalmi alakzatok is leírhatók matematikai modellel – persze ez a modell sok más célra is használható lesz. Képzeljük el, hogy egy közösség tagjai, pl. egy kisváros lakói klubokat hoznak létre. Ennek a kisvárosnak a lakói azonban nagyon demokratikus érzelm˝uek, és a legkisebb társadalmi egyenl˝otlenséget sem t˝urik meg. Ezért el˝oször is nem engedik, hogy legyenek nagyobb klubok, mert szerintük ezek elnyomják a kisebbeket, vagyis kikötik, hogy mindegyik klubnak ugyanannyi tagja legyen. Továbbá azt sem engedik, hogy egyik ember több klubnak legyen tagja, mint a másik ember, hiszen akkor az elo˝ bbi esetleg nagyobb befolyásra tenne szert. Tehát minden ember ugyanannyi klubnak lesz a tagja. Végül még arra is gondolnak, hogy nem lenne helyes, ha A városlakó B és C városlakókkal szemben nem viselkednék egyenl˝oen, hanem pl. B-vel szorosabb kapcsolatban lenne oly módon, hogy azon klubok száma, melyeknek A is és B is tagja, nagyobb lenne, mint azok száma, melyeknek A és C közösen tagja.

106

4. Blokkrendszerek

Végeredményben tehát a városlakók (számukat jelölje v) klubokba vannak szervezve, mindegyik klubnak ugyanannyi tagja van, mondjuk k, a klubok számát jelölje b, továbbá tudjuk, hogy minden lakos ugyanannyi, mondjuk r db klubnak tagja, és bármely két lakoshoz pontosan λ1 db klub van, melynek mindketten tagjai. Nézzük most, hogy tudunk-e valami összefüggést találni az öt szám: b, v, r, k, λ között? Ha minden klub minden tagjának tagsági igazolványt állít ki, hány tagsági igazolvány van? Van b db klub és mindegyiknek k tagja, tehát összesen bk db tagsági igazolvány. De másfel˝ol a városnak v lakója van, és mindegyiknek r tagsági igazolványa van, tehát a tagsági igazolványok száma vr. Azaz bk = vr.

(1)

Másrészt képzeljük el, hogy a klubok úgy is ero˝ síteni akarják tagjaik között a barátságot, hogy megkérik minden tagjukat: egyegy alkalommal a klub székházában vacsorázzanak együtt kettesben mindegyik klubtársukkal. Ha most a város egy aggódó lakója ki akarja számítani, hogy hány vacsorára van kötelezve, így okoskodhat: „Rajtam kívül még v − 1 lakosa van a városnak. Mindegyikkel λ klubnak vagyok közösen a tagja, tehát mindegyikkel λ vacsorát kell elköltenem más-más klubszékházakban. Ez összesen λ(v − 1) vacsora.” De így is okoskodhat: „r klubnak vagyok a tagja. Mindegyiknek rajtam kívül még k − 1 tagja van. Tehát mindegyik klubomban (k − 1)-szer kell vacsoráznom. Ez összesen r(k − 1) vacsora.” A kétféle számolás azt mutatja, hogy r(k − 1) = λ(v − 1).

(2)

1. feladat Ha egy kisvárosnak 924 klubja van, mindegyik 21 taggal, és bármely két ember pontosan 2 klubnak lesz közösen 1

A λ görög bet˝u, az l-nek felel meg. Így ejtik: lambda.

4. Blokkrendszerek

107

a tagja, akkor hány lakosa van a városnak? Hány klubnak tagja minden egyes ember? (Ne lep˝odjetek meg! Ez egy nagyon kicsike város, és mindenki nagyon sok klubnak a tagja.) 2. Látjuk, hogy a b, v, r, k, λ számok közül csak hármat adhatunk meg kedvünk szerint, mert a másik ketto˝ t már az (1)-gyel és (2)-vel jelölt összefüggések meghatározzák. De még hármat sem adhatunk meg akárhogy! Lehet-e például egy 500 lakosú városban 11 tagú klubokat csinálni úgy, hogy mindenki 7 klubnak legyen a tagja? A válasz ez: nem lehet. De ezt be kellene bizonyítani. Most álljatok meg az olvasásban, és próbáljátok ti magatok bebizonyítani! (Nem is olyan nehéz.) Sikerült? Mi így bizonyítottuk: Ha lehetne így klubokat csinálni, a klubok száma, b persze egész szám lenne. Mennyinek kellene lennie? (1)-bo˝ l tudjuk: b=

v · r 500 · 7 2 = = 318 . k 11 11

De ez nem egész szám. Tehát biztosan nem lehet ilyen klubokat csinálni. Vigyázzunk azonban! Abból, hogy a b, v, r, k, λ természetes számok kielégítik az (1) és a (2) egyenlo˝ ségeket, még nem következik, hogy a v lakosú városban lehet b db k tagú klubot csinálni úgy, hogy minden ember r klubnak, és bármely két ember közösen λ klubnak legyen a tagja. Például a b = v = 43, k = r = 7, λ számok kielégítik (1)-et és (2)-t is, mégsem lehet velük klubokat csinálni. Ennek az állításnak a bizonyítása azonban nehezebb annál, semhogy itt le tudnánk írni. 3. Ha figyelmesen elolvastátok az elso˝ fejezetet, akkor biztosan ismeritek a halmaz fogalmát. Ennek a fogalomnak a segítségével most már megtudjuk fogalmazni, hogy mit nevezünk blokkrendszernek: Legyen adott egy v elem˝u halmaz. Válasszuk ki ennek k elem˝u részhalmazait (amelyeket blokkoknak fogunk nevezni), mégpedig úgy, hogy minden elem pontosan r blokkban forduljon el o˝ , és

108

4. Blokkrendszerek

bármely két különböz˝o elem pontosan λ blokkban forduljon elo˝ közösen. A blokkok számát jelöljük b-vel! Ugye látjátok, hogy az így definiált blokkrendszerek valójában semmiben sem különböznek az eddig tárgyalt kluboktól, csak eddig a v elem˝u halmaz elemeit városlakóknak, a blokkokat pedig kluboknak neveztük. Ezután is szívesebben beszélünk városról és klubokról, és reméljük, senkit sem fog zavarni, hogy néha olyan városokról is szó lesz, melyeknek összesen 7 lakosa van. Lássunk most már példákat 1 blokkrendszerekre! Itt van egy az 1. ábrán. Ezt az ábrát úgy kell érteni, hogy a számozott fekete pontok jelölik a városlakókat, és 6 2 3 olyan városlakó alkot egy klu4 bot, aki az ábrán egy egyenes vonallal van összekötve, illetve van még egy klub, amelynek 3 tagját 7 3 egy kör köti össze. 5 Nézzük meg, hogy tényleg blokkrendszert kaptunk-e? Min1. ábra den klubnak 3 tagja van (azaz k = 3). Ez tehát rendben van. Ha megnézzük az 1-to˝ l 7-ig számmal jelölt városlakókat, azt látjuk, hogy mindegyik pontosan 3 klubnak tagja (tehát r = 3). Végül, ha megnézzük, hogy két különböz˝o ember hány klubnak tagja közösen, azt látjuk, hogy pontosan egynek. Például a „2” és „6” városlakók egyetlen klubnak tagjai közösen: annak, amelynek harmadik tagja „5”. Ugyanígy ellen˝orizhetjük az összes többi párt is. Látjuk tehát, hogy λ = 1. Tehát tényleg blokkrendszert kaptunk. A blokkok (vagy klubok) száma: b = 7. Ugyanezt a blokkrendszert másként is ábrázolhatjuk: egymás után leírjuk az egyes klubok tagnévsorát: (1, 2, 3); (1, 4, 5); (1, 6, 7); (2, 4, 7); (2, 5, 6); (3, 4, 6); (3, 5, 7);. Egy-egy zárójelen belül tüntettük fel az illeto˝ klub 3 tagját.

4. Blokkrendszerek

109

4. Ennek a blokkrendszernek, amit most csináltunk, megvan az a tulajdonsága, hogy a blokkok 3 elem˝uek és minden pár pontosan egy hármasban (blokkban) van benne. Szokásos jelöléseinket használva ezt úgy is fogalmazhatjuk, hogy k = 3 és λ = 1. Az olyan blokkrendszereket, amelyeknél k = 3 és λ = 1, Steinerrendszereknek nevezik. (Azért, mert egy Steiner nev˝u svájci matematikus vizsgálta o˝ ket el˝oször a múlt század közepén.) Hány lakosú városban lehet Steiner-rendszert alkotó klubokat csinálni? Ismét az (1) és (2) egyenl˝oségekhez fordulunk segítségül, csak beírjuk a k = 3 és λ = 1 feltételeket. Kapjuk 3b = vr 2r = v − 1. Innen: v−1 2 v(v − 1) b= . 6 r=

(3) (4)

Nézzük most, milyen maradékot adhat v, ha 6-tal osztjuk, és azt akarjuk, hogy r és b egész szám legyen? Elo˝ ször is (3) mutatja, hogy v-nek páratlannak kell lennie, tehát 6-tal osztva csak 1-et, 3-at vagy 5-öt adhat maradékul. Ezt úgy is kifejezhetjük, hogy v csak 6 j + 1, 6 j + 3 vagy 6 j + 5 alakban írható szám lehet, ahol j valamilyen nem negatív egész szám. De 6 j + 5 alakú sem lehet, mert akkor (4) szerint b=

(6 j + 5)(6 j + 4) 1 = 6 j2 + 9 j + 3 + , 6 3

tehát nem egész szám. Így v csak 6 j + 1, vagy 6 j + 3 alakú lehet, más szóval csak olyan városokban lehet Steiner-rendszert alkotó klubokat alakítani, ahol a lakosok száma 6-tal osztva 1-et vagy 3-at ad maradékul. Tehát v = 3, 7, 9, 13, 15, 19, 21 stb. esetén. (Ezekre viszont valóban lehet is, amit azonban itt nem bizonyítunk.) v = 3 esetén

110

4. Blokkrendszerek

nagyon könny˝u a dolog: összesen 1 klub van, 3 taggal. A v = 7 esetre jó blokkrendszert már az el˝obb láttuk. 2. feladat v = 9 esetén, tehát 9 lakosú „városban” alakítsunk olyan klubokat, amelyek Steiner-rendszert alkotnak! 5. Most pedig képzeljük el a következo˝ t: Egy tanárnak 9 leánytanulóból álló csoportja van. Mindennap sétálni viszi o˝ ket, méghozzá hármas sorokban sétálnak. (Tehát 3 db hármas sor van összesen.) Ráadásul úgy akarja o˝ ket sétáltatni egymás után több napon, hogy végül is minden leány elmondhassa, hogy minden, társával pontosan egyszer sétált egy sorban. 3. feladat Ahhoz, hogy ez egyáltalán lehetséges legyen, hány napon át kell sétálniuk? Ha már megoldottátok a 3. feladatot, akkor tudjátok, hogy hány napon át kell sétálni. De nem biztos még, hogy valóban lehet így sétálni. Nézzük meg azonban a 2. feladat megoldását! Hiszen ez éppen az, amit kerestünk! Ha megnézitek, egy-egy sorban van az aznapi „sétarend”. Például a harmadik napon az egyik sorban az 1., 5. és 9. kislány, a másik sorban a 2., 6. és 7., a harmadik sorban pedig a 3., 4. és 8. kislány sétál. Ugyanezt a problémát 9 leány helyett 15-tel egy Kirkman nev˝u német matematikus vetette fel. (Akkor persze 7 napon át kell sétálniuk a leányoknak hármas sorokban.) A 15 iskolás leányról szóló Kirkman-féle problémát nagyon sokáig nem tudták megoldani a matematikusok. Ma már ismert a megoldás, és persze, ha a helyes sétarend már egyszer megvan, akkor nem nehéz ellen o˝ rizni, hogy az valóban helyes-e. A megfelel˝o „sétarend” létezését 9 és 15 helyett általánosságban minden 6 j + 3 alakú v számra csak 1969-ben sikerült bebizonyítania egy Ray-Chaudhuri nev˝u indiai matematikusnak. A feladat nehézségét jobban látjuk, ha észrevesszük, hogy egy ilyen „sétarend” egyúttal Steiner-rendszer is, tehát Ray-Chaudhuri tételéb˝ol következik 6 j + 3 elem˝u Steiner-rendszer létezése is, és ezt már önmagában is elég nehéz bebizonyítani.

4. Blokkrendszerek

111

6. Foglalkozzunk most egy kicsit behatóbban Steiner-rendszerekkel! Képzeljük el, hogy a v lakosú városka lakói között, akik Steiner-rendszert alkotó klubokba vannak szervezve, elégedetlenség üti fel a fejét. Például sokallják a tagdíjat. Ezért egy szervezetet hoznak létre, melynek tagjai a városlakók közül kerülnek ki, és ennek a szervezetnek a célja tiltakozni a magas tagdíjak ellen. Ahhoz azonban, hogy a tiltakozás eljusson minden klubba, az kell, hogy minden klubban legyen legalább egy tagja a szervezetnek. Ezek után az a kérdés, hogy legalább hány tagja van egy ilyen szervezetnek, aminek minden klubban van legalább egy képvisel˝oje? Nézzünk egy olyan városlakót, aki nem tagja ennek a szervezetnek! Nevezzük o˝ t Andrásnak! András r klubnak tagja, és Steiner-rendszer esetén r=

v−1 2

(lásd a (3) egyenl˝oséget). Mindegyik klubnak Andráson kívül még két tagja van, és mivel András minden másik városlakóval közösen csak egy klubnak a tagja, azért a (v − 1)/2 klub közül bármely ketto˝ nek csak egy közös tagja van éppen András. De mindegyik klubban kell a szervezet egy-egy tagjának lennie, és ez mindig egy Andrástól különböz˝o ember (hiszen András nem tagja a szervezetnek). Ez pedig azt jelenti, hogy a szervezetnek legalább (v − 1)/2 tagja van (hiszen jut bel˝olük a (v − 1)/2 klub mindegyikébe egy-egy). Mi van akkor, ha tényleg sikerült létrehozni egy (v − 1)/2 tagú szervezetet, amelynek van képviselete minden klubban? Az eredmény elég meglep˝o: akkor ez a szervezet maga is egy Steinerrendszer! Ezalatt pontosan a következo˝ t értjük: Nézzük ezt a v1 = (v − 1)/2 városlakót, aki a szervezethez tartozik, és csak azokat a klubokat nézzük, amelyeknek mindhárom tagja a szervezethez tartozik. Akkor ez a v1 elem és rajta ezek a meghagyott klubok egy Steiner-rendszert alkotnak. Ehhez elég azt belátni (lásd a 4. feladatot), hogy a v1 ember közül bármely kett˝o pontosan egy klubnak a tagja közösen. Nyil-

112

4. Blokkrendszerek

ván legfeljebb egynek, mert már a régi klubok közül is csak egynek voltak közösen a tagjai. Hogy egynek tényleg tagjai, ehhez azt kell belátni, hogy a régi közös klubjukat meghagytuk, tehát, hogy ennek harmadik a tagja is hozzátartozik a szervezethez. Tegyük fel, hogy nem így lenne. Akkor nevezzük ezt a harmadik, a szervezethez nem tartozó klubtagot Bélának. Ugyanúgy okoskodhatunk, mint fent: Béla (v − 1)/2 klubnak tagja, és ezeknek a kluboknak Bélán kívül nincs közös tagja. Mindegyik klubban van legalább egy tagja a szervezetnek. Csakhogy az egyikben – éppen abban a klubban, amelyikbo˝ l kiindultunk – két tagja is van! A többiben meg legalább egy-egy: ez összesen legalább (v + 1)/2 ember. De a szervezetnek csak (v − 1)/2 tagja van. Ellentmondásra jutottunk, tehát nem lehet, hogy Béla ne tartozzon hozzá a szervezethez. Ezzel pedig beláttuk, hogy a szervezet v1 = (v − 1)/2 tagja és a tisztán bel˝olük álló klubok tényleg egy Steiner-rendszert alkotnak. 4. feladat Bizonyítsuk be, hogy ha van egy v elem˝u halmazunk, ennek ki vannak választva bizonyos k elem˝u részhalmazai, úgy, hogy minden pár pontosan λ db-ban van benne, akkor ezek a k-asok biztosan blokkrendszert alkotnak. Tehát nem kell ellen˝orizni, hogy minden elem ugyanannyi blokkban van-e benne, mert a fenti állításokból szükségszer˝uen következik, hogy minden elem λ(v − 1)/(k − 1) blokkban van benne. (Útmutatás: Azt az utat próbáljátok végigjárni, amelyen a (2) egyenl˝oséghez jutottunk, csak éppen fordított irányban.) 5. feladat Tegyük fel, hogy van egy Steiner-rendszerünk v elemen, és ezen v elem közül ki tudunk választani (v − 1)/2-t úgy, hogy az eredeti Steiner-rendszer hármasai közül azok, amelyeknek mindhárom eleme ezen (v − 1)/2 elem közül kerül ki, egy Steiner-rendszert alkotnak ezen a (v − 1)/2 elemen. Bizonyítsuk be, hogy akkor ez a (v − 1)/2 elem jó szervezet lesz (tehát az eredeti Steiner-rendszer minden hármasa tartalmazza ezen (v−1)/2 elem egyikét). (Elnevezés: A Steiner-rendszer v pontja közül bizonyosakból álló halmazt, amelynek megvan az a tulajdonsága, hogy minden

4. Blokkrendszerek

113

hármasnak legalább egyik pontja ehhez a halmazhoz tartozik, lefogó pontrendszernek fogjuk nevezni. Fentebb tehát azt láttuk be, hogy egy lefogó pontrendszernek legalább (v − 1)/2 eleme van, és ha pont ennyi van, akkor maga is egy Steiner-rendszert alkot.) 7. Képzeljük el most, hogy v elemen („ponton”) van egy Steiner-rendszerünk, és ki akarjuk színezni a pontokat úgy, hogy semelyik blokk (klub, hármas) ne álljon csupa egyszín˝u pontból. Ezt egy színnel nyilván nem lehet megcsinálni, mert akkor minden blokk egyszín˝u lesz. De még két színnel sem lehet megcsinálni. Tegyük fel ugyanis, hogy sikerült a pontokat két színnel, mondjuk kékkel és pirossal úgy kiszínezni, hogy minden hármas tartalmaz kék és piros pontokat is. Akkor mind a kék, mind a piros pontok lefogó pontrendszert alkotnak, tehát mindegyikb˝ol legalább (v − 1)/2 van. Ez együtt v − 1 pont, és van még egy, ez vagy kék, vagy piros (mondjuk piros). Akkor a (v − 1)/2 db kék pont egy lefogó pontrendszert alkot, tehát egy Steinerrendszert is, mint azt már korábban beláttuk. De akkor az ehhez a kis Steiner-rendszerhez tartozó mindegyik hármas csupa kék pontot tartalmaz, holott feltettük, hogy nincs egyszín˝u hármas. Beláttuk tehát, hogy minden Steiner-rendszer színezéséhez legalább három szín szükséges. 6. feladat Lássátok be, hogy az 1. ábrán szerepl˝o, ill. a 2. feladatban definiált Steiner-rendszerek mindegyike kiszínezhet˝o három színnel. 8. Vizsgáljunk ismét általánosságban blokkrendszereket, melyeket az öt paraméter: b, v, r, k, λ jellemez. Egy blokkrendszert kapunk akkor, ha feltesszük, hogy egyetlen blokk van, melyhez a v elem˝u halmaz minden eleme hozzátartozik. Tehát b = 1, r = 1, k = v és λ = 1. Úgy is fogalmazhatunk, hogy a városban egyetlen klub m˝uködik, amelynek mindenki tagja. Zárjuk ki ezt az esetet! Tegyük fel tehát, hogy k < v! Ezen feltétel mellett igaz az alábbi (itt nem bizonyítandó) úgynevezett Fisher-egyenl˝otlenség: b=v

(5)

114

4. Blokkrendszerek

(tehát legalább annyi klub van, mint városlakó). 7. feladat Egy v lakosú városban (v = 3) létesítünk blokkrendszert alkotó klubokat úgy, hogy a klubok száma megegyezzen a városlakók számával (azaz b = v legyen)! (A triviális esetek kizárására most és a kés˝obbiekben is megköveteljük, hogy 1 < k < v teljesüljön.) A Fisher-féle egyenl˝otlenség gyakran igen jó szolgálatot tesz. Képzeljük el, hogy minden klubnak van egy jelvénye. Egy városi ünnepségen a város minden lakója megjelenik, és mindenkinek hordania kell valamelyik klubjának a jelvényét. Meg tudják-e csinálni azt, hogy semelyik két emberen ne legyen ugyanaz a jelvény? Aki elgondolkodik ezen a feladaton, észreveheti, hogy nagyon sok köze van a harmadik fejezetben megismert König-tételhez. Blokkrendszerünkb˝ol (azaz a városi klubokból) ugyanis könnyen csinálhatunk egy páros gráfot, ahogy azt a 2. ábra mutatja. Az alul lev˝o pontok jelölik a városlakókat, a felül levo˝ k a klubokat. Azt, hogy például az A nev˝u városlakó tagja az X nev˝u klubnak, úgy szemléltethetjük, hogy az A és X pontokat a gráfban egy él köti össze. A 2. ábra nem teljes, mert csak egy élt húztunk be, példaképpen. Tudjuk, hogy a valóságban A-ból (és minden alsó pontból) r db él indul ki, X-be (és minden felso˝ pontba) pedig k db él fut be. Alul v db pont van, felül pedig b db pont. Ha kiválasztunk n db alsó pontot (n 5 v), tudjuk, hogy belo˝ lük összesen nr db él indul ki. Az ezen élek fels˝o végpontjaiként el˝oálló pontok számát

klubok

városlakók 2. ábra.

4. Blokkrendszerek

115

jelölje m. Mindegyikbe k db él megy be, összesen tehát mk db. Ezek között szerepel a fent említett nr db él is. Tehát nr 5 mk

(6a)

(1) szerint bk = vr, és tudjuk, hogy b = v (Fisher-egyenlo˝ tlenség), azért k 5 r. Tehát mk 5 mr.

(6b)

(6a)-t és (6b)-t összevetve: nr 5 mr, és ezért

n 5 m.

Tehát minden n db alsó pont legalább n db felso˝ ponttal van összekötve. Akkor pedig alkalmazhatjuk König tételét (lásd a 8. feladatot!), és így bebizonyítottuk, hogy a blokkrendszerb o˝ l készített gráfban van v db él, amelyek mindegyike más-más alsó pontból indul ki, és a fels˝o végpontjaik is mind különbözo˝ ek. Azaz az alsó A1 , A2 , . . . , Av pontokhoz léteznek olyan csupa különböz˝o fels˝o X1 , X2 , . . . , Xv pontok (klubok), hogy pl. A1 X1 -gyel, A2 X2 -vel, . . . , Av Xv -vel össze van kötve. Tehát A1 tagja az X1 klubnak, A2 az X2 klubnak, . . . , Av az Xv klubnak. Akkor pedig a keresett megoldás az, hogy az ünnepségen hordja A1 az X1 klub jelvényét, A2 az X2 klubét, . . . , Av pedig az Xv klubét. 8. feladat Az az állítás, amit itt (König-tétel néven) felhasználunk, a következ˝o: „Ha van egy páros gráf, alul v pont, felül b pont, és minden n db alsó ponthoz (n 5 v) a valamelyikkel összekötött fels˝o pontok száma legalább n, akkor van a gráfban v db él, amelyek mindegyike más-más alsó pontból indul ki, és a fels˝o végpontjaik is mind különböz˝oek.” Hogyan tudnád ezt az állítást bebizonyítani, felhasználva a harmadik fejezetben szerepl˝o König-tételt? (Az ott szerepl˝o König-tétel az itteninek speciális eseteként adódik, ha v = b.)

116

4. Blokkrendszerek

9. Hallottatok már latin négyzetekro˝ l? Ez tulajdonképpen nagyon egyszer˝u fogalom: pl. 4-szer 4-es latin négyzetet úgy kapunk, hogy egy 4 × 4-es sakktábla minden mezejére elhelyezzük az 1-t˝ol 4-ig terjed˝o számok valamelyikét, méghozzá úgy, hogy ugyanaz a szám semelyik oszlopban és semelyik sorban se szerepeljen kétszer. 9. feladat Csináljatok 4 × 4-es latin négyzetet!

10. feladat Hány különböz˝o 4 × 4-es latin négyzet van? Hány van akkor, ha nem tekintünk különböz˝onek két olyat, amelyek egyike úgy áll el˝o a másikból, hogy vesszük az 1, 2, 3, 4 számok egy tetsz˝oleges permutációját (pl. 2134), és az egyik latin négyzetben mindenütt, ahol a k szám áll (1 5 k 5 4), a k szám helyére az alapul vett permutáció k-adik helyén álló számot írjuk? (Például 2134-et alapul véve, a 9. feladat megoldásánál szerepl˝o ábrán látható latin négyzetb˝ol a 3. ábrán bemutatott helyzetet kapjuk.) Nevezzünk két latin négyzetet nem lényegesen különböz˝onek, ha ilyen átalakítással átvihet˝ok egymásba! Ha pedig nem vihet˝ok át így egymásba, nevezzük o˝ ket lényegesen különböz˝oknek! Ha már megvan a különböz˝o 4 × 4-es latin négyzetek száma, meg tudnád-e rögtön adni a lényegesen különböz˝o latin négyzetek számát? Tekintsük most az alábbi két 4 × 4-es latin négyzetet (4. és 5. ábra)! Ha most ezt a két latin négyzetet „egymásra tesszük”, azaz a 4 × 4-es sakktábla minden mezejébe egy számpárt írunk be: elso˝ eleme az a szám, amely a 4. ábra latin négyzetében az illeto˝ mez˝on áll, második eleme pedig az a szám, amely az 5. ábra latin négyzetében áll az illet˝o mez˝on (6. ábra), mit látunk? Azt, hogy

2 4 3 1

1 2 4 3

3 1 2 4

4 3 1 2

3. ábra.

1 2 4 3

2 1 3 4

3 4 2 1

4 3 1 2

4. ábra.

1 4 3 2

2 3 4 1

3 2 1 4

4 1 2 3

5. ábra.

4. Blokkrendszerek

(1,1)

117

(2,2) (3,3) (4,4)

(2,4) (1,3)

(4,2) (3,1)

(4,3) (3,4) (2,1) (1,2) (3,2) (4,1) (1,4) (2,3) 6. ábra. semelyik két mez˝oben nem áll ugyanaz a számpár. Ez persze azt is jelenti, hogy minden számpár el˝ofordul egyszer, hiszen a sakktábla mez˝oib˝ol és a lehetséges számpárokból egyaránt 42 = 16 db van. Ha tehát semelyik számpár nem fordul elo˝ kétszer, akkor mindegyiknek el˝o kell egyszer fordulnia. (Skatulyaelv!) Két latin négyzetet, amelyek rendelkeznek ezzel a tulajdonsággal, ortogonálisnak nevezünk. (Azt is mondjuk néha, hogy az egyik ortogonális a másikra.) Az ortogonalitást így is elleno˝ rizhetjük: Megnézzük a 4. latin négyzet azon mezo˝ it, ahol 1-es áll. Ezek sakknyelven szólva az a4, b3, c1, d2 mezo˝ k. Ezután megnézzük ugyanezeket a mez˝oket az 5. latin négyzeten. Majd ugyanígy járunk el azon mez˝okkel, amelyeken a 2-es, 3-as, ill. 4-es szám áll a 4. latin négyzetben. Ha az 5. latin négyzet mindezeket a próbákat kiállja, akkor tényleg ortogonális a 4. latin négyzetre. (Gondoljátok meg, hogy ez miért van így!) 10. Két ortogonális latin négyzetbo˝ l könnyen csinálható egy b˝uvös négyzet. Nem kell mást tennünk, mint megnézni a 6. ábrán látható párokat. Írjunk el˝oször is mindenhova 4 helyére 0-t (ekkor például a jobb fels˝o sarokban (0, 0) lesz). Ezután pedig minden mez˝on képzeljük beírva az (a, b) pár helyett az ab 4-es számrendszerbeli számot. (Tudjuk, hogy a 4-es számrendszerben ab = 4a + b.) Így a 7. ábrán látható táblázatot kapjuk. Ennek min-

118

4. Blokkrendszerek

5

10 15

8

7

2

13

3

12

9

6

14

1

4

11

0

7. ábra. den sorában és minden oszlopában 30 az elemek összege, így nevezhetjük b˝uvös négyzetnek. Bármely két ortogonális latin négyzetb˝ol ily módon egy b˝uvös négyzetet kapunk, ugyanis minden sorban az egyesek és a „négyesek” helyén is pontosan egyszer szerepel a 0, 1, 2, 3 számok mindegyike, így akármelyik sorban, illetve oszlopban (0 + 1 + 2 + 3) · 4 + (0 + 1 + 2 + 3) = 30 lesz az elemek összege. 11. feladat B˝uvös négyzetünkben 0-tól 15-ig szerepelnek a számok, nem pedig 1-t˝ol 16-ig, mint szokásos. Tudnátok-e a 7. ábrán látható b˝uvös négyzetb˝ol olyat csinálni, amiben 1-t˝ol 16-ig szerepelnek a számok? 12. feladat Az általunk nyert b˝uvös négyzet nem „igazi” b˝uvös négyzet, mert az átlóösszegek különböznek a sor-, ill. oszlopöszszegekt˝ol. Milyen ortogonális latin négyzetekb˝ol lehetne „igazi” b˝uvös négyzetet csinálni? 11. A kérdés most ez: van-e olyan 4 × 4-es latinnégyzet, ami ortogonális a 4. és 5. latin négyzetek mindegyikére? Van. (Mielo˝ tt szemügyre vennétek a 8. ábrát, próbáljatok ti magatok ilyen latin négyzetet csinálni!) 13. feladat Bizonyítsátok be, hogy nincs olyan 4 × 4-es latin négyzet, ami a 4., 5. és 8. latin négyzetek mindegyikére ortogonális lenne! 14. feladat Nézzétek a 9. ábra latin négyzetét! Ugye majdnem ugyanaz, mint a 8. ábrán látható latin négyzet? Mégis, bizonyít-

4. Blokkrendszerek

1 3 2 4

2 4 1 3

3 1 4 2

1 2 3 4

4 2 3 1

8. ábra.

2 4 1 3

3 1 4 2

119

4 3 2 1

9. ábra.

sátok be (lehet˝oleg kevés próbálgatással), hogy nincs olyan 4×4es latin négyzet, ami ortogonális a 9. ábra latin négyzetére (holott a 8. ábra latin négyzetére két másik 4 × 4-es latin négyzet is ortogonális). Érdekes megfigyelni, hogy a 4., 5. és 8. latin négyzetek ugyanazokból: a sorokból állnak, csak más-más sorrendben. 12. Most ebb˝ol a három, páronként ortogonális latin négyzetb˝ol egy blokkrendszert csinálunk. El˝oször egy 5×16-os sémát csinálunk, ami a 10. ábrán látható, Ennek els˝o két sora könnyen kitalálható szabály szerint jött létre, a 3. sort a 4. latin négyzetb˝ol kaptuk úgy, hogy egymás után lemásoltuk a sorait folytatólagosan. A 4., ill. 5. sor ugyanígy jött létre a 8., ill. 5. latin négyzetb˝ol. Blokkrendszerünk 42 + 4 + 1 = 21 pontból fog állni. 42 = 16 pontot P bet˝uvel jelölünk: P1 , . . . , P16 . További 4 + 1 = 5 pontot Q bet˝uvel: Q1 , . . . , Q5 . A blokkok 4 + 1 = 5 elemb˝ol fognak állni. Számuk 4(4 + 1) + 1 = 21 lesz. Az egyik blokk álljon az alábbi 5 pontból: Q1 , Q2 , . . . , Q5 . A további blokkokat Li j -vel jelöljük, ahol 1 5 i 5 4 és 1 5 j 5 5. Az Li j blokk az alábbi pontokból áll: Q j , továbbá Pi1 , Pi2 , Pi3 , 1 1 1 1 1

1 2 2 2 2

1 3 3 3 3

1 4 4 4 4

2 1 2 3 4

2 2 1 4 3

2 3 4 1 2

2 4 3 2 1

3 1 4 2 3

3 2 3 1 4

10. ábra.

3 3 2 4 1

3 4 1 3 2

4 1 3 4 2

4 2 4 3 1

4 3 1 2 4

4 4 2 1 3

120

4. Blokkrendszerek

Pi4 , ahol az i1 , i2 , i3 , i4 számok így vannak definiálva: megnézzük, hogy a 10. ábrán a j-edik sorban hányadik helyeken áll az i szám. A válasz: az i1 -edik, i2 -edik, i3 -adik és i4 -edik helyeken; ez az i1 , i2 , i3 , i4 számok definíciója. Ha az egységes jelölés kedvéért a P1 , P2 , . . . , P16 pontokat rendre az 1, 2, . . . , 16 számokkal jelöljük, Q1 , Q2 , Q3 , Q4 , Q5 -öt pedig 17, 18, 19, 20, 21-gyel, akkor a blokkrendszer az alábbi blokkokból áll (egy-egy blokk elemei az egy oszlopban álló számok): 17 18 19 20 21

1 2 3 4 17

5 6 7 8 17

9 10 11 12 17

13 14 15 16 17

1 5 9 13 18

2 6 10 14 18

3 7 11 15 18

4 8 12 16 18

1 6 12 15 19

2 5 11 16 19

3 8 10 13 19

4 7 9 14 19

1 7 10 16 20

2 8 9 15 20

3 5 12 14 20

4 6 11 13 20

1 8 11 14 21

2 7 12 13 21

3 6 9 16 21

4 5 10 15 21

11. ábra. Ellen˝orizhetjük, hogy így tényleg egy blokkrendszert kaptunk. Ebben a blokkrendszerben b = v = 42 + 4 + 1 = 21, r = k = 4 + 1 = 5, λ = 1. Az ilyen blokkrendszereket, amikben λ = 1 és b = v (és v > 3), véges projektív síknak nevezik (az elnevezés oka az, hogy nagyon sok közös tulajdonsága van a projektív geometriában vizsgált projektív síkkal). Véges projektív síkban a blokkokat általában egyeneseknek nevezik. Ezeknek az „egyeneseknek” megvan az alábbi két tulajdonságuk: 1. Bármely 2 ponton át egy és csak egy egyenes halad (hiszen λ = 1). (Figyeljük meg, hogy a közönséges geometriai értelemben vett egyeneseknek és pontoknak is megvan ez a tulajdonsága!) 2. Bármely két egyenesnek egy és csak egy közös pontja van (ezt itt nem bizonyítjuk). Véges projektív sík az 1. ábrán látható blokkrendszer is, so˝ t ez a legegyszer˝ubb lehetséges véges projektív sík. Be lehet bizonyítani, hogy minden véges projektív síkhoz van egy olyan a természetes szám (n = 2), hogy

4. Blokkrendszerek

b = v = n2 + n + 1,

r = k = n + 1,

121

λ = 1.

n-et az illet˝o véges projektív sík rendjének szokták nevezni. Az 1. ábrán látható véges projektív sík rendje 2, az imént konstruált véges projektív sík rendje 4. Mindmáig csak olyan véges projektív síkokat találtak, amiknek prímhatvány a rendje, de senki sem tudta bebizonyítani, hogy másféle véges projektív sík nem létezik. 15. feladat Keressetek két ortogonális 3 × 3-as latin négyzetet!

16. feladat Készítsetek bel˝olük a fenti eljárás mintájára egy harmadrend˝u véges projektív síkot! 17. feladat Vegyétek az

1 2 2 1

2 × 2-es latin négyzetet, és készítsetek bel˝ole másodrend˝u véges projektív síkot! Lássátok be, hogy ez a pontok számozásától eltekintve megegyezik az 1. ábrán látható véges projektív síkkal! 18. feladat Keressetek 3 olyan 4 × 4-es ortogonális latin négyzetet, amelyek lényegesen különböznek a 4., 5. és 8. latin négyzetekt˝ol! Készítsetek a segítségükkel negyedrend˝u véges projektív síkot!

Megoldások

1. Számoljuk össze! 1. . . . , azaz hányféleképpen lehet 7 gyereket 7 székre leültetni? A megel˝oz˝o gondolatmenetet még egyszer megismételve kapjuk, hogy ez a szám 7 · 720 = 5040. 90 · 89 2. = 4005. 2 3. Ha a 90 ember közti kézfogásokat számolnánk össze, akkor ugyanazt kapnánk, mint az elo˝ z˝o feladatban. Ez nem véletlen, mert mindkét esetben azt számítjuk ki, hogy hány pár alkotható 90 dologból. 4.

10 · 16 = 160; 10 000 · 20 000 = 200 000 000.

8. Az a halmaz, melynek egyik eleme Andrea, másik eleme pedig az a halmaz, amelynek egyetlen elme van: az 1 szám. 9. Nem, mert különbséget kell tenni az egyelem˝u halmaz és ennek (egyetlen) eleme között, hiszen az utóbbi nem is halmaz. 10. 8 részhalmazt kellett találnotok összesen. Ne feledkezzetek meg az üres halmazról és magáról a {0, 1, 2} halmazról!

124

Megoldások

12. A legkevesebb elem˝u ilyen halmaz a {0, 1, 3, 4, 5} halmaz.

13. Tetsz˝oleges sok halmaz egyesítése azokból az elemekbo˝ l áll, melyek legalább egyikükhöz hozzá tartoznak. 14. A legkevesebb elem˝u halmaz, melynek mindketto˝ részhalmaza, a két halmaz egyesítése. 15. Az egyesítés elemszáma legalább 9 és legfeljebb 14. 16. Az egyesítés elemszáma legalább m és legfeljebb m + n. 17. Az {1, 3} halmaz. 18. Az üres halmaz.

19. Az a halmaz, melynek egyetlen eleme a 2 szám. 20. Legfeljebb annyi, mint m és n közül a kisebbik. 21. Vegyük azokat az elemeket, melyek az m elem˝u halmazban benne vannak, de a másikban nem. Ezek száma m − q. Ezekhez hozzávéve a másik halmaz elemeit, számszerint n-et, megkapjuk a két halmaz egyesítését. Tehát p = (m−q)+n. Mindkét oldalhoz q-t adva kapjuk az állítást. 22. „Társaságunk” 7 darab 3 elem˝u halmaz egyesítése, melyek közül bármely kett˝onek a metszete üres halmaz, így társaságunk elemszáma 7 · 3 = 21. 23. Az üres halmaznak egyetlen részhalmaza van, önmaga. Ennek alapján 20 számon 1-et érdemes érteni. (Ez az értelmezés minden más szempontból is helytálló.) 24. Ha n = 1, akkor mindkét oldalon 1 áll. Feltéve, hogy n-re tudjuk az állítást, az els˝o n + 1 szám összege: n(n + 1) +n+1= 2 n2 + n + 2n + 2 n2 + 3n + 2 (n + 1)(n + 2) = = = . 2 2 2 Ez pedig ugyanaz, mint a bizonyítandó képlet, ha benne n helyett (n + 1)-et írunk. 1 + 2 + · · · + n + (n + 1) =

Megoldások

125

25. Ha n = 1, mindkét oldalon 1 áll. Feltéve, hogy n-re igaz az egyenl˝oség, n(n + 1)(2n + 1) + (n + 1)2 = 6 2n2 + n + 6n + 6 2n2 + 7n + 6 = (n + 1) = (n + 1) · = 6 6 (n + 1)(n + 2)(2n + 3) . = 6 Ez pedig ugyanaz, mint a bizonyítandó képlet, ha benne n helyett (n + 1)-et írunk. 12 + 22 + · · · + n2 + (n + 1)2 =

26. n = 1 esetén 2-t kapunk, s ez páros. n − 1-re úgy kapjuk a kifejezést, hogy n(n+1)-hez 2(n+1)-et adunk, tehát páros számot; feltéve, hogy n(n + 1) páros volt, az összeg is páros. Két egymás utáni természetes szám közül az egyik páros szám, tehát a szorzat mindenképpen páros lesz. 27. 10n az els˝o n + 1 jegy˝u szám, ezért 10n. Hasonlóan pn . 29. 4 · 3 · 2 = 24.

30. A 13 + 1 helyet kell kitölteni, tehát 314 .

31. Piros és fehér kocka esetén az eredmények száma 6 · 6 = 36. Egyforma kockák esetén: Ha a két kockán ugyanazt a számot kapjuk, akkor mindegy, hogy meg tudjuk-e különböztetni. o˝ ket vagy sem. Ilyen eset van 6. A többi 30 esetet azonban párosával egyformának látjuk, mert nem tudjuk megkülönböztetni, hogy melyik kockán jött ki az egyik, melyiken a másik szám. Ilyenkor tehát ez csak 15 esetet jelent. Végeredményben most 21-et kapunk. 32. Minden ajándéktárgyra ráírjuk, hogy ki kapja. Így a 12 névb˝ol alkotható 20 elem˝u sorozatokat kapjuk meg. Az eredmény tehát 1220 . 33. Egy számötös, melyet az elso˝ 90 számból alkottunk, kétféle
– lehet: vagy nem tartalmazza a 90-es számot – ilyen van 89 5 89
vagy tartalmazza – ilyen van 4 .

126

Megoldások

34. Az n elem˝u halmazok egy k elem˝u részhalmazát úgy is kiválaszthatjuk, hogy elvesszük a többi n − k elemet; ezt pedig éppen n
-féleképpen tehetjük meg. n−k

35. Az összes részhalmazok száma az „üres részhalmazok száma” – vagyis 1 – plusz az egyelem˝u részhalmazok száma, plusz a kételem˝u részhalmazok száma, . . . , plusz az n elem˝u részhalmazok száma (természetesen a legutolsó az 1).
36. n elemb˝ol n1 -et nn1 -féleképpen választhatunk ki. Akárho
1 gyan is tettük ezt meg, n−n lehet˝oség van az n2 elem kin2 választására, tehát az n és az n elem együttes kiválasztására 1 2
n−n
n 1 · lehet˝ o ség van. Hasonlóan menve tovább, a végeredn1 n2 mény:       n n − n1 n − n 1 − n2 · · ··· = n1 n2 n3 (n − n1)! (n − n1 − n2)! n! · · ··· = = (n − n1)!n1 ! n2 !(n − n1 − n2 )! ... n! = n1 !n2 ! · · · nk ! Itt a lehetséges egyszer˝usítéseket elvégezve, ugyanazt kapjuk, mint fentebb. 37. a) n elem sorbarakásainak (permutációinak) számát, n!-t. b) n elemb˝ol alkotható k elem˝u sorozatok számát: n · (n − 1) · · ·(n − k + 1); c) n elem k elem˝u részhalmazainak számát, vagyis

n k




.

38. Az els˝o oszlopba 8 helyre lehet, ezután a másodikba már csak 7-re és így tovább, tehát a leheto˝ ségek száma 8!. 39. El˝oször eldöntjük, hogy hova helyezzük el a bástyákat, ezt 8!-féleképpen tehetjük meg, utána eldöntjük, hogy melyik az a

Megoldások

négy hely, ahova a piros bástyákat tesszük, ez
het˝o. Az összes lehet˝oségek száma: 8! · 84 .

127

8
4 -féleképpen te-

40. Az el˝oz˝ohöz hasonlóan 8! · 8!.

41. Minden bet˝u „választ magának” helyet, hogy hová kerül az anagrammában. M, B, N, T, R egy-egy helyet választanak, K, O, I, A kett˝ot-kett˝ot, tehát a 10. pont eredménye szerint a leheto˝ ségek száma: 13! 13! = = 389 188 800. 1! · 1! · 1! · 1! · 1! · 2! · 2! · 2! · 2! 16 42. Az összes 13 bet˝us szövegek száma, azaz a 35 bet˝ub o˝ l alkotható 13 elem˝u sorozatok száma a 8. pont szerint 3513. Ha most a lényegesen különböz˝o anagrammafeladatokat akarjuk felsorolni, legcélszer˝ubb, ha úgy tesszük, hogy minden bet˝uhöz megmondjuk, hányszor forduljon el˝o. Azaz 13 helyet
kell szétosztanunk 34 46
bet˝u között. Ez a 12. pont szerint 34+13−1 = -féle lehet˝ o sé34−1 33 get kapunk. 43. El˝oször minden gyereknek adunk egy-egy forintot, majd a maradék n − k forintot úgy osztjuk szét, hogy mindegyikük kapjon legalább még 1 forintot. Csak az utóbbit lehet többfélekép
pen megtenni, és mint tudjuk, éppen n−k−1 -féleképpen. Álk−1 talánosítás: n forintot k gyerek között osztunk szét úgy, hogy mindegyik legalább p forintot kapjon. Az elo˝ z˝oekhez hasonlóan n−(p−1)k−1
kiosztási lehet˝oség adódik. k−1 44. A játék
végén végeredményben k · p pengo˝ t osztanak szét; ez kp+k−1 -féleképpen tehet˝o meg. k−1 45. Odaadunk minden lánynak egy-egy forintot, a maradék pénzt pedig szétosztjuk az „igazságtalanabb” módon. Az eredmény így 

   (n − l) + (k + l) − 1 n+k−1 = (k + l) − 1 k+l−1

128

Megoldások

2. Kombinatorika a számtanban 1.

n
n

Az n-edik sorban, a két szélso˝ elem: n! = n!0! = 1.

n
0

és

n
n .

De

n
0

=

2. Azt kell belátni, hogy minden sorban a balról (k + 1)-edik
elem
ugyanaz, mint a jobbról (k + 1)-edik, tehát, hogy nk = n oz˝o fejezet 34. feladatát! n−k . Ehhez viszont lásd az el˝

3. Tegyük rá a 3. ábra alakzatát egy
Pascal-háromszögre (tehát pl. a balról harmadik N bet˝u az 52 helyére kerül, a balról máso
dik R bet˝u a 94 helyére). Hányféleképpen érhetünk el pl. az M bet˝ukhöz? A két széls˝ohöz egyféleképpen, a középso˝ höz kétféleképpen. És a Pascal-háromszög megfelelo˝ sora is éppen 1 2 1. Általában is, minden elemhez annyiféleképpen érhetünk el felülr o˝ l lefelé, amennyi a Pascal-háromszögben az o˝ helyén áll. Ezt teljes indukcióval bizonyíthatjuk be: ha már az n-edik sor elemeire beláttuk, akkor az (n + 1)-edik sor bármely eleméhez annyiféleképpen juthatunk el, ahányféleképpen a to˝ le balra fent lev˝o elemhez eljuthatunk + ahányféleképpen a to˝ le jobbra fent lev˝o elemhez eljuthatunk. Tehát az (n + 1)-edik sor elemeihez is annyiféleképpen juthatunk el, amennyi a Pascal-háromszög megfelelo˝ helyén
áll. Speciálisan a legalsó A bet˝uhöz 12 -féleképpen juthatunk el, 6
12 azaz a lehetséges leolvasások száma: 6 = 924. 4. A kezd˝o 1-es helyett vegyük a t˝ole jobbra lefelé álló 1-est, és használjuk fel többször egymás után a (2) egyenlo˝ séget! 5. A binomiális tétel szerint:           n n n n n − + − ± · · · + (−1)n = (1 − 1)n = 0. 0 1 2 3 n

Ha
n páratlan, akkor az állítás abból is következik, hogy egyrészt n n
n
n
= , másrészt és o el˝ojellel szerepelk n−k k n−k ellenkez˝ nek.

6. (1 + x)n+m = (1 + x)n (1 + x)m -ben vizsgáljátok xk együtthatóját! A „golyós” módszer is alkalmazható, n + m golyóval, amelyek közül k db választandó ki.

Megoldások

129



7. El˝oször azt bizonyítsátok be, hogy nk = nk n−1 k−1 . Utána pedig alkalmazzátok a (4) egyenl˝oséget (de n helyett (n − 1)-re)! 8.

A feladat lényegében megegyezik a 3. feladattal.

9.

Osszuk el mindkét oldalt 2-vel! 1·2 2·3 3·4 (n − 1)n (n − 1)n(n + 1) + + + ···+ = . 2 2 2 2 2·3

Azaz

          2 3 4 n n+1 + + + ···+ = . 2 2 2 2 3 De ez az állítás a 8. feladat speciális esete l = 2 esetén. Próbáljátok meg az állítást az els˝o fejezetben megismert teljes indukció módszerével is bebizonyítani! 10. Ha az 1 szám köztük van, akkor az akármelyik másikhoz relatív prím. Feltehetjük tehát, hogy az 1 nincs köztük. De akkor az n db szám mindegyike az alábbi n − 1 db skatulyában van: (2, 3),

(4, 5),

(6, 7),

. . . , (2n − 2, 2n − 1).

Akkor valamelyik skatulyában két szám is van. Van tehát az n db természetes szám között két szomszédos (amiknek a különbsége 1). Két szomszédos természetes szám viszont mindig relatív prím. (Bizonyítsátok be!) 11. Jelöljük x-szel az osztály tanulóinak számát. Ha a szitaformulát alkalmazzuk, akkor 0-t kell kapnunk, vagyis x − (18 + 23 + 21 + 17) + (9 + 7 + 6 + 12 + 9 + 12) − −(4 + 3 + 5 + 7) + 3 = 0,

amib˝ol x-et kifejezve és a kijelölt m˝uveleteket elvégezve azt kapjuk, hogy x = 40. 12. Ha tetsz˝olegesen megadok a p1 , p2 , . . . , pk számok közül néhányat, mondjuk p1 -et, p − 2-t és p3 -at, akkor azon számok

130

Megoldások

száma n-ig, melyek ezek mindegyikével oszthatók, úgy kapható, hogy n-et elosztjuk a kiszemelt törzsszámok szorzatával; esetünkben tehát ez a szám p1 pn2 p3 . Ha most kiszitáljuk az 1, 2, . . . , n számok közül azokat, melyek az n szám valamelyik törzstényez o˝ jével oszthatók, a formulánk szerint a következo˝ képpen kell eljárnunk: le kell vonni n-b˝ol az pn1 , majd az pn2 és így tovább, végül az pn számot; ezután hozzá kell adni az eredményhez azokat a k számokat, melyeket úgy kapunk, hogy az a számot két-két törzstényez˝ojével osztjuk el; majd le kell vonni azokat a számokat, melyeket n-et három-három törzstényezo˝ jével elosztva kapunk és így tovább: végül hozzáadjuk vagy levonjuk n-nek p1 · p2 · · · pk ad részét (vigyázzunk! ha n valamelyik törzstényezo˝ je magasabb kitev˝on szerepel a felbontásában, akkor ez az utóbbi hányados nem 1). Ha utánaszámoltok, láthatjátok, hogy amit kaptunk, az ugyanaz, mint amit a feladatban állítunk, ha felbontjuk a zárójeleket. 13. Számpéldák alapján könnyen megsejthetjük, hogy az eredmény n. Bebizonyítani például ezt a következo˝ képpen lehetséges: Tekintsük következ˝o törteket: 1n , n2 , . . . , nn . Ez az n darab tört persze nincs legegyszer˝ubb formában kifejezve; végezzük hát el – képzeletben – a lehetséges egyszer˝usítéseket. Olyan törteket kapunk, melyeknek nevez˝oje n-nek osztója, számlálója kisebb a nevez˝ojénél és relatív prím hozzá; nyilván minden ilyen törtet megkapunk. Ha most n-nek egy d osztóját tekintjük, akkor a d nevez˝oj˝u törtek száma éppen ϕ(d). Ebbo˝ l következik, hogy a ϕ(d)-k összege éppen a törtek száma, vagyis n. 14. Egyszer˝uség kedvéért tekintsünk el az n = 1, 2 esetekto˝ l (ekkor a keresett összeget könnyen kiszámíthatjuk: 1, mindkét esetben). Ha egy n-nél kisebb r szám relatív prím n-hez, akkor n−r is (miért?). Tehát, ha az ilyen számok összegét számítjuk, akkor párosíthatjuk úgy a tagokat, hogy páronként n legyen az összegük. ϕ(n) n·ϕ(n) Mivel ilyen pár 2 darab van, az összeg: 2 . 15–16–17. Hasonlóan igazolhatók teljes indukcióval, mint az el˝oz˝o pontban bizonyított azonosság.

Megoldások

131

18. Ha n = 0, 1, akkor helyettesítéssel látható, hogy az azonosság fennáll. Nagyobb n-ekre teljes indukcióval következik az állítás. Egy kis ízelít˝o abból, hogyan lehet a képletre „rájönni”: Elo˝ ször is nézzük meg, nem lehet-e Fn = an -szer˝u képletet találni (mint pl. a részhalmazok számánál, csak esetleg más a-val). Minden n-re fenn kell hogy álljon an+1 = an + an−1 . Oszthatunk itt an−1-nel, és azt kapjuk, hogy a2 − a − 1 =√0. Ezt a másodfokú egyenletet megoldva, kapjuk, hogy a 1 = 1+2 5 , √

a2 = 1−2 5 . A baj csak az, hogy sem a1 , sem a2 nem felel meg, mert n = 1-re nem kapunk 1-et. Ezen úgy próbálunk segíteni, hogy az √ !n √ !n 1− 5 1+ 5 , 2 2

sorozatokból ügyesen egy harmadik sorozatot képezünk, amely már minden követelménynek eleget tesz majd. Gondoljátok meg, miért éppen úgy képeztük a harmadik sorozatot, ahogyan az a feladatban szerepel! 19. Jobban látszik a megoldás, ha az elso˝ napon l˝ott vadak számát általánosabban a-val, a második napon lo˝ tt vadakét b-vel jelöljük. Ekkor harmadik napon a + b, negyedik napon a + 2b, ötödik napon 2a + 3b, hatodik napon 3a + 5b a lo˝ tt vadak száma. Ebb˝ol már gyaníthatjuk, hogy n-edik napon Fn−3 a + Fn−2b darab vadat l˝ott a vadász (persze, csak ha n = 3). Ezt könnyen igazolhatjuk teljes indukcióval. 20. A Fibonacci-számokat; ez teljes indukcióval könnyen bizonyítható. 21. A téglalap átlója mentén nem illeszkednek pontosan a darabok, hanem egy – éppen 1 cm2 -nyi – területet szabadon hagynak. Az 5 × 5-ös négyzetb˝ol kiindulva, az M.1. ábrán látható módon egy 8 × 3-as téglalapot készíthetünk; ekkor csak az a különbség,

132

Megoldások

M.1. ábra. hogy a részek átfedik egymást (mert 5 · 5 > 8 · 3). Általában egy Fn oldalhosszúságú négyzetb˝ol egy Fn+1 × Fn−1-es téglalapot készíthetünk (gondoljátok meg, hogyan). Ebbo˝ l azt vehetjük észre, hogy Fn2 „közel van” Fn+1 Fn−1 -hez, és felváltva hol kisebb, hol nagyobb nála. Ezt az észrevételt pontosan is megfogalmazhatjuk egy azonosság formájában: Fn2 − Fn+1Fn−1 = (−1)n . Ez az azonosság hasonlóan igazolható teljes indukcióval, mint a 15–17. feladatok állításai.

3. Kombinatorika a mértanban 1. 3.

  n − n. 2

A bizonyítás ugyanúgy végezheto˝ el, mint körök esetén.

4. Most is csak akkor értelmes a kérdés, ha már egy tartományt befestettünk kékre. Egy tetsz˝oleges tartomány színét mármost úgy kapjuk, hogy összekötjük egy pontját a kék tartomány egy pontjával, és megszámoljuk, hogy ez a szakasz hány egyenest metsz. Ha ez a szám páros, a tartomány kék lesz, ha páratlan, akkor piros. 5. Teljes indukcióval bizonyítjuk be az állítást a szereplo˝ országok száma szerint. 1 ország esetén semmi sincs fölrajzolva, az egész sík egyetlen ország, s ezt egy színnel ki lehet színezni.

Megoldások

133

Vegyünk egy n + 1 országból álló térképet, hagyjuk el az ábrából valamely országot határoló éleket. Ismét olyan gráfot kapunk, melynek minden csúcsa páros fokú. Az indukciós feltevés szerint kiszínezhetjük 2 színnel. Ennél a színezésnél a tekintett ország és szomszédai azonos szín˝uek, tehát ha az ország területén a színezést ellenkez˝ojére változtatjuk, akkor az n + 1 országot is jól színeztük ki. 6. Átfogalmazás: Minden gráfban van két azonos fokú pont. Bizonyítás: ha n pont van, akkor a pontok fokai a 0, 1, . . . , n − 1 számok közül kerülnek ki. Nem léphet fel azonban a 0 és az n − 1 egyszerre (indoklás!). Tehát n fokokra csak n − 1 leheto˝ ség van. A skatulyaelv szerint így van két azonos fokú pont. 7. Legyen ez a fok k, és az összes élek száma mondjuk . Ekkor fent és lent egyaránt ké pont kell hogy legyen. 8.

Nem: nem igaz egyik állítás sem, ellenpélda a háromszög.

9. Legyen a pontok foka k. Válasszunk ki alul j darab pontot! Ezekb˝ol kiindul k · j él. Egy fels˝o pont legfeljebb k élt „fogad” ezek közül. Tehát legalább j felso˝ pontba vezet él a j alsóból.   n 10. ; n − 1; n. 2

12. Ha két pontot az eredeti gráfban összeköto˝ út az él elhagyásakor megsemmisül, vagyis átmegy az élen, akkor helyettesíthetjük az élt a kör megmaradt ívével. Így három út egymáshoz f˝uzésével kötöttük össze a két pontot, de az elo˝ z˝oekb˝ol tudjuk, hogy ebb˝ol egy valódi összeköt˝o út is kiválasztható. 13. A gráf összefügg˝o, mert bármely két pontja összekötheto˝ , és nem lehet benne kör, mert a kör két végpontja kétféleképpen is összeköthet˝o volna úttal. 14. Azt kell bizonyítani, hogy a gráf összefüggo˝ , vagyis bármely két pont összeköthet˝o úttal. Két egymással összekötött pont esetén éppen ez az él a megfelelo˝ út. Ha a két pont nincs összekötve, akkor úgy kaphatunk egy ilyen utat, hogy vesszük azt a

134

Megoldások

kört, amely ezen él behúzásakor keletkezik, és ennek az eredeti gráfba es˝o íve a megfelel˝o út. 15. Induljunk ki egy pontból, és haladjunk egymáshoz csatlakozó éleken. Nem érhetünk vissza már érintett ponthoz, mert ez egy kört jelentene. El˝obb-utóbb tehát el kell akadnunk, és ez csak els˝ofokú pontban történhet. 16. Fát kapunk, mert az újabb „gally” hozzávételekor a gráf öszszefügg˝o marad, és nem keletkezik kör (meggondolandó!). Minden fát megkaphatunk így, mert a tekintett fában van els o˝ fokú pont. Ezt elhagyva, ismét fa marad a gráf, ebbo˝ l ismét elhagyhatunk egy els˝ofokú pontot és így tovább. Ez pedig éppen a fa növekedése visszafelé bef˝uzött filmen. 17. Két pont esetén 1 él van. Egy újabb „gally” 1-gyel növeli a pontok számát is és az élek számát is. 18. Hasonlóan járunk el, mint az optimista vállalkozó esetében: a megkonstruált fát F-fel jelöljük, és megmutatjuk, hogy bármely más G fához találhatunk egy H fát, mely olcsóbb (legalábbis nem drágább), és melynek több éle tartozik F-hez, mint C-nek. Kövessük nyomon F megszerkesztését, egészen addig, amíg el o˝ ször kellene G-beli élt törölnünk. Legyen ez az él e. Ha e élt G-bo˝ l elhagyjuk, akkor G-nek megmaradó része két részre esik szét. Mivel nem lehet e két rész közötti élek mindegyike törölve, van egy eltörletlen a él köztük. Ha most e helyett ezt az a élt vesszük G-hez, akkor a kapott H fa olcsóbb lesz (vagy legfeljebb ugyanannyi), mint G. (Gondoljátok meg miért, és azt is, hogy ezt az eljárást folytatva, el˝obb-utóbb magát F-et kapjuk.) 19. Igen jó például a következo˝ eljárás: kiindulunk egy tetsz˝oleges ponthól, megépítjük a belo˝ le kiinduló legolcsóbb vonalat, majd az ehhez (valamelyik végpontjában) csatlakozó vonalak közül a legolcsóbbat és így tovább, mindig a legolcsóbb olyan vonalat építjük meg, mely egy új állomást kapcsol be a már meglevo˝ hálózatba. Rátok hagyjuk annak meggondolását, hogy így a legolcsóbb fát kapjuk.

Megoldások

135

20. Lásd az M.2. ábrát! 7 4

7 6 4

3

1

4

7 4

1 jó: 16

3

6

1 optimista: 17

4

3

6 4

pesszimista: 17

M.2. ábra. 21. Az eredeti gráf, vagyis amit az eredeti országok határai alkotnak, esetleg kicsit eltorzítva. Az eredeti térképen nem lehetnek nagyon „vad” országok, vagyis olyanok, mint az M.3. ábrán látható országok; legjobb, ha feltesszük pl., hogy minden csúcsban csak három ország találkozik, és két ország közös határa egyetlen, összefügg˝o ív (a Szovjetunió és Kína határvonalára ez nem igaz, azt szétvágja Mongólia!).

M.3. ábra. 23. Euler tételéb˝ol fogjuk kiszámítani a keletkezett síkrészek számát; ez eggyel kevesebb, mint a tételben szereplo˝ l, mert az országok közé az óceánt is
be kell számítanunk. Az összefüggésben szerepl˝o c nyilván n2 + 2n (a parton lev˝o csúcsokat is be

136

Megoldások

kell számítani!). Az élek számát megkaphatjuk a 6. pontban szerepl˝o tétel segítségével: összeadjuk a fokszámokat és elosztjuk 2
vel. A fokszámok: 2n darab 3-as és n2 darab 4-es, ezek összege
2n2 + 4n, az élszám n2 + 2n. Így l + n2 + 2n = n2 + 2n + 2, ami
b˝ol l − 1 = n+1 2 + 1. 24. Igen (lásd az M.4. ábrát).

M.4. ábra. 25. Nem. Ugyanis feltételezve, hogy lerajzoltuk, egy olyan térképnek tekinthetnénk rajzunkat, melynek 6 csúcsa, 9 éle, és így – Euler tétele szerint – 5 országa van. De minden országot legalább 4 él határol (nincs is 3 élb˝ol álló kör a gráfban), tehát országonként összeszámlálva, legalább 5·4 2 = 10 él adódik. Így arra a képtelen következményre jutunk, hogy 9 = 10. 26. Képzeljük el, hogy a lehet˝o legtöbb gát van felépítve. Ekkor az egyes medencéket három-három gát határolja (miért?). A gátakat országonként összeszámlálva, 3l2 = e´ adódik. Más szóval, l = 23e´ . Ezt helyettesítsük be az Euler-tételbe: 23e´ + c = e´ + 2; innen e´ = 3c − 6. Tehát: egy síkba rajzolható, c pontú gráfnak legfeljebb 3c − 6 éle lehet.
27. A 23. feladathoz hasonlóan járunk el. Nyilván c = n + n4 (itt felhasználjuk azt, amit az 1. pontban kiszámítottunk, hogy ti.

Megoldások

137


az átlóknak összesen n4 metszéspontja van). Az élek száma: e´ = 

1 1) + n4 · 4 . Tehát Euler tételét felírva: l + n + n4 = 2
n · (n −
n n 4 + 2 · 4 + 2. Mi (l − 1)-re vagyunk kíváncsiak (hiszen
a küls
o˝ „óceánt” nem kell számba vennünk), ami tehát l −1 = n4 + n2 − n + 1. 28. Lásd az M.5. ábrát.

M.5. ábra.

4. Blokkrendszerek 1.

441, 44.

2. A lakók 1-t˝ol 9-ig számozva, a klubok tagnévsora egy-egy zárójelen belül: (1, 2, 3) (1, 4, 7) (1, 5, 9) (1, 6, 8)

(4, 5, 6) (2, 5, 8) (2, 6, 7) (2, 4, 9)

(7, 8, 9) (3, 6, 9) (3, 4, 8) (3, 5, 7)

A te megoldásod biztosan nem különbözik etto˝ l lényegesen. Ezen az értend˝o, hogy ha különbözik is t˝ole, mégis alkalmasan átszámozva a városlakókat, ezzel megegyezo˝ vé fog válni. Próbáld meg! 3. Minden leánynak 8 társa van, és naponta 2-vel tud egy sorban sétálni. Tehát ahhoz, hogy mindegyikkel pontosan egyszer sétáljon egy sorban, 4 nap szükséges.

138

Megoldások

7. Például az alábbi v db klub: mindegyik városlakóhoz csinálunk egy klubot, amelynek mindenki tagja, o˝ t kivéve. Itt b = v, k = v − 1, r = v − 1, λ = v − 2.

8. Csináljunk páros gráfunkból egy új páros gráfot úgy, hogy veszünk b − v db új alsó pontot, és ezek mindegyikét összekötjük mindegyik fels˝o ponttal. Lássuk be, hogy erre az új gráfra teljesülnek a harmadik fejezetben szereplo˝ König-tétel feltételei, tehát van benne els˝ofokú faktor. Lássuk be továbbá, hogy ebbo˝ l már következik, hogy a feladat állilása igaz! 9.

Ez nagyon egyszer˝u. Például az alábbi: 1 4 3 2

2 1 4 3

3 2 1 4

4 3 2 1

Könnyen ellen˝orizhetitek, hogy jól megértettétek-e az ábrán látható latin négyzet alapötletét. Tudnátok-e ugyanilyen 5 × 5-öset csinálni? Hát n × n-eset? 10. 24 · 4! = 576, illetve 24.

11. Minden számhoz 1-et hozzá kell adni, így 4-gyel növekszik minden sor-, ill. oszlopösszeg. 12. Olyanokból, amelyeknek az átlóiban is minden szám pontosan egyszer fordul el˝o. Például az alábbi kett˝ob˝ol: 1 3 4 2

2 4 3 1

3 1 2 4

4 2 1 3

1 4 2 3

2 3 1 4

3 2 4 1

4 1 3 2

Ezekb˝ol az alábbi „igazi” b˝uvös négyzetet kapjuk: 5 12 2 11

10 3 13 4

15 6 8 1

0 9 7 14

13. Ha lenne ilyen latin négyzet, akkor nemcsak o˝ , hanem minden t˝ole nem lényegesen különbözo˝ latin négyzet is ortogonális

Megoldások

139

lenne a 4., 5. és 8. latin négyzetekre. (Ezt be kell látni!) Vehetnénk tehát helyette azt a vele lényegében egyenlo˝ latin négyzetet, aminek az els˝o sora ilyen: 1 2 3 4. De mi állhat ebben a latin négyzetben a második sor els˝o mez˝ojében (a3-ban)? 1 nem, hiszen akkor nem lenne latin négyzet. De 2, 3 vagy 4 sem, mert ha pl. 3 állna, akkor a 8. ábra latin négyzetére nem lenne ortogonális, hiszen „egymásra téve” o˝ ket, a (3, 3) pár a c4 és a3 mezo˝ kön is szerepelne. Tehát tényleg nincs ilyen latin négyzet. (Próbáljátok a fenti megoldás mintájára belátni, hogy n × n-es latin négyzetekb˝ol legfeljebb (n − 1)-et lehet úgy kiválasztani, hogy bármely kett˝o ortogonális legyen egymásra!) 14. Ha lenne ilyen, a 13. feladat megoldásában leírt indokolást alkalmazva feltehetjük, hogy els˝o sora: 1 2 3 4, a második sor els˝o eleme pedig 3 vagy 4. Ezután már viszonylag kevés próbálgatás célhoz vezet. 15.

1 2 3

2 3 1

3 1 2

1 3 2

16. A 4 × 9-es táblázat az alábbi: 1 1 1 1

1 2 2 2

1 3 3 3

2 1 2 3

2 2 3 1

2 3 1 2

2 5 8 11

3 6 9 11

1 6 8 12

2 1 3 3 1 3 2

3 2 1 3 2 1 3

3 3 2 1

A blokkok: 10 11 12 13

1 2 3 10

4 5 6 10

7 8 9 10

1 4 7 11

2 4 9 12

3 5 7 12

1 5 9 13

2 6 7 13

3 4 8 13

A véges projektív sík pontjait 1, 2, . . . , 13 jelöli, egyenesei az alsó táblázat oszlopaiban állnak. Ha az egyenesek táblázatából elhagyjuk az els˝o oszlopot, és az összes többi oszlop utolsó elemét, a maradó hármasok éppen megegyeznek a 2. feladat megoldásaként kapott Steiner-rendszerrel. Be tudnátok-e látni, csak a véges projektív sík tulajdonságait használva, hogy itt biztosan egy Steiner-rendszert fogunk kapni?

Powered by TCPDF (www.tcpdf.org)