¾ Ð Ý

Elekes Gyrgy KOMBINATORIKA FELADATOK (Masodik, b}ovtett kiadas)

Etvs Lornd Tudomnyegyetem 2000.

2

Elekes Gy:

3

Kombinatorika feladatok

E feladatgyjtemny els rend lja: segtsget nyjtani az ELTE matematikus, alkalmazott matematikus, programoz matematikus s matematika tanr szakos hallgati szmra a Vges matematika" trgy tanulshoz. A feladatgyjtemnyek sszelltit mindenkppen befolysolja egyni preferen ijuk: mit tartanak szpnek, rdekesnek s fontosnak. Ez all magam sem lehetek kivtel. Mgis igyekeztem gy sszevlogatni a tmkat, hogy amilyen mrtkben

sak lehet, fedjk az emltett negy szak pillanatnyi kombinatorika anyagt. Ezen tlmen en azonban gyelembe kellett vennem ms szempontokat is. Mr a korbbi vltozatok rsa kzben felhvtk gyelmemet arra, hogy nin s hasonl tmj irodalom sem az ltalnos-, sem a kzpiskolk szmra. Ezrt egyrszt bevettem teljesen kezd knek val, bevezet jelleg feladatokat is, hogy a leend

tanrok merthessenek bel lk, ha maguk is tantjk majd e trgyat. Msrszt, ugyanezen okbl, kt rszre tagoltam az anyagot: alap- s halad szintre. Nem azt szndkozom ezzel sugallni, hogy az els rszt mr ltalnos ill. kzpiskolban kellene tantani; mindssze azt a vlemnyemet juttattam ezzel kifejezsre, hogy egy tlagos kzpiskols (vagy akr egy rtelmes nyol adikos) kpes az els rszben el kerl gondolatok megrtsre s a feladatok megoldsra (kivve esetleg a legnehezebbeket) | remlhet leg mg szrakoztatnak is tallva ket. A nehezebb feladatokat sillaggal jelltem. Ugyanilyen jelet kaptak azok, amelyeket knytelen voltam olyan helyre tenni, ahol bizonyos, a megoldsukhoz szksges el ismeretek mg hinyoznak. A Skatulyk, tlagok " szakaszban pldul a gyakorl feladatok nagy rszhez szksges a binomilis egytthatk ismerete; azrt jelltem ket sillaggal, mert azok sak ks bb kerlnek sorra. Hogy mgis itt szerepelnek, annak az az oka, hogy megoldsi mdszereik ehhez a szakaszhoz kap soldnak; a tanulknak feladni ket persze sak akkor lehet, ha a binomilis egytthatkat el z leg mr megismertk. Akkor viszont lszer is ilyen krdsekkel fszerezni a nha kiss monoton szmolgatsokat. (Mellesleg e problmk kzl egyesek a grfelmlet bizonyos alapvet fejezetei fel ka singatnak; nhnyat ks bb, a megfelel tmk elejn viszont is ltunk majd.) Vgezetl szeretnk ksznetet mondani azoknak, akik munkmban kzvetlenl vagy kzvetve segtsgemre voltak: | Hzi hasznlatra kszlt anyagaibl sok rdekes s szp feladatot engedett t Hrs Lszl, Szkely Lszl s Re ski Andrs. Egy{egy tmban Frank Andrs tletei ill. Sz nyi Tams feladatsorai bizonyultak igen hasznosnak. | Simonovits Miklssal sokig tantottunk egytt kombinatorikt (is), rtunk sten ilezett jegyzeteket s feladatgyjtemnyeket | utbbiak anyaga kpezte jelen sszellts gerin t. | P osa Lajost ol, gondosan osszev alogatott es egymasra eptett feladatsoraibol (melyekb} ol b} oven mertettem) sokat tanultam arrol, hogyan erdemes kombinatorik at | es altalaban matematikat | tantani. | Utoljra hagytam T. Ss Vert, akinek a legtbbet ksznhetek: szerettette meg velem a kombinatorikt. Aki hallotta t valaha el adni, aki tapasztalta, hogyan tudja kibontani a gondolatokban rejl szpsgeket, megrti, mirt egyike azoknak, akik krl a mr rgen vilghr magyar kombinatorikai iskola mai gener ija feln tt.

...

4

Elekes Gy:

5


Tartalomjegyzk I.RSZ : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : :

7

1. Leszmlls I. : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : :

8

1.1. 1.2. 1.3. 1.4. 1.5. 1.6. 1.7. 1.8.

Dobjuk ki a rosszat! : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : s ha tbbszr is megszmoltuk? : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : Gyakorl feladatok (Hars L aszl o gy} ujteseb}ol) : : : : : : : : : : : : : : : : : : : : : : : : : Skatulyk, tlagok|hnyszor szmol, aki nem rest? : : : : : : : : : : : : : : : : : : : : Binomilis egytthatk (Posa Lajos nyom an) : : : : : : : : : : : : : : : : : : : : : : : : : Ha egy elem tbbszr is szerepelhet ::::::::::::::::::::::::::::::::: A szita{mdszer : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : Kt plda rekurziokra : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : :

...

...

9 10 11 13 16 20 21 23

2. Grfok I. : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 28

2.1. Elemi grfelmlet : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 2.2. Fk : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 2.3. Ktszeres sszefgg sg : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 2.4. Irnytott grfok : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 2.5. Vegyes feladatok : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 2.6. Fokszmsorozatok realiz ija : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 2.7. Pros grfok. A K nig{Hall ttelkr. : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 2.8. ltalnos grfok prostsai. Tutte ttele : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 2.9. Grfok kromatikus szma : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 2.10. Skgrfok : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 2.11. Hibs okoskodsok : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : :

28 31 33 34 35 36 37 44 45 47 49

3. Algoritmusok I. : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 52

3.1. Algoritmusok lpsszma. : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 3.2. A legkisebb elem kivlasztsa. Rendezs. : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 3.3. Binris fk. A kupa . : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : :

52 54 54

II.RSZ : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 57 4. Leszmlls II. : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 58

6 4.1. 4.2. 4.3. 4.4. 4.5.

Elekes Gy: >jabb pldk rekurzikra : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : Tkrm, tkrm :::::::::::::::::::::::::::::::::::::::::::::::::::: Talljunk rekurzit ::::::::::::::::::::::::::::::::::::::::::::::::: Lineris rekurzik : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : Genertor{fggvnyek : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : :

... ...

58 58 60 61 63

5. Grfok II. : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 67

5.1. 5.2. 5.3. 5.4.

A Ramsey{ttelkr (Posa Lajos nyom an) : : : : : : : : : : : : : : : : : : : : : : : : : : : : : Extremlis grfok : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : Minimax ttelek : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : A Prfer{kd. : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : :

67 71 74 78

6. Algoritmusok II. (Graf algoritmusok) : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 80 6.1. sszefgg sgi algoritmusok : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 6.2. A Dijkstra{algoritmus. : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 6.3. Minimlis kltsg feszt fk : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : :

80 82 84

7. Halmazrendszerek. : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 87

7.1. 7.2. 7.3. 7.4. 7.5.

Helly tpus u tetelek : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 87 Ramsey tetelei halmazrendszerekre. : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 90 Vges geometrik (Sz} onyi Tam as nyom an) : : : : : : : : : : : : : : : : : : : : : : : : : : : 93 Klasszikus extremlis halmazrendszerek : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 97 Linris algebrai mdszerek : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 100

III.RSZ tletek s eredmnyek : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 103 IV.RSZ Megoldsok : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 115

7


I. RSZ

amit a kzpiskolbl taln mr ismersz (de az se baj, ha mg nem).

8

Elekes Gy:

1. fejezet Leszmlls I.

b

fa; b; g elemeket? ez az fa; b; g sorrend

b

ez az fa; ; bg sorrend

a

ez a

fb; a; g sorrend

a

ez a

fb; ; ag sorrend

a

b

ez a

f ; a; bg sorrend

b

a

ez a

f ; b; ag sorrend

Hnyfle sorrendben helyezhetjk el az a

b

Az bra szerint a lehet sgeket olyan fa reprezentlja, amelyik el szr hrom fel gazik, aztn ktfel, vgl mr sak egy gat hajt. A lehet sgek szma: .

DEF.

3 2 1=6 Az 1 2 . . . n szorzatot a tovbbiakban az n utn rt felkiltjelel jelljk: n! s

n faktorilisnak nevezzk.

A kvetkez feladatokban elg, ha azt vizsgljuk, melyik lpsben hnyfel gazik a lehet sgek fja. 1. Hny klnbz aut{rendszm kszthet (hrom betb l s hrom szmjegyb l)? ! 2. Hny pontosan hatjegy szm van a tzes szmrendszerben, a) ha valdi hatjegy szm nem kezd dhet 0{val? b) s ha mg azt is megkveteljk, hogy ne legyen 10{zel oszthat? 3. Hnyfle lehetsges sorrendje van

n elemnek?

! !

4. Hnyflekppen festhetjk egy n{emeletes hz szintjeit fehrre, drappra s barnra, ha szomszdos szintek nem lehetnek egysznek? !

9


5. Egy 15 tag klub elnkt, titkrt s jegyz t vlaszt. a) Hnyflekppen tehetik ezt? b) s ha Kov s rnak mindenkppen szeretnnek valamilyen tisztsget adni?

!

6. Egy versenyen 57{en indulnak; az jsgok az els hat helyezett nevt kzlik. Hnyfle lehet ez a lista? ! 7. n klnbz virgot k klnbz vzba hnyflekppen oszthatunk el? (Egyes vzk resek is maradhatnak.) 8. Hny darab m n{es 0{1-mtrix van? (Elemeik teht {k vagy {esek.) !

0

1

9. Hny klnbz eredmnyt kaphatunk, ha tzszer dobunk a) dobko kval b) pnzdarabbal? 10. Hnyan vannak a) egy n{elem halmaz sszes rszhalmazai? b) az n hosszsg {sorozatok?

) Mirt egyenl a fenti kt eredmny? Mutass kl snsen egyrtelm termszetes megfeletetst! !

0 1

11. Hnyflekpp lehet elhelyezni a sakktbln 8 bstyt, hogy semelyik kett se sse egymst? ! 12. Hny olyan hatjegy szm van, amelyben az els hrom jegy azonos az utols hrommal? ! 13. Hny A 7! B fggvny van, ha elemszmt jelli.)

jAj = n s jB j = k? (Itt jX j az X

halmaz

!

A 7! B bijek i (kl snsen egyrtelm megfeleltets) van, ha jAj = jB j = n? ! Hny A 7! B injek i (klnbz elemekhez klnbz eket rendel fggvny) van, ha jAj = n s jB j = k ? !

14. Hny 15.

16. Hny TOT szelvnyt kell kitltennk, hogy biztosan legyen 13 + 1 tallatunk?

17.

!

...

1

pr kr szmnak hny osztja van ( {et s n{et is belertve)? A A p1 k1 p2 k2 pi {k klnbz primeket jellnek. ! 18. Hnyflekpp lehet kzppontosan szimmetrikusan elhelyezni a sakktbln 8 bstyt, hogy semelyik kett se sse egymst? ! DEF. n elem sszes lehetsges sorrendjei: n permut ii. Ezek szma n .

!

DEF. n elemb l az sszes lehetsges sorrendben k darab klnbz kivlasztsa: az n elem k{adosztly vari ii. Ezek szma n(n 1)(n 2) . . .(n k + 1) =

!(

)!

n = n k . (A bal oldalon k szorztnyez szerepel.) Megjegyzs: A permut i teht a vari i spe ilis esete: el bbi fogalomhoz jutunk.

k = n{re ppen az

DEF. n elemb l kpezhet k tag sorozatok (egy{egy elem tbbszr is szerepelhet): az n elem k {adosztly ismtlses vari ii. Ezek szma nk .

10

Elekes Gy:

1.1. Dobjuk ki a rosszat! Egy tipikus hiba (s elkerlse) Hny olyan (htjegy) telefonszm van, amiben van valahol egyms mellett kt azonos szmjegy? (Tegyk fel, hogy ezek a szmok 0{tl 9{ig brmilyen jeggyel kezd dhetnek.) Megolds": 6. Azok szma, amelyekben az els kt jegy azonos: 5 6 Ugyangy, ahol az i{edik s i {edik jegyek azonosak: .
+1

6 10

10 1 10 = 10 10

Hol a hiba? Ott, hogy egyeseket, pl. a 11 22 345{t ktszer szmoltuk; a 111 2222{t mg tbbszr. I. J megolds (ki sit bonyolultabb): mindent sak egyszer szmolunk. Jelljk az i{edik jegyet ai {vel! 6. Ha a1 a2 : Ha a1 6 a2 , de a2 a3 : 5. . . . 5 . Ha a1 6 a2 6 a3 6 a4 6 a5 6 a6 a7 : 5 4 2 3 3 2 4 5 Eredmny: . II. J megolds (sokkal egyszerbb): J = sszes { rossz. sszes: 7 ; Rossz (ha nin s kt azonos szomszdos): 6. 7 6 6 6. J: sszes { rossz

= =

=

10 1 10 . . .10 = 10 10 9 1 10 10 10 10 = 9 10

= = = = = = 10 9 9 9 9 9 1 = 9 10 10(10 + 9 10 + 9 10 + 9 10 + 9 10 + 9 ) 10

10 9 = 10 10 9 = 10(10 9 ) 19. Hny termszetes szm teljesti az 57 n 157 felttelt?

!

20. Hny hatjegy termszetes szm van? (Ami 0{val kezd dik, az nem hatjegy.)

!

21. Ko kval tzszer dobva hny olyan sorozatot kaphatunk, amiben van legalbb egy hatos? ! 22. Egy 15 tag klub elnkt, titkrt, jegy t s pnztrost vlaszt. Kov s rnak mindenkppen szeretnnek valamilyen tisztsget adni. Hnyfle lehet a vezet sg? !

11


1.2. . . . s ha tbbszr is megszmoltuk? 23. Kilen egyforma dula kzl ngyre egy{egy A{t runk piros, kk, zld illetve fekete tintval; a tbbin a B,C,D,E s F betk tallhatk feketvel. a) Hnyflekppen rakhatjuk a dulkat sorba egyms utn? b) Szilrd, szegny, sznvak; egyltaln nem tudja megklnbztetni a szneket. Hny olyan sorrendje van a dulknak, amikor sak azt ltja, hogy ABC szerint sorban vannak? s hny olyan, amikor sak a B A C A D A E A F sorrendet ltja?

) Hny sorrendet tud megklnbztetni Szilrd? ! 24. Az el z feladat fekete B jel duljt hrom pldnyra serljk: egyik barna, msik lila, a harmadik pedig szrke. a) A 11 dulnak hny olyan sorrendje van, amir l Szilrd sak azt ltja, hogy ABC{sorrendben vannak? b) Hny C B D B E B F A A A A tpus van?

) Hny sorrendet tud most megklnbztetni Szilrd? 25. Hsz egyforma dula kzl nyol ra 1"{et, tre 2"{t s htre 3"{at rtunk (mindegyiket feketvel!). Hnyflekppen rakhatjuk sorba ket? ! 26. Egy piros s egy kk dobozba akarunk eltenni 100 klnbz trgyat gy, hogy mindkett be 50{50 jusson. Hny lehet sg van? 27. (folytats) Mi a vlasz, ha egy srga dobozunk is van, s 150 trgyat kell (egyenletesen) elosztanunk? 28. n1 darab 1{est, n2 darab 2{est, , nk darab k{ast hnyflekppen rakhatunk sorba? ! 29. Hnyfle anagramma (a betk sorrendjnek megvltoztatsval keletkez , esetleg rtelmetlen sz) kszthet a MATEMATIKA betib l? DEF. k1 darab 1{es, k2 darab 2{es, , kn darab n{es lehetsges sorballtsainak szma a k1 k2 kn elem ismtlses permut ii. Ezek szma:

...

+ +...+

...

(k1 + k2 + . . . + kn )! k1 ! k2 ! . . . k n !

1.3. Gyakorl feladatok

(Hars L aszl o gy} ujteseb}ol)

30. A kanadai irnytszmok XnXnXn alakak, ahol az X {ek egy{egy (esetleg klnbz ) bett, az n{ek egy{egy szmjegyet jelentenek. Hny ilyen irnytszm ltezhet?

12

Elekes Gy:

31. Az iskolai atltika versenyre magasugrsbl, tvolugrsbl, 60 ill. 400 mteres futsbl s kislabdadobsbl kell egy osztly 27 tanulja kzl killtani egyet{ egyet. Ugyanaz az ember tbb (akr az sszes) sportgban is indulhat. Hnyfle lehet a nevezsi lista? 32. Hny olyan hatjegy szm van, amiben nin s egyms mellett kt azonos szmjegy? ! 33. n t s n lnyt egy sorba akarunk lltani gy, hogy mindig felvltva egy lny { egy kvetkezzen. Hnyflekppen tehetjk ezt? ! 34. Hny olyan htjegy telefonszm van, amiben van kt szomszdos azonos szmjegy? 35. (folytats) s ha sak azt kveteljk meg, hogy valahol legyenek azonosak, de nem felttlenl egyms mellett? ! 36. Hnyflekppen kldhetnk el egy nyron 29 klnbz kpeslapot ngy ismer snknek? (Megtehetjk, hogy valaki egyet se kap; akr mindet kldhetjk ugyanannak.) 37. Hny hsztag szimmetrikus {sorozat van? (msodik fele az els tkrkpe) 38. Olyan nyol jegy szmot keresnk, melyet a szmjegyei sorrendjnek megfordtsval keletkez szmhoz adva : : {et kapunk. Hny ilyen van? 39. A vitorlsbajnoksgon 37 haj indult. Fakez Jan si eddig mindig utolsnak rt lba; rgi vgya, hogy el bbre rukkoljon. A verseny utn ltjuk, amint szles mosollyal megy hazafel: sikerlt! Hnyfle lehetett a befutsi sorrend? (Mg az sem kizrt, hogy | risi szeren svel | dobogra kerlt vagy akr nyert is!) 40. Egy Forma I{es sapatrl az a hr jrja, hogy els szm versenyz jket, X{ et a msik, Y nem el zheti meg, ha X az els helyen van; s t, ha vezet s X felzrkzik mgje, kteles el re engedni. Ms helyezsekrt | ha nem k vannak az len | szabad egymssal satzniuk. Hnyfle lehet a sorrend a dobogn (els hrom hely) egy olyan futamon, ahol huszonnyol an indulnak? 41. Tz egyforma sokit, hat egyforma rggumit s kilen egyforma jgkrmet osztunk ki 25 gyerek kztt gy, hogy mindenki pontosan egyvalamit kapjon. Hnyflekppen tehetjk ezt? ! 42. Ngy bartomnak 29 klnbz kpeslapot kldtem: Aladrnak tt, Benek nyol at, Cilinek hetet s Dominak kilen et. Hnyflekppen kldhettem el a lapokat? 43. Hny klnbz (nem felttlenl rtelmes) anagramma kszthet a KARABAH sz betib l, ha se az elejn, se a vgn nem llhat A ? 44. n klnbz magassg ember hnyflekppen tud kt n{hosszsg sorba llni gy, hogy az els sorban mindenki ala sonyabb legyen a hts sorban a megfelel helyen llnl? !

0 1

99 999 999

2

Az 52 lapos fran ia krtyban ngy szn (k r, pikk, kr s tre) mindegyikb l 13 darab van. Minden sznb l ngy gura, (sz, kirly, dma s bubi),

13


45. 46. 47. 48. 49. 50. 51.

52.

53. 54. 55. 56. 57. 58. 59. 60.

kilen pedig kettest l tzesig szmozott. Ngy jtkosnak 13-13 lapot osztva termszetesen klnbz nek tekintjk, ha nlad van 13 rtkesebb s nlam 13 kevsb j, vagy ugyanazok a lapok ppen ellenkez leg helyezkednek el. Az persze kzmbs, hogy a pikk szt el bb kaptad, mint a tre kirlyt, vagy fordtva. Hny klnbz leoszts van? ! Hny olyan leoszts van, ahol minden jtkosnak van sza? ! Hny olyan leoszts van, amikor minden sz egy kzbe kerlt? ! Hny olyan leoszts van, amikor minden gura kt, egymssal szemben l

jtkoshoz kerlt? Hny olyan leoszts van, amikor minden jtkosnak jut minden szmbl s gurbl? Hny olyan leoszts van, ahol kt szemben l jtkosnak sszesen sak kt sznb l jut lap? Az 52 lapos fran ia krtybl 5 lapot osztanak. Hnyflekpp lehet nlad a) pker [4 egyforma gura vagy szm℄, b) full [2 egyforma + 3 egyforma gura vagy szm℄,

) kt pr [2 egyforma + 2 msfajta egyforma gura vagy szm℄, d) sor [5 egyms utni, nem felttlen azonos szn gura vagy szm℄, e) supa tre? Hnyflekppen festhetjk ngy klnbz sznre egy szablyos tetrader lapjait, ha az egymsba forgathat pldnyokbl sak egyet{egyet akarunk? (folytats) Ugyanez a krds egy ko kval s hat sznnel. Egy zskban 10 pr ip van. Milyen valszn, hogy ha kivesznk bel le 6 darabot, lesz kztk egy pr? pr kr . (A pi -k klnbz primeket jellnek.) Mennyi az Legyen n p1 k1 p2 k2 n osztinak szorzata ( {et s n{et is belertve)? ! Hny klnbz grf adhat meg az f ; ; ; ng pontokon? ! Hnyfle lehet egy ping{pong krmrk zs eredmnye? (Nem a helyezs szmt, hanem az, ki kit vert meg s kit l kapott ki; a nyers arnya kzmbs.) Ugyanez a krds sakk{krmrk zsre. (Itt dntetlen is van.) Mekkora osztly esetn lesz 50% -nl nagyobb valsznsge, hogy kt tanulnak ugyanakkor van a szletsnapja? Az ; ; ; n szmok kzl hnyflekpp vlaszthatunk ki hrmat gy, hogy az sszegk oszthat legyen hrommal?

=

... 1

1 2 ...

1 2 ... 3

1.4. Skatulyk, tlagok|hnyszor szmol, aki nem rest?

14

Elekes Gy:

Hrom plda | hrom mdszer, amire szksgnk lesz. A skatulya{elv:

+1

Ha n dobozba n golyt tesznk, valamelyikbe legalbb kett kerl. (Ht persze: ha mindegyikbe legfeljebb egy jutna, akkor legfeljebb n goly lenne.) tlagols: Ha nhny szm szmtani kzepe 59, akkor tallhat kztk olyan is, ami legalbb 59 s olyan is, ami legfeljebb annyi. (Ht persze: ha pl. mindegyik kisebb lenne, akkor az tlaguk is kisebb volna.) Igaz{e hasonl llts pozitv szmok mrtani vagy harmonikus kzepre? Kett s leszmlls: Pistike sszeadni tanul. Piros s kk golyk vannak el tte; egy rszk kisebb, msok nagyobbak. Megszmolja a pirosakat s a kkeket; majd a ki siket s a nagyokat. sszeadja az els kt szmot, aztn a msik kett t. Csodlkozva ltja, hogy a kt eredmny azonos. (Ht persze: mindkett az sszes goly szma.) Megjegyzs: a fenti hrom mdszer gyakran egymssal kombinlva hasznlhat.

A skatulya{elv 61. Hat pr fekete s ugyanannyi kk zoknid | amelyeket, sajnos, nem raktl ssze prosval | sszekeveredett a kban. Teljes sttsgben hny darabot kell el venned a 24{b l, hogy biztosan legyen kztk egy sszeill pr? 62. (folytats) s ha egy kk prra van szksged? 63. Egy dobozban szz goly van. Kzlk 28 piros 20 zld 12 srga 20 kk 10 fekete 10 fehr Mi a legkisebb darabszm, amennyi goly kztt mg biztosan lesz 15 egyszn?

!

64. Mutasd meg, hogy minden trsasgban van kt ember, akiknek ugyanannyi ismer sk van a jelenlv k kztt! (Az ismeretsgek kl snsek.)

15


65.

Bizonytsd be, hogy tetsz leges 100 darab termszetes szmbl kivlaszthat nhny, amelyek sszege oszthat 100{zal! 66. Egy hatszg oldalait s tlit (sszesen 15 vonalat) tetsz legesen piros s kk sznekkel hztl be. Mutasd meg, hogy a) brmely s sbl indul hrom egyszn vonal. b) biztosan rajzoltl hrom egyszn vonalbl ll hromszget. 67. Igaz{e ugyanez tszgre? s ht{ vagy tbb oldalra?

tlagols s kett s leszmlls

68. Ha egy mtrix minden sorban az elemek tlaga legalbb 100, akkor van olyan oszlop is, ahol az tlag szintn legalbb 100. 69. Kt krlapot vgtunk ki tltsz flibl s mindkett t n egyforma kr ikkre osztottuk. E kr ikkeket pirosra s kkre festi valaki, spedig az egyik lapon n{et pirosra s n{et kkre; a msikon tetsz legesen. Mutassuk meg, hogy a kt krlap egymsra helyezhet gy, hogy legalbb n kr ikk kerljn vele azonos sznre! 70. Legyen H tetsz leges korltos skbeli alakzat, melynek terlete legalbb 10 egysg. Daraboljuk fel a skot vzszintes s fgg leges egyenesekkel egysgngyzetekre (kpzejk azt, hogy paprbl van), s helyezzk egymsra azokat a ngyzeteket, amelyekre H {nak legalbb egy pontja kerlt. Mutassuk meg, hogy a paprdarabok tdfhet k egy tvel gy, hogy H {nak legalbb 10 pontjt talljuk el egy szrssal. (Az llts akkor is igaz, ha a terlet 9,1 egysg. Mirt?) 71. (folytats) Legyen H tetsz leges korltos alakzat a skban; terlett jellje TH . Mutassuk meg, hogy H eltolhat gy, hogy legalbb TH darab r spontot tartalmazzon! 72. Egy sszejvetelen tzen vettek rszt. rkezskor ngy msikkal fogott kezet 5 ember t msikkal fogott kezet 2 ember hat msikkal fogott kezet 3 ember Hny kzfogs trtnt sszesen? !

2

Gyakorl feladatok 73. Hny mrk zst jtszanak egy n rsztvev s kiesses ping{pong versenyen? Az 1, 2, , 2n szmok kzl n {et kivlasztva a) biztosan lesz-e kztk kt relatv prm? (azaz olyan, melyek legnagyobb kzs osztja 1) b) Ht kett , amelyek kzl egyik osztja a msiknak?

74.

...

+1

16

Elekes Gy:

... ()

75. Legyenek A1 ; A2 ; ; An tetsz leges vges halmazok. Jellje jAi j az i{edik elemeinek szmt, d x pedig az x X elem fokt,X vagyis azt, hogy x hny darab jAi j Ai {ben van benne. Igazold, hogy d x x i 76. (folytats) Bizonytsd be az el z lltst abbl is, hogy egy ai;j mtrixra

( )=

XX

i

j

j

i

ai;j ;

azaz a sorsszegek sszege s az oszlopsszegek sszege azonos. 77. A skot n darab sokszgre s a kimarad (vgtelen) tartomnyra osztottuk fel. A darabok rendre d1 ; d2 ; ; dn msikkal rintkeznek egy{egy szakasz mentn (kt rsz kzs hatra nem llhat egynl tbb darabbl). Hny hatr{ szakasz van? 78. Egy ABC hromszg belsejt kisebb hromszglapok egyestre bontottuk gy, hogy brmely kt kis hromszg vagy egy teljes kzs oldal mentn, vagy egy

s sukban rintkezik, vagy egyltaln nem. (A nagy hromszg oldalaira is eshet kis hromszg s sa.) Fessk be az AB oldalon lv s sokat tetsz legesen pirosra vagy kkre, a BC olalon lv ket kkre vagy srgra, a CA{ra es ket pedig srgra vagy pirosra (gy A sak piros, B sak kk s C sak srga lehet); vgl az ABC belsejbe es ket is sznezzk, brhogyan. Igazold, hogy a nagy hromszg mellett legalbb egy ki sinek is mindhrom s sa supa klnbz sznt kapott! !

1

ai;j =

( )

XX

...

DEF. Egy grfban seresznynek neveznk kt, egy pontbl indul lt (azaz egy kt

lb l ll utat, ha gy tetszik). a) Ha G{nek n pontja van, melyekre rendre d1 ; d2 ; dn l illeszkedik, hny

seresznye van G{ben? b) n pont, e l grfban legalbb hny seresznye van? ! 80. Tegyk fel, hogy egy n pont, e l grfban nin s hromszg. a) Egy l hny seresznyben szerepelhet?

79.

...

b) Mutasd meg, hogy a grfban legfeljebb

81. 82.

) Bizonytsd be, hogy

2 e n4 .

e(n

2

2) seresznye lehet!

Tegyk fel, hogy G{ben nin s ngy pont kr! Mutasd meg, hogy a) legfeljebb n seresznye lehet! n b) e n3=2

1 2

2 + 14

G{ben

Tizenht tuds hrom tmrl folytat levelezst egymssal (barmely kett mindig ugyanarrl, de egy harmadik rhat nekik klnbz ekr l). Bizonytsd be, hogy van kztk hrom, akik pronknt ugyanarrl leveleznek! 83. Legyen irra ionlis szm! Egy egysgnyi kerlet kr tetsz leges pontjbl indulva mrj fel egyms utn hosszsg veket! Bizonytsd be, hogy a vgpontok halmaza sr lesz a krvonalon (azaz brmely pozitv hosszsg vbe esik vgpont). !

17


1.5. Binomilis egytthatk 1

84. Hnyflekppen lehet sorbarakni kt {est s

(Posa Lajos nyom an)

n

2 db. 0{t?

!

85. Egy krmrk zses bajnoksgon n sapat indul. Mindegyik mindegyikkel jtszik egyszer egyikk, egyszer msikuk plyjn. Hny me

sb l ll a bajnoksg? ! 86. Ugyanez a krds, ha minden mrk zst a Npstadionban rendeznek (a nagy rdekl ds miatt), s gy persze mindenki mindenkivel sak egyszer jtszik.

87. Egy n tag trsasgban mindenki mindenkit kzfogssal dvzlt. Hny kzszorts trtnt sszesen? 88. Mi kze egymshoz az el z ngy feladatnak?

1

89. Hnyflekppen lehet sorbarakni hrom {est s

n

3 db. 0{t?

!

90. Az ultit hrman jtsszk. Bajnoksgot rendezel, ahol az n jtkos mindegyike | az eslyegyenl sg jegyben | minden lehetsges kt ellenfl ellen asztalhoz l s jtszik egy partit. sszesen hny jtszmt jtszanak a rsztvev k?

91. Mdostsuk a Lott szablyokat! Tegyk fel, hogy a 90 szmbl hrmat hznak ki. Hny szelvny kell a biztos telitallathoz? 92. Hny hromelem rszhalmaza van egy n{elem halmaznak? 93. Mi kze egymshoz az el z hrom feladatnak? 94. Hny LOTT szelvnyt kell kitltened, hogy biztos ts tallatod legyen?

A Pas al{hromszg 95. Ismteljnk egy kis elemi algebrt: a) x y 2 ? b) x y 3 ?

) x y 4 ? d) Mennyi lesz x2 y 3 egytthatja

( + ) = ( + ) = ( + ) =

(x + y)5{ben ?

96. Sorold fel a) az fa; b; g halmaz 0,1,2,3{elem rszhalmazait! b) az fa; b; ; dg halmaz 0,1,2,3,4{elem rszhalmazait! Melyikb l hny darab van?

) Hny ktelem rsze van az fa; b; ; d; eg halmaznak? d) Ezek kzl hnyban van benne az e? s hnyban nin s? Jelljk Ckn {val xn k y k egytthatjt a Pas al{hromszg:

(x+y)n {ben! Ezekb l a szmokbl kszl

18

Elekes Gy:

1

1

1

1

5

6

1

1

1

2

3

4 15

1

10

3

6 20

10

1 4 15

1

1

5

6

0. 1. 2. 3. 4. 5. 6.

1

sor sor sor sor sor sor sor

1 1 7 21 35 35 21 7 1 stb. 97. Mutasd meg, hogy a Pas al{hromszgben minden szm a felette lv kett

sszege, azaz Ckn Ckn 11 Ckn 1

=

+

>jabb jells: n egy n elem halmaz k elem rszhalmazainak szma. k 98. A fenti de n i szerint a) mennyi n , n , n n s n ? n b) Ht n , n , n n s n n ?

:=

0 1 2 3

3

1

2

x jellst hasznlva rd fel, hny olyan k{elem rsze van az f1; 2; . . . ; ng y

99. Az halmaznak, a) amiben az n benne van? b) s amiben nin s benne?

) Adj kl snsen egyrtelm megfeleltetst az f ; ; ; ng halmaz k {elem rszei (k rgztett) illetve az f ; ; ; n g halmaz k s k elem rszei kztt! d) Mutasd meg, hogy a rszhalmazok szmra a Ckn {khoz hasonl sszefggs igaz:

1 2 ...

n k

=

n k

1 2 ...

1

1 + 1

n

k

1

1

n 100. Mutasd meg, hogy minden k n szmprra Ckn k 101. (folytats) Igazold, hogy a fenti kt mennyisg kzs rtke

0

n! k! (n k)!

=

= n (n 1) . k. .! (n

!

k + 1)

102. Hnyflekppen olvashatod ki a MATEMATIKA szt a kvetkez bra bal fels

sarkbl a jobb alsig haladva? M A T E

A T E M

T E M A

E M A T

M A T I

A T I K

T I K A

(0 0)

103. Egy ngyzetr s ; pontjbl r segyenesek mentn jobbra vagy felfel lpve hnyflekppen juthatsz el az u; v pontba? (u; v )

( )

0

19


A binomilis egytthatk azonossgai

A kvetkez feladatokat prbljtok Ckn ill. n k de n ijt hasznlva megolda n ni. ltalban mkdik az k {ra vonatkoz kzvetlen kplet is; a teljes induk i pedig jl olajozott masinaknt ontja a bizonytsokat. Kombinatorikus szemlletnket azonban a rszhalmazos de n i hasznlata fejleszti legjobban. 104. Mutasd meg, hogy a Pas al{hromszg szimmetrikus! A fenti instruk i szellemben teht lsd be, hogy a) x y n {ben xn k y k {nak s xk y n k {nak ugyanannyi az egytthatja. b) egy n elem halmaznak ugyanannyi k {elem rsze van, ahny n k {elem. Aki ezeken tlmen en expli it kpletet s/vagy induk it is tud hasznlni, az sszesen ngy bizonytst ismer majd. !

( + )

105. Mennyi

(

n + n + . . . + n + . . . + n + n? 0 1 n 1 n k

(Polinommal is, rszhalmazzal is oldd meg! )

)

!

106. Mutasd meg, hogy minden nem-res halmaznak ugyanannyi pros elemszm rsze van, ahny pratlan! ! n n n n n 107. ?

1 + 2

. . . + ( 1) n = k + 1 n n + 1 108. Bizonytsd be, hogy k ! k + k +... + k = k +1 109. Az 1+ i komplex szm hatvnyainak segtsgvel adj zrt formult a kvetkez

0

sszegekre: a) b)

n 0 n

1

n + n 2 4 n + n

3

5

. . . + ( 1)k 2nk + . . . . . . + ( 1)k 2k n 1 + . . .

(Rszhalmazos megoldst is keress, legalbb nhny spe ilis tpus n{re! )

Igazold az albbi azonossgokat! 110. 111. 112. 113. 114.

n n 1. k k 1 n k + 1 n . k 1 k m = n n k . k k m k 4n < 2nn < 4n. 2n + 1 n = k n = k n m

n X k=0

m + k = m + n + 1. n k

!

20

Elekes Gy:

n X

n k

= n2n 1. k=0 X 116. ( 1)k 2k4m+ 1 = 0. k X r s r + s 117. k n k = n . 115.

k

k

118. 119.

120. 121. 122. 123.

124.

! ! !

r s r + s k n+k = r+n .

X

k

X

n k = n 2n m . m k m k X 2 n = 2n. n k k

r k s + k = r + s + 1 . m n m+n+1

X

k

s k kr ks = s r + r

X

k

X

k

1

1 .

r k s + k = r + s + 1 . m s r m

( 1)k 42mk = ( 4)m.

X

k

Nhny gyakorl feladat . . .

125. Egy vfolyam 50 lny s 30 hallgatja ttag kldttsget vlaszt, spedig hrom lnyt s kt t. Hnyflekppen tehetik ezt? ! 126. (folytats) An sa s Ber i ppen haragban vannak; nem akarnak egytt bekerlni. Hnyfle lehet a deleg i? 127. Hny szigoran monoton nv f ; ; ; k g 7! f ; ; ; ng fggvny van? ! 128. Egy r r{es pontr s s saibl hnyflekppen vlaszthatjuk ki egy tengely{ prhuzamos tglalap ngy s st? 129. Egy tra kban k fajta kpeslap kaphat. Hnyflekppen kldhetnk bel lk n bartunknak 2{2 klnbz t? 130. Egy konvex n{szg semelyik hrom tlja nem megy t egy ponton. Hny metszspontjuk van az tlknak szesen? 131. n klnbz magassg ember hnyflekppen tud kt n{hosszsg sorba llni gy, hogy az els sorban mindenki ala sonyabb legyen a hts sorban a megfelel helyen llnl? ! 132. Hrom dobko kval dobva a mutatott szmok sszegt gyeljk. Melyik szm a leggyakoribb?

1 2 ...

2

1 2 ...

21


1.6. Ha egy elem tbbszr is szerepelhet . . . 133. Mutass kl snsen egyrtelm megfeleltetst a) az 1 s 2 szmjegyekb l kpezhet ttag monoton nv sorozatok s az 1,2,3,4,5 s 6 jegyekb l ll, ugyan sak ttag szigoran monoton nv

sorozatok kztt! b) az n tag a1 ; a2 ; ; an ai k monoton nv s az ugyan sak n tag b1 ; b2 ; ; bn bi k n szigoran monoton nv sorozatok kztt! k db. van!

) Mutasd meg, hogy a b) alattiakbl n n

...

... (1

(1

+

) 1)

+

1

134. Melyik kszletben van tbb domin s mirt: a) 0{tl 8{ig szmozva, duplk is vannak; b) 0{tl 9{ig szmozva, duplk nin senek. 135. Hny olyan tjegy szm van, amelyben egyik szmjegyet sem kvet nla kisebb? 136. Egy gyereknek 10 rggumit akarsz venni; goly, Donald s lapos van. Hnyflekpp vlogathatsz?

DEF. Jellje a tovbbiakban nk azt, hnyflekppen lehet n elemb l k{t kivlaszta-

ni, ha a sorrend nem szmt, de az elemek tbbszr is szerepelhetnek. Elnevezse

ismtlses kombin i. 137. Mutassuk meg, hogy

n

k

= n + kk 1.

138. tfajta kpeslapot rulnak. Hnyflekpp vehetnk 12 -t? 139. Legfeljebb h any tagja van egy

k valtozos homogen d{edfoku polinomnak?

140. k ember kztt akarunk bizonyos sszeget sztosztani. Keress kl snsen egy-

rtelm megfeleltetst a kvetkez kt vltozat kztt: a) n forintot osztunk ki tetsz legesen (az is lehet, hogy egyesek semmit sem kapnak); b) n k forintot osztunk ki gy, hogy senki ne tvozzon res kzzel.

+

141. (folytats) Mennyi a lehet sgek szma az el z feladatban? 142.

143.

k fle kpeslapod van, spedig az i{edikb l ai darab (i k). Hnyflekppen kldhetjk el az sszeset n bartunknak? (Lehet, hogy valaki nem kap; az is lehet, hogy valakinek egy fajtbl tbbet is kldnk.)

Hnyflekpp lehet a pol on lv n knyvb l k db{ot levenni, ha szomszdosakat nem szabad? !

22

Elekes Gy:

1.7. A szita{mdszer 144. Hny olyan pozitv egsz szm van, mely osztja a melyiknek?

1040 s 2030 szmok vala!

145. 12 knyv kzl 6 nem rdekes, 4 rosszul van fzve, 3 rosszul fztt knyv nem is rdekes. Hny jl fztt rdekes knyvnk van? 146. Egy osztly 30 tanulja kzl a matematikt 12 a matematikt s a zikt 5 a zikt 14 a matematikt s a kmit 4 a kmit 13 a zikt s a kmit 7 szereti. Hny tanul nem kedveli egyiket sem?

mindhrmat 3

!

147. (folytats) Milyen algebrai mveletekkel szmolhat az el z feladat eredmnye a szmadatokbl? !

Ismt egy tpus{hiba. Hnyflekppen tudunk eltenni 20 klnbz tartalm paprlapot egy piros, egy srga, egy kk s egy zld irattartba gy, hogy mind a ngybe legalbb egy jusson? (Egy dosszin bell a sorrend kzmbs.) Megolds": Tegynk a ngy helyre egyet{egyet! Erre n n n n lehet sg van. A maradkot osszuk el tetsz legesen! Ez n 4 fle mdon trtnhet. Eredmny": n n n n n 4.

(

(

1)(

2)(

3) 4

1)(

2)(

3)

4

...

Termszetesen itt is | mint az I.rsz 1.1. ( Dobjuk ki ") pontjban | az a baj, hogy bizonyos eseteket tbbszr szmoltunk. Pl. ha a piros irattartba eredetileg az 1{es paprt tettk, s ks bb odakerlt, mondjuk, a 8{as, ez ugyanaz, mintha eredetileg tettk volna oda a 8{ast s ks bb az 1{est. Jellje a tovbbiakban jX j az

X

halmaz elemszmt!

A szita{formula: Kijellted az A halmaz n rszhalmazt, A1 ; A2 ; et. Azon elemek szma, amelyek egyik Ai {ben sin senek benne,

jAj

X

jAi j +

X

jAi \ Aj j

X

. . . ; An {

jAi \ Aj \ Ak j +. . .+( 1)n jA1 \ . . . \ An j

148. Igazold a szita{formult! 149. (folytats) Hny elem van benne legalbb egy Ai {ben?

!

23


150. Oldd meg helyesen a szita{formula el tti irattarts feladatot!

151. Egy kerek asztal krl l n ember kzl hnyflekppen vlaszthat ki hrom, pronknt nem szomszdos? 152. Egy zskban 10 pr ip van. Hnyflekppen vehetnk ki bel le 6 darabot, hogy ne legyen kztk egy pr sem? 153. A ruhatrban 10 ember hnyflekpp kaphatja vissza a kabtjt, ha semelyiknek sem jut a sajtja? 154. Levelet rsz n bartodnak, de | miel tt a mr meg mzett bortkokba tennd

ket | elalszik a villany. Vletlenszeren elhelyezve ket mi a valsznsge, hogy egyik bartod sem a neki rt levelet kapja? 155. Hny, ezernl kisebb termszetes szm van, mely nem oszthat a 2, 3, 5, 7 szmok egyikvel sem?

2

156. Hny n bets sz kpezhet az a1 ; a1 ; a2 ; a2 ; betk nem lehetnek szomszdosak?

. . . ; an; an betkb l, ha azonos

157. Hny rkpezse van egy n elem halmaznak egy m elem halmazra? (rkpezs: az m elem halmaz minden eleme legyen kpe az n elemb l legalbb egynek.) 158. Mutasd meg, hogy

n! = nn

159. 160.

n

n i 1 (n 1) + . . . + ( 1)

n (n i)n + . . . + ( i

1)n

1

n

n

1

Egy n elem halmazt hnyflekppen lehet m darab (nem felttlenl diszjunkt) k elem rsznek egyestseknt el lltani, a) ha a rszhalmazok sorrendje szmt s lehetnek azonosak is. b) ha supa klnbz rszhalmaz kell s a sorrend nem szmt.

...

Adottak egy X alaphalmaz A1 ; A2 ; An rszhalmazai. Hny elem tartozik az Ai {k kzl a) pontosan egybe? b) pontosan kett be?

) pontosan k {ba? d) legalbb k {ba? ! pr kr szmhoz hny nla kisebb, hozz relatv prm van? (a 161. Az n p1 k1 p2 k2 pi {k klnbz primek, ki .)

=

162. 163.

...

Mutasd meg, hogy egy

k{nak polinomja!

n

1

pont

G

grf

k

sznnel val j sznezseinek szma

Hnyflekppen vghatunk egy r elem halmazt k darab nem{res rszre? (A reszek nin senek szamozva; sak a tartalmuk k ulonb ozteti meg } oket.) !

24

Elekes Gy:

1.8. Kt plda rekurziokra A Fibona

i{szmok DEF. Az F1 = F2 = 1 ; Fn = Fn 1 + Fn 2 rekurzival de nilt szmsorozat elemei a Fibona

i{szmok (nha lszer az F0 = 0{t is bevenni):

1; 1; 2; 3; 5; 8; 13; 21; . . .

164. Hnyflekpp lehet felmenni n lp s fokon, ha egyszerre egy vagy kt fokot lphetnk? 165. Hny olyan n{hossz sorozat kpezhet az a s a b betkb l, melyben nin sen kt szomszdos b? ! 166. Mutasd meg, hogy a szomszdos Fibona

i{szmok relatv prmek! ! 167. Bizonytsd be, hogy minden m -re van m{mel oszthat Fibona

i{szm! ! 168. Bizonytsd be, hogy ha k j n, akkor Fk j Fn ! 169. Bizonytsd be, hogy minden termszetes szm egyrtelmen felrhat klnbz , nem szomszdos Fibona

i{szmok sszegeknt! 170. Keress olyan ai mrtani sorozatot, amely kielgti az an an 1 an 2 rekurzit! (Az azonosan 0 sorozaton kvl is van ilyen!) ! 171. (folytats) Mutasd meg, hogy az ilyen sorozatok tetsz leges lineris kombin ii is jk lesznek! 172.
i{sorozatot kt mrtani sorozat lineris kombin ijaknt! 173. A pol on lv n knyvb l nem vehetnk le szomszdosakat. Hnyflekppen vlaszthatunk a) nhnyat (tetsz leges szmt)? b) pontosan k darabot?

( )

=

+

Bizonytsd be a kvetkez egyenl sgeket: 174. 175. 176. 177. 178.

179.

Fn+2 =

X

k

n k + 1 k

Fn+1 Fn 1 F2n = ( 1)n . F1 + F2 + . . . + Fn = Fn+2 1. Fmk+m = Fmk 1 Fm + Fmk Fm+1 . p n 1 1 p5 n p5 2 Fn = p15 1+2 5 . Milyen szmok alkotjk az

mtrixot?

!

1 1 n 1 0

25


Keressnk kpleteket! Hatvnyok sszegei Bizonyra mindenki ismeri az els

n termszetes szm sszegt:

1 + 2 + . . . + n = n(n2+ 1) Valsznleg kzismert az is, hogy magasabb hatvnyokra is van hasonl kplet, ha nem is tudja ket mindenki fejb l:

n + 1) 12 + 22 + . . . + n2 = n(n + 1)(2 6 2 13 + 23 + . . . + n3 = n(n2+ 1) rdekes, hogy az utbbi ppen a legels ngyzete. Az is feltnhet, hogy a hrom kplet n nagy rtkeire krlbell

n2

2

;

n3

4

n 3 ill: 4 :

DEF. Jelljk f r (n){nel az els n darab r{edik hatvny sszegt:

f r (n) = 1r + 2r + . . . + nr :

180. 181.

Ennek tulajdonsgt (nagysgrendjt, als{fels be slst s a pontos rtk zrt alakjt) vizsgljuk a tovbbiakban. Bizonytsd be, hogy

f r (n) nr+1

! r +1 1 ; ha n ! 1:

!

(folytats) Mutasd meg, hogy

nr+1 r+1

r+1

f r (n) (n r++1)1 :

!

26

Elekes Gy:

Klnbsg{sorozatok. Egy egyszer trkk. DEF. Legyen a0 ; a1 ; a2 ; . . . ; an . . . tetsz leges sorozat. Az a1 a0 ; a2 a1 ; . . . ; an+1 an ; . . . sorozatot az an klnbsg{sorozatnak nevezzk. Jellse

an = an+1 an: Hasonlan de nilhat a 2 an = an = an+1 an = an+2 2an+1 + an sorozat is, s ltalban k an = k 1 an: Ezzel a jellssel 0 an = an s 1 an = an . 182. Tltsd ki (a {kat az ai {kkel kifejezve) az albbi tblzatot: 0 an : a0 a1 a2 . . an 2 an 1 an 1 an : a0 a1 a2 . . an 2 an 1 2 an : 2 a0 2 a1 2 a2 . . 2 an 2 3 3 3 3 an : a0 a1 a2 . .

n an :

n an

(Ne felejtsd el az als n an {et is kifejezni az ai {kkel!) ! 183. (folytats) s ha a fenti hromszgben az elemek nem a felettk lv k klnbsgei, hanem sszegei lennnek, mi kerlne az als sor kzepre? ! k 184. Fejezd ki an {et a sorok bal szln tallhat a0 {okkal! ! P i a0 n i . 185. (folytats) Mutasd meg, hogy an i! n n Megjegyzs: Ez a Taylor{formulra hasonlt, sak n hatvnyai helyett leszll" szorzatok szerepelnek benne. 186. Bizonytsd be, hogy ha an pr n r{edfok polinom, akkor an r {edfok polinom lesz.

(

=

1) . . .(

= ()

( 1)

187. (folytats) Igazold azt is, hogy r{edfok polinom azonosan 0. Megjegyzs: A fenti 184. feladat szerint

an =

+ 1)

X

(r+1){edik klnbsgsorozata !

n i

i a0 :

A 187. feladatbl pedig, ha valahonnan tudjuk egy sorozatrl, hogy polinom, akkor bizonyosak lehetnk abban, hogy elg sokadik diferen ii eltnnek, teht an fenti felrsban a tagok szma n-t l fggetlen. Ezek az szrevtelek sok konkrt sorozat n{edik tagjnak expli it felrst knnytik meg.


188. n ltalnos helyzet egyenes hny rszre vgja a skot? 189. n ltalnos helyzet sk hny rszre vgja a teret? 190. (folytats) Mit mondhatunk d dimenziban? 191. Keress kpletet f 4 n {re, a negyedik hatvnyok sszegre! 192. a) brzolhat-e brmely ngy halmaz krkkel (Venn{diagrammal)? b) n kr legfeljebb hny rszre osztja a skot?

()

27

! ! !

28

Elekes Gy:

2. fejezet

Grfok I.

2.1. Elemi grfelmlet 1. A hagyomny szerint Knigsberg (ma Kalinyingrd) polgrai egy napon nehz krdssel kerestk fel a vrosukban lak Leonhard Eulert: mondan mr meg nekik, mirt nem sikerl soha gy vgigstlniuk a Pregel foly ht hdjn, hogy mindegyiken sak egyszer keljenek t. (L. trkp.) Te tudnl vlaszolni nekik?

2.1. abra. A konigsbergi hidak. Megjegyzs: Valsznleg ez az els grfelmleti jelleg problma, aminek rsos nyoma maradt. A tovbbiakban ltalban irnytatlan lekb l ll grfokkal foglalkozunk, melyeknek vges sok pontjuk van. Ha nem mondjuk kln, akkor tbbszrs- s hurokleket nem engednk meg; sak egyszer grfokat vizsglunk.

Fokszmok DEF. Pont foka (vagy fokszma): a bel le indul lek szma. 2. Van{e olyan (legalbb kt pont) grf, amiben minden pont foka klnbz ?

!

3. Van{e olyan 9 pont grf, melyben a pontok foka rendre a) 7, 7, 7, 6, 6, 6, 5, 5, 5 b) 6, 6, 5, 4, 4, 3, 2, 2, 1

!

29


4. (folytats) Ht olyan 8 pont grf van{e, melyben a fokszmok 6, 6, 6, 6, 3, 3, 2, 2 ? ! 5. Mutasd meg, hogy brmely grfban a fokszmok ssszege az lszm ktszerese! 6. Tetsz leges grfban a pratlan fok pontok szma pros. ! DEF. Egy supa klnbz lekb}ol allo lsorozat sta, ha el nem ismetl}odik benne, es minden l egyik vgpontja az el z , msik vgpontja a rkvetkez llel kzs. Krsta, ha a kezd { s a vgpont azonos. DEF. >t, illetve kr: olyan sta (ill. krsta), melyben sem l, sem pont nem ismtl dik (kivve krben a kezd { ill. vgpontot). 7. Mutasd meg, hogy ha egy grf minden pontja legalbb msodfok, akkor a grfban van kr! ! 8. (folytats) Igazold, hogy ha minden pont foka legalbb k, akkor van k vagy tbb pont kr!

+1

sszefgg sg DEF. Egy grf sszefgg , ha brmely kt pontja kztt vezet t. (Egyetlen pontbl ll grfot sszefgg nek tekintnk.)

9. Igaz{e, hogy ha egy grf brmely kt pontja kztt van sta, akkor a grf sszefgg (azaz pontjai kztt van t is)? !

10. Mutasd meg, hogy ha a{bl vezet t b{be, b{b l pedig {be, akkor a{bl is vezet {be! !

DEF. A maximlis (azaz nem nvelhet ) sszefgg rszgrfokat a grf komponenseinek nevezzk. ( sszefgg grf maga egy komponens.) 11. Igaz{e, hogy minden pont benne van egy komponensben? 12. Lehet{e kt klnbz komponensnek kzs pontja?

13. 14.

DEF. 15. 16.

!

Megjegyzs: A grfok teht egy vagy tbb, kzs pont nlkli komponensre bomlanak. >gy is mondhattuk volna, hogy ezek a van a { b t" rel i szerinti ekvivalen ia{osztlyok. A 10. feladat ppen azt mondja, hogy e rel i tranzitv. Mutasd meg, hogy ha egy n pont grf minden pontjnak foka legalbb n, akkor a grf sszefgg ! ! (folytats) Igaz marad{e az el z llts, ha n fok pontokat is megengednk? ! A G grf komplementere az a G, melyben pontosan azokat az leket hzzuk be, amelyek az eredeti G{ben nem szerepelnek. Igaz{e, hogy vagy G, vagy a komplementere biztosan sszefgg ? ! Mutasd meg, hogy sszefgg grfbl elhagyva egy kr egyik lt a grf tovbbra is sszefgg marad.

2

1

30

Elekes Gy:

17. Igaz{e, hogy minden sszefgg grf tartalmaz krmentes sszefg rszgrfot? 18. Bizonytsd be, hogy brmely n pont sszefgg grfnak legalbb n

1 le van!

Euler{vonalak s {krstk DEF. Euler{krstnak (ill. Euler{stnak vagy Euler{vonalnak) neveznk 19. 20. 21.

egy krstt (ill. stt), ha minden let pontosan egyszer hasznl. Mutasd meg, hogy ha egy sszefgg grf egy krnek leit trlve a maradk grfnak van Euler{krstja, akkor az eredetinek is van! (folytats) Igaz-e ugyanez Euler{vonalra? Bizonytsd be, hogy egy sszefgg grfban a) akkor s sak akkor ltezik Euler{krsta, ha minden pont foka pros; b) akkor s sak akkor ltezik Euler{sta, ha legfeljebb kt pratlan fok pont van.

) mit mondhatunk azokrl a grfokrl, amelyekben pontosan egy pratlan fok pont van? d) Ha pontosan k pratlan fok pont van, akkor az elek halmaza k darab elidegen setara bonthat o. ! Egy vrosban, ahol az thlzat sszefgg , egyirny ut k is vannak. Mikor jrhatja be egy lo solaut az sszes ut t (spedig az egyirnyakat pontosan egyszer, j irnyban; a ktirnyakat pedig a kt svban egyszer oda, egyszer vissza) gy, hogy vgl a kiindulponton fejezze be a munkjt! (folytats) Mutasd meg, hogy ha minden ut a ktirny, akkor az el z bejrs mindig megoldhat! Iranytott es ir anytatlan eleket is tartalmazo gr af elei mikor j arhat ok be u gy, hogy mindegyiken (az ir anytatlanokon is!) pontosan egyszer menj unk vegig?

2

22.

23.

24.

Hamilton{utak s {krk

5 5

25. Bejrhat-e az {s sakktbla egy lval, a) ha nem kell ugyanott befejezned, ahonnan indultl; b) ha a kiindul mez re kell visszatrned? ! 26. (folytats) Ugyanezek a krdsek {es sakktblra. ! 27. Mutasd meg, hogy pratlan szm mez b l ll sakktblt nem lehet lval a fenti b) tpusban vgigjrni! 28. (folytats) De a {ast lehet! DEF. Hamilton{krnek (ill. Hamilton{tnak vagy Hamilton{vonalnak) neveznk egy krt (ill. utat), ha minden ponton egyszer megy t.

4 4

8 8

31


29. Igazold a kvetkez ket: a) ha a G grfban ltezik k darab pont, amelyeket trlve G tbb, mint k komponensre esik szt, akkor G{nek nin s Hamilton{kre; b) ha a grfban ltezik k darab pont, amelyeket elhagyva G mg k {nl is tbb komponensre esik szt, akkor Hamilton{tja sin s!

+1

Megjegyzs: Sajnos, ez a felttel nem elgsges! Nem is ismert ltalnos kritrium Hamilton{kr ltezsre. Elgsgesek, de nem szksgesek az albbiak: 30. Mutasd meg, hogy ha egy n pont grfnak legalbb

(n 1)(n 2) + 2 2

le van, akkor a grfban van Hamilton{kr! ! (Dira ttele): Ha egy n pont grf minden pontja legalbb n= fok, akkor a grfban van Hamilton{kr. 32. Petersen grf: egy t pont krben egy sillagtszg; a megfelel bels}o{k uls}o

s sok sszektve. M as de n io: a s u sok egy otelem} u halmaz ketelem} u reszhalmazai. Kett} ot osszek ot unk, ha a ketelem} u reszek diszjunktak. a) Mutasd meg, hogy a ket de n io ugyanazt a gr afot adja. b) Igaz-e, hogy a Petersen grf eltranzitv", azaz b armely el atvihet} o b armely m asikba a s u sok alkalmas permuta ioj aval?

) A Petersen grfnak nin s Hamilton kore, de b armely s u s at elhagyva a maradeknak mar lesz.

31.

2

!

( ... )

... ) ( ...

33. A Gk ir anytott graf s u sai azon k hossz u a1 ; a2 ; ; ak sorozatok, melyekre h ai 2 f ; ; ; ng. Elet uzunk a1 ; a2 ; ; ak {bol a2 ; ; ak ; ak+1 {be. ! (a) Biz.be: Gk {nak van ir anytott Euler-korsetaja. (b) Van-e ir anytott Hamilton{kore?

1 2 ...

(

)

2.2. Fk DEF. Az sszefgg , krmentes grfokat fnak nevezzk. (Egy pontbl vagy egyetlen DEF. 34. 35. 36. 37.

lb l ll grf is fa. Egy, ill. kt pont fa nin s is ms.) Ha krmentes, de nem felttlenl sszefgg , akkor erd . (Komponensei fk, azrt.) Rajzold fel az sszes 3, 4 ill. 5 pont ft! (Az izomorfakat | amelyek a pontok

serjvel egymsba mennek | sak egyszer.) Igaz{e, hogy minden legalabb ket s u s u fban van pontosan els fok pont? ! Mutasd meg, hogy minden n pont fa lszma n . ! (folytats) Hny le van egy n pont, k komponens erd nek? !

1

32

Elekes Gy:

38. Igaz{e, hogy

n pont, legalbb n l grfban van kr?

39. Bizonytsd be, hogy egy grf akkor s sak akkor fa, ha brmely kt pontja kztt pontosan egy t vezet.

40. Igazold, hogy tetsz leges n pont sszefgg grfra az albbiak ekvivalensek (azaz, ha brmelyik teljesl, akkor az sszes tbbi is)! i) krmentes ii) n le van iii) brmely pontpr kztt legfeljebb egy t vezet. 41. Igaz{e, hogy fban mindig van legalbb kt els fok pont? !

1

42. Hzzl be egy fba mg egy lt! Bizonytsd be, hogy gy mindig pontosan egy kr keletkezik! 43. Igazold, hogy fkban az sszes leghosszabb t egy ponton megy t!

44.

Ez az llts nem minden grfra igaz (br sokig gy sejtettk).

!

45. Jelljk egy fa legalbb harmadfok s sainak szmt x{szel, az els fokakt pedig y {nal! a) Mutasd meg, hogy ha a fnak legalbb kt pontja van, akkor y x ! b) Mikor llhat egyenl sg a){ban? !

+2

46. 47.

Mutass pldt olyan fra, amelynek egyetlen automor zmusa a helyben hagys! Brmely fa brmely automor zmusnak van vagy x pontja, vagy x le (azaz vagy helyben hagy egy pontot, vagy egy l kt vgpontjt fel serli).

48. d1 ; d2 ; . . . ; dn (ahol di 1) pontosan akkor lesz egy fa fokszm{sorozata, ha 49.

d1 + d2 + . . . + dn = 2(n 1). Egy fa T1 ; T2 ; . . . ; Tk reszf ai koz ul

b armely kett} onek van kozos s u sa. Bizonytand o: az osszesnek is van. Igaz-e hasonlo allt as s u sok helyett elekre? 50. A skon vges sok pont gy helyezkedik el, hogy minden pr tvolsga klnbz . Minden pontbl a hozz legkzelebb llhoz egyenes szakaszt hzunk. Keletkezhet-e gy zrt sokszgvonal? !

Feszt fk DEF. Egy sszefgg grf egy rszfjt (azaz olyan rszgrfjt, ami fa) feszt fnak

nevezzk, ha tartalmazza az eredeti grf minden pontjt. Ha egy nem sszefgg grf minden komponensnek vesszk egy{egy feszt fjt, feszt erd t kapunk.

51. Mutasd meg, hogy minden sszefgg grfnak van feszt fja! 52. (folytats) Minden grfnak van feszt erdeje.

!

53. Bizonytsd be, hogy sszefgg grfbl mindig elhagyhat egy pont (a bel le indul lekkel egytt) gy, hogy sszefgg grf maradjon! !

33


54. Mely sszefgg grfokbl radrozhatunk ki egy let (de pontokat nem!), hogy az sszefgg sg ne sznjn meg? ! 55. Igazold, hogy brmely, legalbb t pont grfban vagy a komplementerben van kr! ! 56. Hzzl be egy fba mg egy lt! Bizonytsd be, hogy gy mindig pontosan egy kr keletkezik! ! 57. Mutasd meg, hogy n pont, e l, k komponensb l ll grfban legalbb e n k klnbz kr van! ! 58. Bizonytsd be, hogy brmely n pont sszefgg grfnak legalbb n le van!

+

1

!

2 1

59. Mutasd meg, hogy brmely n pont grfra az albbiak ekvivalensek: i) nem tartalmaz krt s n le van. ii) sszefgg s krmentes. iii) sszefgg s n le van. iv) nem tartalmaz krt s brmely kt (szektetlen) pontjt sszektve pontosan egy kr keletkezik. v) sszefgg , de brmely lt trlve mr nem marad az. vi) brmely kt pontjt pontosan egy t kti ssze.

1

2.3. Ktszeres sszefgg sg DEF. A G(V; E ) grfnak sztvg pontja v 2 V , ha V {b l kihagyva v {t (s E {b l DEF. 60. 61. 62. 63.

64.

a v {re illeszked leket) az sszefgg komponensek szma n . Az sszefgg G grf ktszeresen sszefgg , ha jV j s nin s sztvg pontja. (A pontszmra vonatkoz felttel a kt pont, egyetlen l grfot zrja ki.) Bizonytsd be, hogy ktszeresen sszefgg grf brmely lt elhagyva a maradk sszefgg lesz. ! Ha G ktszeresen sszefgg , akkor brmely kt pontja kztt vezet kt, kzs bels pont nlkli t. (>gy is mondhatjuk, hogy brmely kt pont egy krn van.) Igaz-e, hogy ktszeresen sszefgg grfhoz jabb pontot vve s azt kt (klnbz ) rgivel sszektve jra ktszeresen sszefgg grfot kapunk? ! Legyen V1 a ktszeresen sszefgg G V; E grf pontjainak tetsz leges, legalbb kt elem rszhalmaza, v 2 V n V1 pedig tetsz leges pont. Mutasd meg, hogy vezet v {b l V1 kt klnbz pontjba egy{egy kzs bels pont nlkli t. (Csak v , a kezd pont azonos.) ! A kvetkez kt felttel kzl melyik egyenrtk a ktszeres sszefgg sggel? a) Brmely x; y; z ponthrmashoz van olyan x{y t, ami elkerli z {t; b) Brmely x; y; z ponthrmashoz van olyan x{y t, ami tmegy z {n. !

3

(

)

34

Elekes Gy:

65. Igaz-e, hogy brmely sszefgg grf brmely x; y; z 2 V ponthrmashoz van (t lk nem felttlenl klnbz ) p 2 V , melyb l vezet egy{egy kzs bels

pont nlkli t x; y s z mindegyikbe? (Valamelyik t lehet l nlkli, egyetlen pontbl ll is.) ! 66. Mutasd meg, hogy ktszeresen sszefgg grfban brmely x; y pontprhoz s e lhez van olyan x{y t, ami tartalmazza e{t! 67. (folytats) Igaz-e, hogy ktszeresen sszefgg grf brmely kt le egy krn van? DEF. sszefgg grfban blokknak nevezzk | a maximlis (nem b vthet ) ktszeresen sszefgg rszeket; | a sztvg leket. 68. Mutasd meg, hogy kt klnbz blokknak legfeljebb egy kzs pontja lehet!

!

2.4. Irnytott grfok Krmrk zsek 69. Mutasd meg, hogy egy ping{pong krmrk zs rsztvev i sorballthatk gy, hogy mindenki legy zte a kzvetlenl mgtte llt! (Azt nem kveteljk meg, hogy az sszes mgtte llt le kellett volna gy znie.) 70. (folytats) Bizonytsd be, hogy az ilyen sorrendek szma mindig pratlan! 71. Mutass pldt arra, hogy ha pontosan egy mrk zs mg htra van, akkor nem felttlenl ltezik ilyen sorballts! 72. Mutasd meg, hogy egy (legalbb h arom tag) ping{pong krmrk zs versenyz i | ha nin s olyan soportjuk, akik mindnyjan legy ztk a msik soport minden tagjt | krbellthatk gy, hogy mindenki legy zte a t le jobbra llt! ! 73. Adj eljrst (esetleg rj programot) ami tetsz leges teljes irnytott grfban megkeresi az alkalmas krbelltst, ha van; ha nin s, akkor mutat egy rossz" sztvgst. DEF. Pszeudogy ztesnek neveznk egy X versenyz t, ha mindenki, aki legy zte

t, kikapott legalbb egy olyan Y {tl, akit X legy z tt. (>gy is mondhatnnk, hogy X minden veresgrt kzvetve, valamely Y {on keresztl elgttelt vett.) 74. Mutasd meg, hogy minden krmrk zsnek van pszeudogy ztese! ! 75. (folytats) Ha nin s olyan versenyz , aki mindenkit legy ztt, akkor legalbb kt pszeudogy ztes van! ! 76. (folytats) Most kezd rdekes lenni az gy: az el z felttel mellett van hrom pszeudogy ztes is!

35


77. (folytats) Mr sak egy krds maradt: tudsz-e olyan vgeredmnyt produklni, ahol nin s ngy? 78. Mutass minden pszeudogy ztes!

n

6= 2; 4{re olyan vgeredmnyt,

amikor minden versenyz

!

Megjegyzs: A lehetsges krmrk zs{eredmnyek majdnem mind ilyenek! (Lsd a kvetkez feladatot.)

DEF. Vletlen krmrk zs: minden jtszmrl 1/2 valsznsggel, egymstl fggetlenl dntjk el, ki nyert.

79. Jellje pn annak valsznsgt, hogy egy n rsztvev s vletlen krmrk zsen nem mindenki pszeudogy ztes. Bizonytsd be, hogy pn ! ! !

0

Irnytott grfok + DEF. A G irnytott grfban az x pont be{foka (jele: d+ G (x), vagy rviden d (x)), illetve ki{foka (jele: dG (x), vagy rviden d (x)) az x{be bemen ill. onnan kifel irnytott lek szma. X

d+G (x) =

X

()

dG x . x2G x2G 81. Mely grfok irnythatk gy, hogy minden pontba ugyanannyi l menjen be, mint ahny kijn? (Ez a kzs rtk klnbz pontokra klnbz lehet!)

80. Mutasd meg, hogy

82. (Euler{krsta) Mely irnytott grfok jrhatk be gy, hogy minden len (j irnyban) pontosan egyszer vgigmenve a kiindulpontba jussunk vissza?

83.

Minden irnytott grfban van olyan V1 fggetlen ponthalmaz, hogy V n V1 minden pontja V1 valamelyik pontjbl legfeljebb kt lpsben elrhet . (fggetlen ponthalmaz: nin s kztk l.)

Er s sszefgg sg. DEF. Egy irnytott grf er sen szefgg , ha brmely pontjbl brmely msikba vezet irnytott t. (Ez minden pontprra kt felttel: egy oda, egy vissza.) sszefgg , ha az lek irnytst elfelejtve irnytatlan grfknt sszefgg

lesz; ennek semmi kze az irnytott utakhoz.

84. Keress mdszert irnytott grf er s sszefgg sgnek vizsglatra!

85. Egy er sen sszefgg grf pontjait kt diszjunkt, nem-res osztlyba osztottuk. Mit mondhatunk a kt rsz kztti lekr l? ! 86. Tudsz-e ilyen tpus szksges s elgsges felttelt az er s sszefgg sgre? !

87. Mutasd meg, hogy ha egy irnytatlan grf brmely lt trlve a grf mg mindig sszefgg marad, akkor irnythat gy, hogy er sen sszefgg legyen.

36

Elekes Gy:

2.5. Vegyes feladatok 88. Melyek azok a grfok, amelyekben brmely kt lnek van kzs pontja? 89. Hny klnbz grf adhat meg az

1; 2; . . . ; n pontokon?

! !

90. Nevezzk egy sszefgg grf kt pontja kozotti tvolsgnak az ket sszekt legrvidebb t hosszt. Mutasd meg, hogy ez eleget tesz a hromszgegyenl tlensgnek! 91. (folytats) Igazold ugyanezt arra az esetre is, ha tvolsgnak a leghosszabb t hosszt nevezzk! 92. Ha egy sszefgg grf minden pontja msodfok, akkor a grf egyetlen krb l ll. 93. Milyen komponensekb l llhat egy grf, ha minden pontjnak foka legfeljebb kett} o? ! 94. Mutasd meg, hogy sszefgg grf brmely kt leghosszabb tjnak van kzs pontja! !

95.

Tegyk fel, hogy egy grf minden pontjnak foka legalbb hrom. a) Mutasd meg, hogy a grfban van pros szm pontbl ll kr. b) Nin s olyan m > egsz, amivel minden kr hossza oszthat lenne.

) Mutass olyan pldt, amiben van pratlan pont kr! d) Igaz{e, hogy mindig lesz a grfban pratlan kr is?

2

DEF. Az A halmaz P part ija olyan H1 ; H2 ; . . . halmazrendszer, melyre

96.

S

!

Hi = A Hi \ Hj = ;, ha i 6= j . Nevezzk az A alaphalmaz P1 ; P2 ; . . . part irendszert szeparlnak, ha brmely x; y 2 A{ra van i, hogy x s y a Pi part i klnbz osztlyaiba esik. Bizonytsd be, hogy tetsz leges n elem A halmaz brmely P1 ; P2 ; . . . ; Pn sze-

s

parl part irendszerb l kihagyhat egy Pi gy, hogy a maradk mg mindig szeparl legyen.

DEF. Legyen adva a G(V; E ) grf, jV j = n s kt pont: s; t 2 V gy, hogy (s; t) 2 E . A grf s{t szmozsa g : V ! f1; 2; . . . ; ng, ha

g(s) = 1; g(t) = n; 8y 6= s; t 9x; z 2 V

97.

hogy

(x; y) 2 E; (y; z) 2 E s g(x) < g(y) < g(z):

Minden ktszeresen sszefgg grfnak van s{t szmozsa.

37


2.6. Fokszmsorozatok realiz ija 0

...

=

+

0

102.

P

...

98. Legyen d1 ; d2 ; ; dn termszetes szmokbl ll sorozat, melyre di pros. Konstrulj olyan | esetleg tbbszrs- s hurokleket is tartalmaz | n pont grfot, melyben az i{edik pont foka ppen di (a huroklek ktszeresen, azaz mindkt vgkkel szmolandk). ! 99. Legyenek a a a s b b b termszetes szmok, men 1 2 m P 1 P2 lyekre ai bj . Igazold, hogy ltezik (esetleg tbbszrs lt is tartalmaz) m n pont pros grf, melyben a fels pontok fokszmai ppen az ai {k, az alsk pedig a bj {k. P 100. Legyen d1 ; d2 ; ; dn termszetes szmokbl ll sorozat, melyre di X pros s minden i n{re di dj . Konstrulj olyan | esetleg tbbszrsj 6=i let is tartalmaz | hurokl nlkli n pont grfot, melyben az i{edik pont foka ppen ni . 101. Mely d1 d2 dn fokszm{sorozatok valsthatk meg egyszer gral?

...

...

...

!

...

...

Mely a1 ; a2 ; ; an s b1 ; b2 ; ; bm fokszmsorozat{prok valsthatk meg egyszer pros gral? 103. Legyen d1 d2 dn n olyan sorozat, melyre P di n . Mutasd meg, hogy ltezik n pont fa ilyen fokszmokkal! !

1

...

= 2(

1)

2.7. Pros grfok. A K nig{Hall ttelkr. DEF. A G grf ktosztly, ha pontjai kt rszre oszthatk gy, hogy egyik rszen

bell se menjen egyetlen l sem. (Minden l a kt rsz egy{egy pontjt ksse ssze.) 104. Adj mdszert (esetleg rj programot) annak eldntesre, hogy egy grf ktosztly{e! Bizonytsd is be, hogy mdszered helyesen mkdik mind pozitv vlasz (ha az eredmny egy j kettoszts) mind negatv vlasz esetn (ha az eredmny az, hogy nin s ilyen)! DEF. G pros grf, ha minden kre pros (azaz nin s benne pratlan kr). Spe ilisan a krmentes grfok (fk s erd k) szksgkppen prosak. 105. Bizonytsd be, hogy egy grf akkor s sak akkor ktosztly, ha pros. (Mivel teht a kt fogalom azonos, elg egy elnevezs; a rvidebb "pros grf"{ ot szoks hasznlni.) !

38

106.

Elekes Gy:

2

Mutasd meg, hogy brmely e l grf tartalmaz legalbb e= l pros grfot!

!

...

...

107. Legyenek a2 an s b1 b2 bm termszetes szmok, meP a1 P lyekre ai bj . Igazold, hogy ltezik (esetleg tbbszrs lt is tartalmaz) m n pont pros grf, melyben a fels pontok fokszmai ppen az ai {k, az alsk pedig a bj {k. Sokmindent lehet pros grfokkal brzolni: gyrtk s megrendel k kzti szlltsokat; egy halmaz elemei s bizonyos rszhalmazai kztt az "x eleme a H rszhalmaznak" rel it; k s lnyok kztt a "ki{kinek{tetszik" (ebb l irnytott grf lesz) vagy a "kl snsen tetszenek egymsnak" rel it (utbbibl irnytatlan pros grf lesz).

+

=

Prostsok (fggetlen lrendszerek). 108. Egy vllalatnl ht plyz jelentkezett hat res munkahelyre (szmozzuk ezeket 1{t l 6{ig); egy ember tbb helyre is: Aladr az 1 {es munkahelyre Bla az 1,6 {os munkahelyre Csaba a 2,3,4 {es munkahelyre Dani a 2,5 {s munkahelyre Erzsi a 3,4,5 {s munkahelyre Feri a 1,6 {os munkahelyre Gza a 6 {os munkahelyre (a) brzold a helyzetet pros gral (b) dntsd el, hogy betlthet {e mind a hat munkahely (egy ember sak egy helyre kerlhet). Ha nem mind, akkor hny tlthet be? Indokold a vlaszt! ( ) javt{e valamit, ha Feri meggondolja magt s a 2{es munkahelyet is hajland elfogadni? DEF. a G grf leinek egy F rszhalmazt fggetlen leknek vagy rszleges prostsnak nevezzk, ha kzlk semelyik kett nek nin s kzs vgpontja. 109. (folytats) Egy munkakzvett nl hat ember jelentkezett. Nyol lls jhet szba: kos 1,2,3,4,6. munkahely Bandi 2,5,8. munkahely Csilla 2,5. munkahely Dra 2,8. munkahely Ern

5,8. munkahely Feri 1,2,3,4,7. munkahely Adj meg egy lehet legnagyobb fggetlen lrendszert! Indokold meg, mirt nin s nagyobb!


39

110. Mutasd meg, hogy ha nhny (mondjuk k) jelentkez egyttesen sak k {nl kevesebb helyre plyzik, akkor nem lehet mindenkit elhelyezni! (Hasonlan: ha nhny (mondjuk k) helyre egyttesen sak k {nl kevesebb jelentkez plyzik, akkor nem lehet minden helyet betlteni.) 111. Egy harmadik gnl ht helyre sak hatan plyznak: Anita 1,2 Bea 2,3 Cirill 3,4 Diana 4,5 Elemr 5,6 Fri i 6,7

munkahelyre munkahelyre munkahelyre munkahelyre munkahelyre munkahelyre

A f nk mr belenyugodott, hogy gy nem lehet az sszes helyet betlteni. El is dnttte, hogy a hat emberb l ki hova kerl: A{1, B{2, C{3, D{4, E{5, F{6. Ekkor rkezik a posts egy tvirattal: "megpaalyaazom a 2--es munkahelyet stop geeza stop stop". A fenti hat fggetlen lb l melyikeket serli ki a f nk s mely msikakra?

Hall felttele s ttelei. DEF. Azt mondjuk, hogy a G(V1 ; V2 ; E ) pros grf V1 osztlya teljesti a Hall{

felttel{t, ha tetsz leges k termszetes szmra V1 brmely k db. pontja egytt legalbb k db. V2 {belivel van sszektve. DEF. Legyen F fggetlen (nem felttlenl maximlis) lrendszer a G grfban. F {re nzve alternl (="vltakoz") egy t (vagy kr), ha lei felvltva F {beliek ill. F {en kvliek. (Pl. t pont kztt ngy egyms utni l: f1 ; e1 ; f2 ; e2 , ahol fi F {beli, ei nem F {beli; vagy akr kt pont kztt egy F {en kvli l nmagban is alternl t) 112. Legyen F1 fggetlen lrendszer G{ben. Mutasd meg, hogy (a) ha van F1 {re nzve alternl kr, akkor van msik, F2 fggetlen lrendszer is G{ben, ami ugyanannyi lt tartalmaz, mint F1 . (b) ha van F1 {re nzve alternl t, ami F1 ltal nem fedett ponttal kezd dik s vgz dik, akkor van F1 {nl tbb lb l ll F2 fggetlen lendszer is G{ben. ! 113. Legyen F fggetlen lrendszer a G pros grfban. G egyik ponthalmaza legyen V1 , a msik V2 (nem felttlenl ugyanannyi pontak). Azon V1 {beli pontok halmazt, amelyekre nem illeszkedik F {beli l, jelld C1 {gyel; a megfelel V2 { belieket C2 {vel. Nevezhetjk ezeket teltetlen vagy fedetlen pontoknak. (a) mutasd meg, hogy ha C1 {b l vezet alternl t C2 {be, akkor van F {nl nagyobb fggetlen lrendszer a grfban. (b) Jelld a C1 {en kvli, de abbl alternl ton elrhet V1 {beli ill. V2 {beli pontok halmazt B1 {gyel ill. B2 {vel; A1 ill. A2 pedig legyen a kt maradk

40

Elekes Gy: (vagyis amik nem rhet k el alternl ton). F lei teht rszben A1 {b l A2 {be, rszben B1 {b l B2 {be vezetnek. ( ) Tedd fel mg azt is, hogy a nem{res C1 {b l nem vezet alternl t C2 {be. Mutasd meg, hogy ekkor V1 nem teljestheti a Hall{felttelt! ( tlet: mivel lehetnek sszektve a B1 [ C1 {beli pontok?) !

(

)

114. (folytats) Adj mdszert (esetleg rj programot) pros grf maximlis prostsnak keressre! Igazold, hogy mdszered mind pozitv, mind negatv vlasz esetn helyes eredmnyt ad! Megjegyzs: pros grf trolsa vagy l{listval, vagy n m{es ktdimenzis tmbbel (mtrix{szal) trtnhet: a V1 {beli i s V2 {beli j pontokra a tmb G i; j eleme: ; ha van i; j l; G i; j ; ha nin s.

( )

( ) = 01

( )

Hall ttele: Pros grfban a V1 ponthalmazt fed prosts ltezshez a Hall{felttel szksges s elgsges is.

115. A 113. feladat felhasznlsval bizonytsd be Hall ttelt!

!

Megjegyzs: a fenti gondolat; az eljrs tlete s abb l Hall ttelnek bizonytsa K nig Dnest l szrmazik. Hall eredeti bizonytsa V1 elemszma szerinti teljes induk i volt: 116. Keress induk is bizonytst Hall ttelre! [tlet: az induk is lps sorn vlassz szt kt esetet aszerint, hogy (i) V1 minden nem{res valdi rszb l tbb V2 {belibe megy l, mint ahny eleme e rsznek van, illetve (ii) van olyan nem{res valdi rsz, ami a Hall{felttelt pontos egyenl sggel teljesti.℄

Gyakorl feladatok

1; 2; 3; 4; 5; 6; 7; 8g. Az els osztly

117. A G pros grf s u sai fa; b; ; d; e; f; g; hg s f pontjainak szomszdai: a: b:

: d: e: f: g: h:

f3, 5, 6g f2, 3, 4, 7g f3, 5g f1, 4, 8g f3, 6g f1, 2, 7, 8g f1, 3, 5, 8g f5, 6g

Keresd meg G egy maximlis prostst, tovbb a 113. feladatban szerepl

Ai ; Bi ; Ci (i = 1; 2) halmazokat!

41


118. Egy iskolban a dikok klnfle bizottsgokat vlasztottak (egy ember tbb bizottsgnak is tagja lehet) s most minden bizottsg a sajt tagjai kzl egy{ egy elnkt szeretne kinevezni. Brmely bizottsg brmely tagja alkalmas lenne elnknek, de nem akarjk, hogy valaki egyszerre tbb bizottsgnak is elnke legyen. Mikor valsthat ez meg? ! 119. Zsuzsi huszonngy meseknyvt szeretn sztosztani tizenkt atalabb unokatestvre kztt. >gy gondolta, mindegyiknek kt{kt olyat ajndkoz, ami mg nin s meg nekik. t gyereknl mr puhatolzott; sszesen ht knyv jhet nluk szba, a tbbi 17 mindegyikknek megvan. Szt tudja{e Zsuzsi osztani a knyveket gy, ahogy tervezte? 120. Egy laktanyban kttag rsget kell lltani a kapukhoz, a raktrakhoz, az

rtornyokba, stb.; sszesen 29 helyre. Az rparan snok megkrdezi, ki hova menne szvesen. Mindenki megnevez nhny rhelyet. Mikor teljesthet minden

r ignye? ! 121. Valaki kivlasztotta egy halmaz nhny rszhalmazt s most szeretne mindegyikb l kijellni hrom{hrom elemet gy, hogy minden elem sak egy rszhalmaznl szerepeljen. Mikor tudja ezt megtenni? 122. Adott s1 ; s2 ; ; sn termszetes szmok s H1 ; H2 ; ; Hn halmazok esetn mi a szksges s elgsges felttele annak, hogy minden i n{re a Hi {b l kivlaszthass si darab elemet gy, hogy az sszes ilyen elem klnbz legyen?

...

...

Teljes prostsok DEF. az F fggetlen lrendszer a G grf teljes prostsa, ha G minden pontj-

123.

DEF.

124. 125. 126.

ra illeszkedik F {nek legalbb egy le (s akkor szksgkppen pontosan egy). Persze ekkor a pontszm pros; ha pedig G pros grf, akkor a kt osztlyban azonos szm pont van. Hall ttele teljes prostsokra: Legyen G olyan pros grf, amelyben az als s a fels ponthalmaz ugyanakkora. Ha G{ben ltezik teljes prosts, akkor V1 {re is s V2 {re is teljesl a Hall{felttel; ha pedig valamelyikre teljesl, ez mr elgsges a teljes prosts ltezshez. Bizonytsd be Hall fenti ttelt! ! Egy grf r{regulris, ha minden pontjnak foka r. Mutasd meg, hogy r{regulris pros grf biztosan teljesti a Hall-felttelt! Kvetkezmny: r{regulris pros grfnak mindig van teljes prostsa. (folytats) Igaz marad{e a fenti llts, ha a grfban tbbszrs leket is megengednk? ! Lerajzoltl egy pros grfot, melyben minden s sba pontosan r l fut. Vletlenl ppen r darab klnbz szn eruzd van (a feketn kvl, amivel az eredeti bra kszlt). Bizonytsd be, hogy az leket kihzhatod sznessel gy, hogy minden s sba supa klnbz szn menjen!

42

Elekes Gy:

127. (folytats) Igaz marad{e a fenti llts, ha a grfban tbbszrs lek is szerepelnek? 128. (folytats) Mutass pldt olyan nem-pros, de regulris grfra, ahol a fenti sznezs lehetetlen! 129. Ha egy nem-negatv egsz elemekb l ll mtrix minden sor- s oszlopsszege r, akkor a) van nem-0 kifejtsi tagja; b) el ll r darab permut i{mtrix sszegeknt. 130. Hzassg{problma (K nig) Tegyk fel, hogy egy n lnybl s n bl ll trsasgban minden pontosan r lnyt (nem felttlenl ugyanazokat) tudna elkpzelni leend felesgeknt (s azok erre hajlandak is lennnek), msrszt minden lny pontosan r nak nyjtan kezt (akik azt el is fogadnk). Mutasd meg, hogy sszellthat n boldog jegyespr! 131. Mutasd meg, hogy ha egy pros grfban minden pont foka r, akkor pontok s lek hozzvtelvel kiegszthet olyann, amelyben minden s sra pontosan r l illeszkedik!

132. Igaz marad{e a 126. feladat, ha sak azt tesszk fel, hogy minden s sba legfeljebb r l fut be? 133. Egy 52 lapos kartya{ somagot tizenh arom negylaposra osztott valaki. Bizonytsd be, hogy a negyesekb} ol kiv alaszthatunk egy-egy lapot, amelyek mind klnbz gur ak ill. sz amok (teh at egy{egy asz, kir aly, ... , h armas, kettes).

. . . s nhny nehezebb. 134. Legyen G(V1 ; V2 ; E ) pros grf s X1 V1 ; X2 V2 ; a s s{osztlyok tet 135.

sz leges rszhalmazai. Tegyk fel, hogy olyan (rszleges) prosts is ltezik, amely fedi X1 {et s olyan (esetleg msik) is, ami X2 {t fedi. Mutasd meg, hogy ekkor van olyan is, ami fedi mindkett t!

Bizonytsd be, hogy minden pros grfban ltezik olyan (rszleges) prosts, ami fedi az sszes maximlis fok pontot!

136. (folytats) Adj ebb l j megoldst a 132. feladatra!

DEF. Egy nem negatv elemekb}ol allo mtrix dupln szto hasztikus, ha minden sor- s oszlopsszege 1.

137. Dupln szto hasztikus mtrixnak van nem-0 kifejtsi tagja.

!

138. (folytats) Dupln szto hasztikus mtrix permut imtrixok (konvex) lineris konbin ija.

139.

Legyen G pros grf, melynek van teljes prostsa s minden als" pont foka legalbb r. Bizonytsd be, hogy G{nek legalbb r klnbz teljes prostsa van!

!

43


DEF. Ha egy ngyzetes mtrix determinnsnak kifejtsi tagjait nem a szoksos el jelezssel, hanem anlkl adjuk ssze, a mtrix permanenst kapjuk.

Van der Waerden sejtse (Sokig megoldatlan volt; a kzelmltban igazolta | egymstl fggetlenl | Falikman s Jegori sev): Dupln szto hasz-

!

tikus mtrix permanense legalbb nn . n

Lefog pontok. K nig ttele. 140. Egy osztlyban vegyes prosokat szeretnnek sszelltani az iskola tollaslabda{ bajnoksgra. t lny s t tud jtszani, de nem minden szba jhet pr akar egytt szerepelni: Andrisnak mindegy; jtszana Flrval, Gabival, Helgval, Ildivel vagy akr Jutkval is. Balzs, Csaba, Dani s Ede viszont sak Jutkval hajland egy prba kerlni. Hny prt tud az osztly killtani? ( tlet: lehet{e olyan pr, amelyikben sem Andris, sem Jutka nin s benne?) 141. Az asztalitenisz bajnoksg prosainak sszelltsa se megy smn: a tz ping{pongozni tud bl Andris s Balzs sak Mar ival akar egy prban lenni, Csaba s Dani Norbival, Ede s Kar si pedig Oszihoz ragaszkodnak. La i lenne Mar ival, Norbival vagy akr Oszival is. Az utbbi hrom brki oldaln killna, akik ket vlasztottk. sszellthat{e t vagy legalbb ngy pr? (tlet: kik azok, akik nlkl nin s pros?) DEF. A G tetsz leges (teht nem felttlenl pros) grf pontjainak L rszhalmaza lefog pontrendszer, ha minden lnek legalbb egy vgpontja L{ben van. 142. Legyen F a G grf fggetlen lrendszere, L pedig lefog pontrendszer. Mutasd meg, hogy F {ben nem lehet tbb l, mint ahny pontja L{nek van. Kvetkezmny: tetsz leges grfban legfeljebb annyi fggetlen l lehet, mint a legkisebb lefog pontrendszer pontszma. K nig ttele: Pros grfban fggetlen lek max. szma = lefog pontok minimlis szma 143. Mutasd meg, hogy a 113. feladat ( ) felttele mellett fggetlen lrendszer! 144. (folytats) Igazold ebb l Knig ttelt!

F

maximlis lszm

!

Gyakorl feladatok 145. Adj meg a 117. feladat pros grfjban egy, az leket lefog minimlis pontrendszert!

44

Elekes Gy:

146. Mutass pldt arra, hogy K nig ttele nem{pros grfokra nem igaz! 147. Vedd el jra a vegyes prosokrl szl feladatot! Ott Balzs, Csaba, Dani s Ede sak Jutkval volt hajland egy prba kerlni. Mutasd meg, hogy ha egy pros grfban ilyen eset ll el (teht az egyik rsz ngy pontja a msik rsznek

sak ugyanazzal az egy pontjval van sszektve), akkor | ha a ngy pont egy n pont rszben van | legfeljebb n fggetlen le lehet a grfnak.

3

148. (folytats) Mit mondhatsz, ha egy n pont rsz valamely rsznek sszesen sak k d pontjval van sszektve?

149. Legyen G n{pont pros grf. Adj n d szksges s elgsges (a) Hall{tpus felttelt; (b) lefog pontokra vonatkoz felttelt!

k

pontja a msik

!

(d = 0; 1; 2; . . .) fggetlen l ltezsre

. . . s nhny nehezebb. DEF. Tetsz leges grfban lefed lrendszernek nevezzk lek egy halmazt, ha minden s sra illeszkedik kzlk legalbb egy.

DEF. Egy tetsz leges grf nhny pontja fggetlen pontrendszer, ha nem vezet kztk l (azaz ha res rszgrfot hatroznak meg).

150.

n pont grfban a fggetlen pontok max. szma + a lefog pontok min. szma = n. Tovabba, ha nin s izolalt pont, akkor a fggetlen lek max. szma + lefed

lek min. szma = n.

151. Izollt pont nlkli pros grfban fggetlen pontok max. szma

= lefed lek min. szma

152. (folytats) Mutass pldt arra, hogy nem{pros grfra az el z llts ltalban nem rvnyes!

2.8. ltalnos grfok prostsai. Tutte ttele 153. Egy osztly mind a 20 tanulja szeret pingpongozni. Egyniben mindnyjan indulnak is az iskolai bajnoksgon, de 10 prost is ki akarnak lltani. Sajnos, Kar sin s Mar in kvl | akik mindenkivel jl kijnnek | a maradk 18 gyerek ngy soportra bomlik. Egyik ilyen trsasg ht tagbl ll, a msik tb l, a maradk kett ben hrman{hrman vannak. Senki sin s jban a tbbi

soport tagjaival, olyannyira, hogy nem is akarnak velk egy prba kerlni. Killthat-e azrt mg a tz pr?

45


DEF. A G grf teljesti a Tutte{felttel{t, ha brmely k termszetes szm s

tetsz legesen vlasztott k s s elhagysa utn a maradk grfban legfeljebb k sszefgg komponens pontszma lesz pratlan. Megjegyzs: Spe ilisan k {ra a felttel azt is biztostja, hogy G{nek pros szm pontja lesz. 154. Bizonytsd be, hogy a Tutte{felttel szksges teljes prosts ltezshez! Megjegyzs: A felttel elgsges is: Tutte ttele: Tetsz leges G grfban akkor s sak akkor ltezik teljes prosts, ha G teljesti a Tutte{felttelt.

=0

Teljes grfok faktoriz ija. 155. Mutasd meg, hogy a) n

sapat egy teljes bajnoksgot le tud jtszani n b) n sapat is le tudja jtszani a teljes bajnoksgot n (Mindenki mindenkivel egyszer jtszik.)

2 2

1

2

2

1 fordulban; 1 fordulban;

2.9. Grfok kromatikus szma DEF. A G(V; E ) grf jl sznezhet k sznnel, ha s sai k osztlyba oszthatk (pl.

V1 [ V2 [ . . . [ Vk = V ) gy, hogy egy osztlyon bell nem megy l, azaz x; y 2 Vi (x; y) 2= E . DEF. G kromatikus szma a legkisebb k, ahny sznnel a grf jl sznezhet . Jellse (G). esetn

156. Mik a kt sznnel sznezhet grfok? ! 157. Ha minden pont foka legfeljebb d, akkor a grf d sznnel sznezhet . ! 158. Mutasd meg, hogy ha egy sszefgg grfnak van sztvg pontja, akkor kromatikus szma ugyanannyi, mint blokkjai (maximlis ktszeresen sszefgg

rszei) kromatikus szmainak maximuma. ! 159. Mutass olyan grfot, a) amiben nin s hromszg s G ; b) amiben nin s K4 s G ;

) amiben nin s teljes k {szg s G k . 160. (folytats) Minden k {ra mutass hromszg nlkli, k sznnel nem sznezhet

grfot! 161. Adott a skban vges szm egyenes, melyek kzl semelyik hrom sem megy t egy ponton. A metszspontokat tekintsk egy grf s sainak, a (vges) szakaszokat pedig leknek. Mutasd meg, hogy a grf hrom sznnel sznezhet !

+1

( ) 3 ( ) 4 ( )

!

46

Elekes Gy:

162. (folytats) Igaz marad-e az llts, ha kett nl tbb egyenes is tmehet egy ponton? ! 163. Ha egy sszefgg grfban minden pont foka legfeljebb pont is, akkor G k .

( )

k

s van kisebb fok

!

Brooks ttele. Ha egy sszefgg grf nem teljes s minden pont foka legfeljebb

k ( 3), akkor (G) k.

164. Mutasd meg, hogy ha egy sszefgg grf nem teljes s legalbb hrom pont, akkor tallhat benne olyan a; b; ponthrmas, melyek kztt pontosan kt l fut. !

165.

(folytats) Bizonytsd be Brooks ttelt a) hromszorosan sszefgg grfokra; b) minden grfra.

166. Igaz-e Brooks ttele

k = 2{re?

!

Perfekt grfok.

( )

A tovbbiakban ! G jelli a G grf legnagyobb teljes rsznek pontszmt (a maximlis klikk{mretet).

DEF. Nevezzk a G grfot normlisnak, ha (G) = !(G).

Megjegyzs: A 159. feladat szerint vannak nem normlis grfok is.

167. Az albbi grfok kzl melyek normlisak: a) fk; b) Kn (teljes n{szgek) n ; ; ; ;

) hrom{hz-hrom{kt", s u sai: H1 ; H2 ; H3 ( hzak"), K1 ; K2 ; K3 ( kutak"), s minden Hi minden Kj {vel ssze van ktve); d) Petersen grf (egy t pont krben egy sillagtszg; a megfelel s sok sszektve); e) pratlan krk; f) pratlan krk komplementerei? !

= 3 4 5 ...

168. Mutasd meg, hogy a fk komplementerei normlisak! 169. Bizonytsd be, hogy a kvetkez grfok mind normlisak: a) pros grfok; b) rszben rendezett halmaz sszehasonltottsgi grfja" (az a s b elemeket akkor ktd ssze, ha vagy a b vagy b a);

) intervallum{grfok (intervallumoknak feleltess meg s sokat; kss ssze kett t, ha a megfelel

intervallumok egymsba metszenek). 170. (folytats) Normlisak-e az el z feladatban szerepl grfok komplementerei?

!

47


DEF. G0 (V 0 ; E 0 ) a G(V; E ) fesztett rszgrfja, ha V 0 DEF. 171.

V

s

E0

a

V0

pontjai kztt fut sszes eredeti lb l ll. A G grf perfekt, ha minden fesztett rszgrfja normlis, azaz 8G0 G0 ! G0 . Bizonytsd be, hogy az albbi grfok mind perfektek: a) fk; b) Kn (teljes n{szg) n ; ; ; ;

) pros grfok; d) rszben rendezett halmaz sszehasonltottsgi grfja"; e) intervallum{grfok. Mutasd meg, hogy egy grf nem lehet perfekt, ha tartalmaz a) hromnl tbb pont, tl nlkli pratlan krt; b) ilyen kr komplementert. Norm alis grafhoz egy u j pontot hozz aveve es azt minden regivel osszek otve ismet norm alis graf adodik. Igaz-e ugyanez normalis" helyett perfekt"{tel? Perfekt graf egy x s u s at perfekt graal helyettestve (es minden u j s u sot osszek otve x minden regi szomszedjaval) ismet perekt gr afot kapunk.

( )=

( )

= 3 4 5 ...

172.

173.

174.

Perfekt grf sejts. Egy grf akkor s sak akkor perfekt, ha az el z

feladatban szerepl a) s b) tpus rszek egyikt sem tartalmazza.

175. Mutasd meg, hogy a a 171. feladatban szerepl grfok komplementerei is perfektek!

Lovsz ttele. (Rgebben gyenge perfekt grf sejts" volt.) Perfekt grf komplementere is perfekt.

Megjegyzs: A sejtsb l Lovsz ttele is kvetkezne; az el bbi azonban megoldatlan.

2.10. Skgrfok 176. Melyik grfot tudod lerajzolni gy, hogy lei ne messk egymst: a) egy ko ka leinek hlzata; b) Kn (teljes n{szg) n ; ; ; ;

) hrom{hz-hrom{kt", s u sai: H1 ; H2 ; H3 ( hzak"), K1 ; K2 ; K3 ( kutak"), s minden Hi minden Kj {vel ssze van ktve); d) Petersen grf (egy t pont krben egy sillagtszg; a megfelel s sok sszektve). ! 177. (folytats) Mi a helyzet, ha az el z ngy grf leit (kzs bels pont nlkli, tetsz leges hosszsg) utakkal helyettestjk? !

= 3 4 5 ...

48

Elekes Gy:

DEF. G skbarajzolhat, ha s sainak megfeleltethet a sk egy{egy pontja, leinek

pedig a megfelel pontprt sszekt folytonos grbk, amelyek nem metszik egymst.

Kuratowski ttele. Egy grf akkor s sak akkor nem skbarajzolhat, ha tartalmaz olyan rszt, ami K5 {b l vagy a hrom{hz-hrom{kt"{bl keletkezik az el z feladat l{t helyettestsvel.

DEF. A G(V; E ) grfbl az e 2 E l sszehzsval keletkezik az a G0 (V 0 ; E 0 ) grf, melyben e kt vgpontjt egyetlen ponttal helyettestjk, sszektve ezt

mindazon rgi pontokkal, melyekkel a kt vgpont valamelyike ssze volt ktve G{ben.

178. Hogy fgg ssze

G s G0

skbarajzolhatsga?

Wagner ttele. Egy grf akkor s sak akkor nem skbarajzolhat, ha tartalmaz olyan rszt, amib l bizonyos lek egyms utni sszehzsval K5 vagy a hrom{hz-hrom{kt" keletkezik. Megjegyzs: Kuratowski s Wagner ttelei nem ugyanazt mondjk! Erre mutat pldt a kvetkez feladat: 179. Bizonytsd be, hogy a Petersen{grf (lsd 176.d. feladat) sszehzhat t pont teljes gr, de nem tartalmaz abbl l{t helyettestssel keletkez rszt.

DEF. Skbarajzolt grf vagy grf skbarajzolsa: pontok s ket sszekt , egymst nem metsz folytonos grbk. (Egy grfnak sok skbarajzolsa van; sok skbarajzolt grf tartozik hozz.)

Megjegyzs: Igaz az is, hogy skbarajzolhat grfnak van olyan skbarajzolsa, ahol minden l egyenes szakasz. s l.

Jellje egy skbarajzolt grf s sainak, leinek s lapjainak szmt rendre ,

e

Euler ttele. Skbarajzolt grfra

+ l = e + 2: Kvetkezmny: Adott grf minden skbarajzolsban ugyanannyi a lapok szma.

180. Hny le van egy n pont skgrfnak, ha minden lapja (a kls , vgtelen darabot is belertve) hromszg? ! 181. Bizonytsd be, hogy lehet!

n 3 pont skbarajzolhat grfnak legfeljebb 3n

182. Skgrfnak mindig van legfeljebb tdfok pontja. 183. Mutasd meg, hogy minden skgrf jl sznezhet hat sznnel!

6 le ! !

49


184.

(folytats) Bizonytsd be, hogy t szn is elg!

Ngy{szn ttel. Brmely skgrf jl sznezhet ngy sznnel. Megjegyzs: Az eredeti ngy{szn sejts trkpek orszgainak (skgrfok lapjainak) sznezhet sgre vonatkozott.

DEF. A G(V; E ) skbarajzolt grf dulisa a G (V ; E ) , ha G pontjai G lapjainak felelnek meg s kt pontot annyi E {hoz tartoz l kt ssze, ahny kzs le a nekik megfelel eredeti kt lapnak volt volt.

185. Mi a dulisa a kvetkez grfoknak (a skbarajzols lnyegben egyrtelm): a) egyetlen kr; b) K4 ;

) a ko ka lhlzata; d) az oktader lhlzata. ! 186. Mutasd meg, hogy a) G is skbarajzolhat; b) e e s l . ( , e s l rendre a grf s sainak, leinek s lapjainak szmt jelli.)

=

=

187. Lehetsges-e, hogy egy skbarajzolhat grf klnbz lerajzolsaibl klnbz

dulisok addnak? ! Megjegyzs: A dulis tulajdonkppen azt kdolja, milyen lek kerlnek egy{ egy lapra. >gy is mondhatnnk, hogy a nem-izomorf dulisok a lnyegesen klnbz skbarajzolsokat reprezentljk. 188. Igaz-e, hogy

189.

G = G?

!

Hromszorosan sszefgg skbarajzolhat grf dulisa fggetlen a lerajzolstl.

190. A skot vges szm egyenes sokszg{tartomnyokra bontja. Mutasd meg, hogy ezek a lapok kt sznnel sznezhet k gy, hogy szomszdosak ne legyenek egysznek! 191. (folytats) Mely skgrfokra ltezik a fentihez hasonl sznezs? 192. Hny sznnel sznezhet ek

K4 lapjai?

! !

Ngy{szn ttel lapokra. Minden skgrf lapjai ngy sznnel sznezhet ek gy, hogy szomszdos lapok ne legyenek egysznek.

193. Mutasd meg, hogy a ttel kt alakja ekvivalens!

194. 195.

!

Bizonytsd be, hogy minden skgraf pontjai h arom sznnel sznezhet}oek u gy, hogy az egyes sznosztalyok altal fesztett reszgr afok kozos pont nelk uli utakbol alljanak! Mutasd meg, hogy b armely skgraf pontjai ot sznnel j ol sznezhet}oek u gy, hogy radasul minden koron legalabb h arom szn forduljon el} o.

50

Elekes Gy:

2.11. Hibs okoskodsok 2

196. llts":Ha egy n pont G grfban minden pont foka r (az ilyen grfokat r{regulrisnak nevezik), akkor G felbomlik r darab (kzs l nlkli) teljes prosts egyestsre. Megolds":r szerinti teljes induk ival. a) r {re az llts trivilis. b) Tegyk fel, hogy r{re az llts igaz. Egy r{regulris G grfhoz hozzvve egy {regulris F {et, r {regulris G0 {t kapunk. Mivel G az induk is felttel szerint r darab teljes prosts egyestse, F pedig maga egy teljes prosts, gy az r {regulris G0 valban r teljes prosts egyestse. HOL A HIBA? (VAN!!)

=1 1

+1

+1

+1

1

197. llts":n pont fnak n le van. Megolds":Induk i n szerint: a) n {re (vagy n {re) az llts trivilis. b) Tegyk fel, hogy n pont fkra az llts igaz. Vegynk hozz egy n pont fhoz egy j let, melynek egyik vgpontja az eredeti fban van, a msik j, egy n {edik pont.
=1

=2

+1

+1

= ( + 1) 1 2

1

+1

fgg . n 2) n 1 egy n Megolds": (n 1)( pont teljes grf leinek szma. Ha 2 2 ehhez mg egy let hozzvesznk, mely egy eredeti pontbl az n{edikbe fut, sszefgg grfot kapunk. HOL A HIBA? (VAN!!)

=

1

199. llts":Egy (legalbb kt tag) ping{pong krmrk zs versenyz i | ha nin s olyan soportjuk, akik mindnyjan legy ztk a msik soport minden tagjt | krbellthatk gy, hogy mindenki legy zte a t le jobbra llt! Megolds":teljes induk i n, a versenyz k szma (vagyis a grf pontszma) szerint: I. n {re mindenkppen van rossz" sztvgs, teht az llts minden megfelel ktpont grfra igaz. (Vagy n {ra a felttel szerint a versenyz k krbe vertk egymst; van megfelel kr) II. tegyk fel, hogy az n{nl kisebb szmokra mr tudjuk, s tekintsnk egy n{rsztvev s versenyt! Vegyk ki az egyik versenyz t, pl. a{t. A tbbiek az induk is felttel szerint megfelel en krbellthatk.

=2

=3


51

Ha mindenki kikapott volna a{tl (ill. ha mindenki legy zte volna a{t), lenne rossz" sztvgs. Legyen b olyan, akit l kikapott; innen jobbra szmolva tegyk a{t az els olyan el, akit legy ztt. HOL A HIBA? (VAN!!)

52

Elekes Gy:

3. fejezet Algoritmusok I.

3.1. Algoritmusok lpsszma. Mikor j" egy algoritmus? Ha mkdik" vlaszolhatod els kzeltsben, esetleg hozztve: azaz nem kerl vgtelen iklusba, hanem befejez dik gy, hogy a j eredmnyt adja." Valban, enlkl egy algoritmus sak hibs lehet; krds, ennyi elg-e mr ahhoz, hogy jnak min stsk? Tegyk fel, valaki azt szeretn megtudni, tgyalogolhat-e a Szaharn gy, hogy naponta { egyik ozistl a msikig | nem tbb, mint harmin kilomtert kelljen megtennie. Mr ssze is lltott egy teljesnek mondhat listt, melyben krlbell ktszz ozis szerepel, pontos fekvskkel egytt. Az egyszersg kedvrt szmtgpre vitte az adatokat; ezek alapjn szeretne most vlaszt kapni krdsre. | Az egymstl harmin kilomteren bell fekv helyek grfjt kell vizsglnom | mormogja | az a krds, van-e benne t a kt adott pont kztt? (A tervezett kiindulsi- ill. lpontra gondol.) | Ezzel nagy lpst tett el re: tfogalmazta a feladatot a matematika, jelen esetben a grfelmlet nyelvre. Lssuk, jl folytatja-e: | Egyszer az egsz: sorra veszem a pontok minden egyes rszhalmazt, mindegyiknek az elemeit minden lehetsges sorrendben; kiegsztem ezeket a kezd - s a vgponttal, vgl ellen rzm, hogy az egyms utniak kztt van-e le a grfnak (harmin kilomternl kisebb-e a tvolsguk). Ha tallok ilyen rszhamazt s hozz ilyen sorrendet, megvan az titerv; ha nem, akkor nem is lehetsges. Ez az algoritmus nyilvn megfelel az lljon le s adjon helyes eredmnyt" kritriumnak. Nevezhetjk teht jnak a mdszert? Azt most ne krdezzk, tud-e az illet hibtlan programot rni bel le; tegyk fel, hogy kzben mr megrta, t{tz pontbl ll grfokon pr per alatt lefutott (persze a nagyobbakon lassabban). Elindtotta az igazi adatokon; sajnos mr rk ta fut s mg mindig nem llt le.

53


Mi lehet a problma? Gondolkozzunk el azon, hogy a ktszz pontnak hny rszhalmazt kell vgigvizsglni (minden lehetsges sorrendben). Ezek szma nyilv an 200 . Ez egy 60 jegy (!) szm. A mai leggyorsabb szmtgpek nhny szzmilli utastst hajtanak vgre msodper enknt. Mennyi id alatt vgeznnek ennyi mveletet? Tbb, mint 50 msodper alatt. Egy v kevesebb, mint 8 msodper ; a zikusok a vilgegyetem keletkezsnek id pontjt hszmillird vvel ezel ttre teszik. Ha a mai legyorsabb gpet akkor indtottk volna el, azta sszesen is sokkal kevesebb, mint 30 utastst hajthatott volna sak vgre. (Bizonyra szreveszed, hogy ez nem a fele az emltett 60 {nak; nem kt, hanem 30 szmtgp vgezhetett volna 60 mveletet. Ehhez a Fld minden egyes kbmillimterben egy{egy gpnek kellene dolgoznia.) Vonjuk le ebb l azt a kvetkeztetst, hogy a Szahara{feladat nem oldhat meg szmtgppel?

2

10

10

10

10

10

10

Inkbb azt a tanulsgot szrjk le, hogy nem mindegy, mennyi id alatt ad j eredmnyt egy eljrs. Pl. a fenti exponen ilis szm ( n ) rszhalmazt vizsgl, ha a pontszm n; ez kzepes mret adathalmaz esetn is elkpeszt en nagy lehet. Jobbak azok a mdszerek, amelyek lpsszma az adatok mretnek polinomja. A tovbbiakban ilyen algoritmusokat prblunk tallni | s persze ezen bell is a lehet leggyorsabbat.

2

Hogyan troljunk adatokat szmtgpben? Kt alapvet trolsi struktra{tpust fogunk hasznlni: tmbket s listkat. Mindkett lerhat magasszint programnyelveken (Magyarorszgon a

PASCAL s a C nyelv a legismertebbek). rdemes a gyakorlatban is megismerkedned velk bevezet programozsi tanknyvek segtsgvel. A tovbbiak azonban enlkl, nmagukban is rthet ek lesznek. A tmbk is, a listk is bizonyos egysgekb l llnak; az alapvet klnbsg kztk a trols s hozzfrs mdjban van. DEF. A tmbk azonos mret egysgekb l llnak s egyetlen sszefgg blokkban helyezkednek el, sorszmmal elltva. Az A tmb i{edik elemre A i {knt hivatkozhatunk. El nye: az egysgek kzvetlenl (helyk alapjn) elrhet ek anlkl, hogy az

ket megel z egysgeket megvizsglnnk. Htrnya: ha egy tmb els szz eleme pl. nagysg szerint rendezve van s egy jabbat akarunk kzjk tenni (a tovbbiakban ezt beszrsnak nevezzk) mondjuk kzpre, akkor ehhez az tvennl nagyobb indexeket eggyel odbb kell mozgatni. (Persze ezt fellr l rdemes kezdeni.) Megjegyzs: Tbbszrs indexels tmbk is megengedettek, pl. egy kett s indexszel elltott A tmb i; j index eleme A i; j . Ekkor A{t ktdimenzis

[℄

( )

[ ℄

54

Elekes Gy:

tmbnek nevezzk. DEF. A listk tetsz leges, nem felttlenl azonos mret egysgekb l llhatnak s

elhelyezkedskben sin s semmi rendszer. Elrni sak azltal lehet ket, hogy minden egysg a lnyeges inform in kvl mg .n. mutatt is tartalmaz, ami a lista kvetkez elemnek helyr l szolgltat inform it. Szksg van persze egy kln mutatra a lista els elemnek megtallshoz is. El nye: ha j egysget akarunk beszrni, ehhez semmit sem kell mshova mozgatnunk; elg, ha ennek mutatjt a listban majdan utna kvetkez egysgre lltjuk, a megel z t pedig az ppen beszrtra. Htrnya: egyedl az els egysg rhet el kzvetlenl; a tbbi sak gy, ha ebb l indulva vgigkeressk a listt. 1. Egy tmbben ezer vals szmot trolsz 1{t l 1000{ig indexelve, nagysg szerint rendezve. Arra vagy kvn si, szerepel-e kztk az 123456,78. A tmb hny elemt kell megvizsglnod ennek eldntshez? (Olyan mdszert keress, ami biztosan kevs elemet nz meg.) ! 2. (folytats) Mi a helyzet szzezer elem tmb esetn? !

3.2. A legkisebb elem kivlasztsa. Rendezs. 3. Hny sszehasonlts szksges ahhoz, hogy n darab klnbz adott szm kzl kivlaszd a legnagyobbat? ! 4. Mutasd meg, hogy n elem rendezesehez | ha sak sszehasonltsokat vegz unk | legalabb n n m}uvelet kell. 5. Milyen nagys agrend} u a Bubork{rendezs" lepesszama a legrosszabb esetben? 6. H any lepesben lehet kt rendezett tmb ot sszefslni? ! 7. (folytats) Es sszefslssel rendezni? ! Megjegyzs: Ennek az algoritmusnak | a jo lepesszam mellett | az is el} onye, hogy konnyen megrhat o rekurzv hvasokkal.

log

3.3. Binris fk. A kupa . DEF. binris fa: minden pontban legfeljebb ketfele agazik. Magassga: a gyokerb}ol a legt avolabbi levelbe vezet}o u t hossza.

DEF. kiegyenslyozott binris fa: a levelek mind ket szomszedos szinten helyezkednek el. 8. Tz szintb l ll binris fnak hny pontja lehet? Mennyi ebb l a levelek szma s mennyi az elgazsi pontok!

55


9. Milyen sszefggs van (nem felttlenl kiegyenslyozott) binris fa elgazsi ponjainak ill. leveleinek szma kztt? 10. Egymilli elem kiegynslyozott binris fa milyen magas? Olyan struktrt de nilunk, ami jelent sen meggyorstja (szmtgpekben) az adatok trolst, ha az a l, hogy a trolt szmok kzl brmikor gyorsan kikereshessk a legkisebbet, tovbb (ugyan sak gyorsan) trlhessnk, skkenthessnk s jabbakat szrhassunk be. (Ha a legnagyobb szm folyamatos nyilvntartsa a l, akkor az egyenl tlensgek rtelemszeren megfordulnak.) DEF. Kupa : (ez az angol nyelv irodalomban szoksos heap" kifejezs fordtsa; magyarul hasznljk a piramis" elnevezst is.) Olyan slyozott s s, majdnem teljes binris fa, melyben, ha az x s s leszrmazottai y1 s y2 , akkor w x w y1 ; w y2 . (Ekkor a minimlis w nyilvn mindig a gykrben lesz.) Megjegyzs: Egy kupa trolsa klnsen egyszer: tarthatjuk egy tmbben, ahol az i{edik elem gyerekei a i{edik s a i {edik; szl je az bi= {edik. 11. Mutasd meg, hogy n s s kupa ban a trls, skkents s j elem hozzvtele

log2n lpsben megvalsthat! 12. n szmbl n lpsben (!) lehet kupa ot pteni. 13. Rendezz n elemet, kupa okat hasznalva, n n id}oben!

()

( ) ( )

2

2 +1 log

2

56

Elekes Gy:

57


II. RSZ

ami taln mr jdonsg.

58

Elekes Gy:

4. fejezet

Leszmlls II.

4.1. >jabb pldk rekurzikra A Stirling{szmok DEF. Jellje S (r; k) azt, hnyflekppen vghatunk egy r elem halmazt k darab nem{res rszre! Pldul az

1. 2. 3.

4.

(3 2) = 3 ( 2) = ( 1) =

fa; b; g halmaz kt rszre vgsai: fa; bg f g fa; g fbg fag fb; g;

teht S ; . a) S r; ? b) S r; r ? Keress rekurzit S r; k {ra s kszts tblzatot az r rtkekre! Hny klnbz mdon oszthatunk szt r klnbz trgyat k klnbz szn htizskba gy, hogy egy zsk se maradjon res? Fejezzk ki a vlaszt a) a szita{formulval; b) S r; k segtsgvel! Bizonytsd be, hogy k X i k k i r: S r; k

( )

6

( )

( ) = k1!

5. 6.

i=0

( 1)

r X

i

(

)

r Mutasd meg, hogy S (r + 1; k + 1) = S (p; k). p p=k Bizonytsd be, hogy az an = nr sorozatra (itt r rgztett k a0 = k! S (r; k).

7. (folytats) Igazold, hogy nr

=

r X

k=1

!

S (r; k) n (n

termszetes szm)

1) . . . (n

!

k + 1).

59


4.2. Tkrm, tkrm . . . 8. Billy, a owboy egy egyenes folypart kzelben lakik. Reggel fell a lovra, hogy a vznl megitassa; utna Maryhez szndkozik lovagolni, aki kiss tvolabb, de a folyn innen lakik. Hogyan kereshetjk meg a legrvidebb Billy{ folypart{Mary" utat? ! 9. Az origbl mindig jobbra ill. felfel szomszdos r spontokra egysgnyit lpve hnyflekpp juthatunk el (7,11){be, ha sose lphetnk olyan helyre, ahol y x ? 10. Az peren is tenger kzepn talljuk a Catalan{szigeteket. Meseorszg fel l hajzva mr messzir l feltnnek a szinte megmszhatatlan, pontosan 45 fokos korall{szirtek krvonalai. rdekessge a soportnak, hogy az rkez hajrl minden szigethegy gerin nek vonala hat darab 1 km{es szakaszbl ll (pl. fel{le{fel{fel{le{le sorrendben; ezt a szigetet teht kt, ppen a tengerszinten rintkez hegy alkotja), s az sszes, ilyen tpus szigetb l pontosan egyet lt az utaz. a) Hny szigetb l ll a soport? b) s ha a gerin {vonalak 8 km{esek? ! 11. 15 s 12 lny hnyfle sorrendben mehet be a tn terembe, ha sosem lehet tbb lny odabent, mint ? ! 12. Egy mozi pnztrnl n gyerek ll sorba 10 Ft{os jegyekrt. Kzlk n{nek tizese, a msik n{nek egy{egy huszasa van. A kasszban nin s vltpnz. Hny olyan sorrendje van a gyerekeknek, amikor a sor nem akad el, a pnztros mindig tud visszaadni? ! 13. (folytats) Jelljk az el z feladat eredmnyt Cn {nel! Mutasd meg, hogy

=

3

2

Cn = C0 Cn 1 + C1 Cn 2 + . . . + Ci Cn i 1 + . . . + Cn 2 C1 + Cn 1 C0

= 1; C1 = 1; C2 = 2; C3 = 5; C4 = 14; C5 = 42; . . .. 1 2nn. Bizonytsd be, hogy Cn = n + 1 Egy n entimteres pl t hnyflekppen trhetnk 1 m{es darabokra, ha

DEF. A fenti Cn {eket Catalan{szmok-nak nevezzk. C0 14. 15.

a) egy lpsben mindig egy 1 m{nl hosszabb darabot trnk kt rszre? b) egy lpsben mindig az sszes, 1 m{nl hosszabb darabot kt rszre trjk? 16. A r spontos feladat milyen esetben vezet Catalan{szmokra? 17. Egy 2n oldal szablyos sokszg s sait hnyflekpp lehet pronknt kzs pont (s vgpont) nlkli szakaszokkal (oldalakkal vagy tlkkal) sszektni?

60

Elekes Gy:

18. Egy 10 tnyez s szorzat hnyflekpp zrjelezhet , hogy minden zrjelben egy jabb szorzs legyen kijellve? 19. Hnyflekpp lehet egy n oldal konvex sokszget nem metsz tlkkal hromszgekre bontani? 20. Hny olyan f n 7! n monoton fggvny van, ami minden i n{re teljesti az f i i felttelt? 21. Exped i indul az Antarktiszra; egy v alatt szndkoznak krljrni. A szksges lelmiszert a tervezett tvonal mentn | nhny heti adagokra osztva | mr el re elhelyezte egy szllt repl gp. (Az utols menetben, amikor az embereket, sl eket, sznokat s kutykat viszi, ms mr nem fr a gpbe.) Indulskor jut eszkbe: nem ellen riztk, kitart-e minden tszakaszon az lelem a kvetkez tartalk{raktrig. a) Nyugtasd meg ket! Igazold, hogy van olyan hely, ahonnan indulva mindig lesz nluk elg lelem (feltve, hogy krtjukat tnyleg befejezik egy v alatt.) b) Mutasd meg azt is, hogy ha az el re elhelyezett mennyisg egy heti adaggal tbb a szksgesnl, akkor olyan hely is van (s pontosan egy!), ahonnan indulva mindig lesz nluk legalbb egy egsz heti tartalk. 22. Tegyk fel, hogy egy supa s tagokbl ll sorozat sszege ppen . Mutasd meg, hogy pontosan egy olyan iklikus permut ija van, melyben minden kezd szelet (azaz minden i n{re els i tag sszege) pozitv. 23. (folytats) Igazoljuk, hogy azon n elem, tagokbl ll sorozatok szma, melyben a teljes sszeg 1 s minden kezd szelet sszege pozitv (itt nin s n . permut i), n n (Mi kze ezeknek a Catalan{szmokhoz?) 24. Hny olyan sorozat kpezhet n darab s n darab felhasznlsval, melyben minden rszletsszeg ? 25. n hangya mszik egy szk jratban, melyb l kzepen egy zskut a" gazik ki. A jrat s a mellkg olyan keskenyek, hogy kt hangya mr nem fr el egyms mellett, nem el zheti egyik a msikat. (Persze, aki bemegy a zskut ba, azt akrhnyan meg tudjk el zni.) A f gban folyamatos a halads, semelyik sem fordul vissza. Hnyfle klnbz sorrendben jhetnek ki? 26. Hny n level sr binris fa van? (Egy r pontban gykerez binris fa sr, ha minden pontban, ami nem levl, pontosan ktfel gazik.)

()

:

1

+1

1

1

2 +1

1

1 2 +1 2 +1

0

+1

1

4.3. Talljunk rekurzit . . . Prblj rekurzv sszefggseket tallni a kvetkez feladatokra! (Megoldanod most nem kell ket. Ha talltl rekurzit, s a megoldsa is rdekel, nzd meg a Lineris rekurzik"{nl vagy a Genertorfggvnyek"{nl!)


61

27. A Hanoi torony problma": A legenda szerint Hanoi{ban egy kolostorban a lmk egy falapbl felfel kill hrom ruda ska egyikre fzve n darab klnbz mret, kzpen lyukas korongot kaptak Buddhtl. Legalul volt a legnagyobb, felette a tbbi egyre kisebb s kisebb. Azt a feladatot adta nekik, hogy juttasssk a korongokat valamelyik msik ruda skra gy, hogy kzben egyszerre sak egyet tehetnek t, s semelyiket sem szabad nla kisebbre helyezni. Nem knny a lmk dolga (a legenda szerint mire befejezik, eljn a vilg vge). A Ti feladatotok egyszerbb: an {nel jellve az n korong esetn szksges lpsszmot, keress rekurzit an {re! !

= 100

28. Tegyk fel, hogy egy szmtgp{ program egy n elem S struktrt kezel

Rutin n; S eljrst ( szubrutint") hasznl, ami nmi el kszts utn (ha n ) meghvja sajt magt hrom kisebb struktrra, majd ha ennek vge, nmi befejez mveletek utn lell. Kb. gy nz ki, mint

1

(

)

(n; S );

Pro edure Rutin Begin

If n 1 then begin

el kszts; Rutin(n 1; S1 ); Rutin(n 1; S2 ); Rutin(n 1; S3 ); befejezs;

end;

end;

Ha n mret S struktrn az el kszts s a befejezs egytt lps a Rutin teljes futsa? Keress rekurzit!

k n lps, hny

!

29. Egy turista Bergeng iban minden nap egyet vsrol a kvetkez kb l (amg a pnze tart): fagylalt 1 tallr

soki 2 tallr gyml sl 2 tallr

30. 31. 32. 33. 34.

n tallrt? ! Jellje Sn az olyan f : f1; 2; . . . ; ng 7! f1; 2; . . . ; ng fggvnyek szmt, melyek rtkkszlete kezd szelet, azaz ha f valahol felvesz valamilyen y rtket, akkor felvesz minden 1 z y {t is. (Legyen S0 = 1.) Keress rekurzit Sn {re! n egyenes legfeljebb hny rszre vgja a skot? n sk legfeljebb hny rszre vgja a teret? Egy zrt n oldal trttvonal legfeljebb hny pontban metszheti nmagt? Egy konvex n -szg semelyik 3 tlja sem megy t egy ponton. Hny tlmetHnyflekppen klthet el

szspont van?

62

Elekes Gy:

4.4. Lineris rekurzik Els rend rekurzik. DEF. Az els rend lineris rekurzik ltalnos formja (ahol teht an a korbbi tagok kzl sak an

1 {t l fgg, s attl is linerisan) a kvetkez : an = (n) an 1 + b(n):

DEF. Ha s b konstansok, akkor a rekurzi lland egytthats. 35. Legyen a0 tetsz leges. Mi a fenti rekurzi megoldsa, ha a) n n, b n ; b) n ,bn ?

( )= ( )=0 ( )=2 ( )=0 ! 36. Ha (n) = 1, a0 s a b(n){ek pedig tetsz legesek, mennyi lesz an ? ! 37. (folytats) Ha a f egytthat lland: (n) = 6= 1, vezesd vissza a feladatot az el z re az

a An := nn

fggvny segtsgvel! Megjegyzs: Az tlet onnan szrmazik, hogy ha bn

!

38. A Hanoi torony problmra (lsd 27. feladat) az a0 addott. Oldd meg ezt a fenti mdszerrel! 39. Oldd meg az

= 0 lenne, an = a0n volna. = 0, an = 2an 1 +1 rekurzi

a0 = 0, an = 2an 1 + n rekurzit!

40. A hromszor nmagt hv eljrs lpsszmra (28. ) feladat) a

n1 k n rekurzi addott. Milyen nagysgrend a lpsszm?

3 +

41. Ha egy nem lland egytthats feladatban bn

42.

! !

0 = 0, n =

= 0; mennyi lesz an?

! !

(folytats) Hogy lehet visszavezetni (v.. 37. feladat) a nem lland egytthats problmt olyanra, ahol lland? ! n . Mekkora az n{edik tag? 43. a0 , an n an 1 ! 2 44. Oldd meg az a1 , an+1 n+1 n2 rekurzit! n an

=0

=

=0

+

=

+(

1)

63


Msodrend rekurzik

=5

6

45. Az an sorozatot az an an 1 an 2 rekurzio de nialja. Mi az altalanos tag, ha a kezd}otagok: a) a0 , a1 ; b) a0 , a1 ;

) a0 , a1 ; d) a0 , a1 ? e) Hogyan lehet kital alni a rekurziobol, melyik mertani sorozatok a f} oszerepl}ok"? 46. an an 1 an 2. a) Van-e jo mertani sorozat? b) a0 , a1 eseten mi az altalanos tag?

=1 =1 =2 =8

=2 =3 =5 = 17

= 11 =3

28 = 18

A kovetkez}okben lland egytthats, konstans tagot nem tartalmaz (azaz homogn") lineris msodrend rekurzikkal fogunk foglalkozni, melyek ltalnos alakja xn a xn 1 b xn 2 : Megjegyzs: Pldul a Fibona

i{szmok rekurzija ilyen. A megoldsi mdszer is az ott ltottra emlkeztet: 47. Keress olyan nem azonosan 0 mrtani sorozatokat, amelyek kielgtik a fenti rekurzit! ! DEF. A

=

q2

+

aq b = 0

egyenletet a rekurzi karakterisztikus egyenletnek nevezzk. 48. Mutasd meg, hogy ha a karakterisztikus egyenletnek kt klnbz (vals vagy komplex) gyke van, akkor brhogyan megadva x0 {t s x1 {et, a rekurzi megoldsa kt (vals vagy komplex hnyados) mrtani sorozat sszegeknt rhat!

!

49. (folytats) Bizonytsd be, hogy ha sak egyetlen q megolds van, akkor n q n is kielgti a rekurzit! Milyen alakban kereshet xn ? ! 50. Oldd meg az x0 , x1 , xn xn 1 xn 2 rekurzit! ! 51. Oldjuk meg az a0 , a1 k, an k an 1 k2 an 2 rekurziot! 52. n darab (egyforma) etkezesi szelveny unk van, melyeket k etteremben kolthet unk el. Barmely helyen ehet unk ket utalvanyert b} oseges ebedet vagy { egy hely kivetelevel | egyszer} ubbet egy utalvanyert. Ha az ettermek sorrendje is szamt, h anyfelekeppen hasznalhatjuk fel az osszes utalvanyt? 53. Leteznek-e olyan ; ; ; Æ; a0 ; a1 ; a2 ; a3 egesz szamok, hogy az an an 1 an 2 an 3 Æan 4 rekurzio korlatos, de nem periodikus sorozatot de nial? 54. Adjunk meg olyan ; ; a0 ; a1 val os sz amokat, hogy az an an 1 an 2 rekurzio korlatos, divergens, de nem periodikus sorozatot de nialjon!

= 3 = 8 = 4( =1 =2 =2

+

+

)

=

=

+

+

64

Elekes Gy:

4.5. Genertor{fggvnyek Sokat markolunk (s sokat is fogunk).

...

...

Legyen a0 ; a1 ; a2 ; ; an ; tetsz leges sorozat. Ennek vgtelen sok elemre vonatkoz sszes inform i belefr egyetlen fggvnybe:

f (x) =

1 X n=0

an xn

DEF. A fenti f (x) az an sorozat genertor{fggvnye.

Megjegyzs: Analzisb l (lsd Taylor{sorok) ismert, hogy f {b l az an egytthatk egyrtelmen meghatrozhatak, ha a vgtelen sor nem sak x {ra konvergens. Ekkor a konvergen ia{tartomny egy (esetleg vgtelen) intervallum, s a sor tagonknt dieren ilhat s integrlhat. DEF. Az an sorozat exponen ilis genertor{fggvnye:

=0

g(x) =

1 a X n n x

n=0

n!

Megjegyzs: Az an egytthatk g {b l is egyrtelmen visszanyerhet ek; az el z megjegyzs minden egyes lltsa rvnyes g {re is. Az albbi feladatokat az x helybe alkalmas fggvnyt helyettestve, esetleg derivlssal ill. integrlssal oldhatod meg, felhasznlva, hogy a vgtelen mrtani sor sszege ismert: jxj < esetn

1

1 + x1 + x2 + . . . + xn + . . . = 1 1 x ;

illetve abbl, hogy

1 1 ex = 1 + x + x2 + . . . + 1!

2!

1 xn + . . . n!

=2

n sorozat 55. Hatrozd meg az an a) genertor{fggvnyt; b) exponen ilis genertor{fggvnyt! ! 56. Legyen a0 , a1 , an an 1 an 2 , ha n . (a) Irjuk fel az (an ) sorozat g x generatorf uggvenyet kozvetlen ul a rekurzi obol! (b) Fejts uk sorba g x -et es gy hatarozzuk meg an {et!

=1

=4

()

=4

()

4

2

65

Kombinatorika feladatok 57. Minek a genertor{fggvnye a) 1+1 x ; b) 1 13x ;

) 1 1x2 ; d) 1+1x2 ?

! ! ! !

2

58. Minek az exponen ilis genertor{fggvnye ex ?

1 2x + 3 hatvnysort! 1 60. Milyen hatvnysor lltja el

(1 x)2 {t? 61. (folytats) Ht 1 r {t? ! (1 x) 62. Minek a genertorfggvnye 1 a) 1 4x + 4x2 ; 1 ? ! b) 2 x 10x + 25 1 1 1 1 x 63. Az (1 + x)(1 + 3x) = 2 (1 + x) 2 (1 + 3x) azonossg felhasznlsval keresd meg a bal oldal hatvnysort! ! 1 64. (folytats) Keress hasonl felbontst (s abbl hatvnysort) az (1 + x)(1 + 3x) 59. Keresd meg

fggvnyhez is! 65. Melyik sorozat genertorfggvnye a) 2; b)

1 1 3x + 2x 1 ? x2 + 5x + 6

Fibona

i s a turista Klnsen jl hasznlhatk a genertor{fggvnyek rekurzv sorozatok n{edik tagjnak expli it felrsra. 66. Mutasd meg, hogy a Fibona

i{sorozat f genertorfggvnye teljesti az f x xf x x2 f x egyenl sget! Adj ebb l j bizonytst az

1+ ( )+

azonossgra!

()

( )=

p n p n 1 1 + 1 1 5 5 p Fn = p 5 2 5 2

+ + + +

67. Hat arozd meg F0 F1 F2 Fn -t! 68. A Bergeng iba ltogat turista (29. feladat) rekurzija: t0 , t1 tn 1 tn 2 . Bizonytsd be, hogy a sorozat genertor{fggvnyre xf x x2 f x teljesl s adj ebb l kpletet tn {re!

+2 1+ ( )+2 ( )

=1

= 1, tn = f (x) =

66

Elekes Gy:

69. Oldd meg az 50. feladatot genertor{fggvnnyel is! n X n 70. A 30. feladatban az S0 , Sn S (ha n ) rekurzira jutotk n k k=1 tunk. Mutasd meg, hogy Sn exponen ilis genertor{fggvnye

=1

=

g(x) =

1

1 X

Sn n x = n=0 n!

2

1

ex

;

s bizonytsd be ebb l, hogy

1 X

Sn =

k=0

kn 2k+1 :

()

71. Jelolje Pk n az n termeszetes szam felbont asainak szam at pozitv egeszek osszegere, melyek mindegyike legfeljebb k . Biz be:

pk (x) =

1 X n=k

Pk (n)xn =

1

: x)(1 x2 ) . . . (1 xk )

(1

()

72. Jelolje Pmax=k n az n termeszetes szam felbont asainak sz am at pozitv egeszek osszegere, melyek koz ul a legnagyobb eppen k . Biz be:

pk (x) =

( )

73. Jelolje P n; k az egesz osszegere.

1 X n=k

n

Pmax=k (n)xn =

75.

pk (x) =

x)(1

termeszetes szam felbont asainak sz am at

P (n; k) = 74. Biz be:

(1

xk : x2 ) . . . (1 xk )

1 X n=k

k X i=1

P (n; k)xn =

(1

k

darab pozitv

P (n k; i):

x)(1

xk : x2 ) . . . (1 xk )

Bizonytsd be, hogy minden n termeszetes sz amra a supa k ul onb oz}o osszeadand obol all o osszegel}oallt asok szama egyenl} o a supa p aratlan osszeadandobol allo osszegel}oallt asok szam aval. (Az osszeadandok sorrendje nem sz amt.)

67


5. fejezet

Grfok II.

5.1. A Ramsey{ttelkr

(Posa Lajos nyom an)

Vgtelen Ramsey{ttelek. 1. Legyen H a termszetes szmok tetsz leges vgtelen rszhalmaza (ha gy tetszik, szigoran nv rszsorozata). Mutasd meg, hogy vagy van H {ban vgtelen sok szm (nem kell az egsz H ), amelyek kzt brmely kett nek van egynl nagyobb kzs osztja, vagy van benne vgtelen sok, pronknt relatv prm (azaz olyanok, hogy e rszben brmely kett legnagyobb kzs osztja egy). 2. Legyen H olyan, mint az el z feladatban! Mutasd meg, hogy vagy van benne vgtelen sok szm, hogy brmely kett osztja egymst, vagy van vgtelen sok, hogy semelyik kett nem osztja egymsnak! 3. Mit mondhatunk, ha vgtelen sok pont kztt minden prt vagy piros, vagy kk sznnel sszektnk? ! 4. Mit mondhatunk, ha vgtelen sok pont kztt bizonyos prokat sszektnk (feketvel), bizonyosakat pedig nem? ! 5. Ramsey ttele vgtelen grfokra: Vgtelen teljes grf (jellse: K1 ) leit tetsz legesen sznezve kt sznnel, mindenkppen keletkezik egyszn lekb l ll K1 . tfogalmazs: brmely vgtelen grfban van vagy vgtelen teljes, vagy vgtelen res rszgrf.

Ramsey ttelei vges grfokra. 6. Egy hatszg oldalait s tlit (sszesen 15 vonalat) tetsz legesen piros s kk sznekkel hztl be. Mutasd meg, hogy a) brmely s sbl indul hrom egyszn vonal. b) biztosan rajzoltl hrom egyszn vonalbl ll hromszget.

68

Elekes Gy:

7. Igaz{e ugyanez tszgre? s ht{ vagy tbb oldalra? Mutasd meg, hogy n pont kztt a prokat pirossal s kkkel sszektve leg-

8.

n(n

1)(n 5) 24

darab, hrom egyszn vonallal hatrolt hromszg kealbb letkezik! 9. Tizenht tuds hrom tmrl folytat levelezst egymssal (brmely kett mindig ugyanarrl, de egy harmadik rhat az els kett nek kt klnbz r l). Bizonytsd be, hogy van kztk hrom, akik pronknt ugyanarrl leveleznek! 10. Mutasd meg, hogy 16 tudsra az llts nem igaz! ! DEF. n pont teljes grf (jellse: Kn ): minden pont minden msikkal ssze van ktve.

Ramsey ttele vges grfokra: Tetsz leges k s l termszetes szmokhoz van olyan R k; l , hogy egy n R k; l pont teljes grf leit kt osztlyba osztva (pl. pirossal s kkkel megrajzolva) biztosan keletkezik vagy az egyik tpus (piros) lekb l Kk , vagy a msik tpus (kk) lekb l Kl . tfogalmazs: brmely, legalbb R k; l pont grfban vagy van k pont teljes, vagy van l pont res rszgrf. DEF. Adot k s l esetn a legkisebb R k; l {et R k; l {lel jelljk. 11. Mutasd meg, hogy ha R k ; l s R k; l ltezik, akkor R k; l is, s R k; l R k ; l R k; l . 12. (folytats) Bizonytsd be Ramsey ttelt s mutasd meg, hogy R k; l

( )

( )

( )

( )

( 1 )+ (

(

2 1 . 13. Mennyi R (3; 3)?

( ) ( ) 1 ) ( 1) 1)

( )

( )

k+l k

(3 4) = 9

10

!

14. Mutasd meg, hogy R ; . (Nem sajthiba! A trivilis, lsd 12. feladat.) 15. Bizonytsd be, hogy tetsz leges k s l termszetes szmokhoz van olyan M k; l , hogy egy n M k; l tag sorozatban mindig tallhat k tag nvekv vagy l tag skken rszsorozat! ! 16. Egyszeren igazolhat, hogy a d dimenzis trben legfeljebb d olyan pont adhat meg, melyek kztt a fellp sszes tvolsg egyenl . Megadhat{e vgtelen sok, ha megengednk kt klnbz tvolsgot (de tbbet nem)? 2 17. Mutass olyan k pont grfot, amelyben nin s se teljes, se res k {pont rsz! ponton is! 18. (folytats) Mutass hasonlt k 2 k 19. (folytats) Bizonytsd be, hogy ponton ez lehetetlen! !

( )

( )

+1

(

1)

3 2

Erd s ttele:

1

2k=2 < R(k; k) < 22k :

Megjegyzs: A fels be sls egyszer: l. el z feladat. Az als be sls volt az els , valsznsgszmtst hasznl eredmny a grfelmletben.

69

Kombinatorika feladatok 20. Mutasd meg, hogy ha

2

n k

2( 2 ) (2) < 2( 2 ) ; k

n

n

akkor az n pont grf lei kt sznel sznezhet ek gy, hogy ne keletkezzen egyszn Kk ! ! 21. (folytats) Bizonytsd be ebb l Erd s als be slst! Sejts (megoldatlan): ltezik

lim k!1 Megjegyzs: Erd s ttele szerint

p

p k

2<

!

R(k; k): p k

R (k; k) < 4.

Ramsey ttelei tbb sznre. Vgtelen Ramsey ttel tbb sznre: Legyen s 2 termszetes szm. K1 leit s sznnel sznezve mindenkppen keletkezik supa egyszn lb l ll K1 . Vges Ramsey ttel tbb sznre: Tetsz leges s s k1 ; k2 ; . . . ; ks termszetes szmokhoz van olyan Rs (k1 ; k2 ; . . . ; ks ), hogy egy n R pont teljes grf leit s osztlyba osztva (pl. pirossal, kkkel, . . . , sszesen s sznnel megrajzolva) biztosan keletkezik vagy az els tpus (piros) lekb l Kk1 , vagy a msodik tpus (kk) lekb l Kk2 , . . ., vagy vagy az s{edik tpus lekb l Kks . DEF. A legkisebb ilyen R{et Rs (k1 ; k2 ; . . . ; ks ){sel jelljk. 22. Bizonytsd be a tbbszn Ramsey{tteleket!

23.

Mutasd meg, hogy

Rs (3; 3; . . . ; 3) 1 + s!(1 +

24.

!

1 1 1 1! + 2! + . . . + s! ) = de s! e

(S hur ttele) Minden s{hez van olyan N (s), hogy az 1; 2; . . . ; N szmokat

brhogyan osztva

s osztlyba, valamelyikben megoldhat lesz az x+y =z

egyenlet. (Ez azt jelenti, hogy legalbb egy osztlyban tallhat hrom | nem felttlenl klnbz | szm, x, y s z , melyekre a fenti egyenl sg teljesl. A ttelben szerepl minden bet | s; N; x; y; z | pozitv egsz szmot jelent.)

70

Elekes Gy:

A vges s vgtelen kztti kap solat. A Knig{lemma. 25. Mutass olyan vgtelen pont gykeres ft, melyben a gykrb l indulva tallhat akrmilyen hossz t (azaz van 10{nl hosszabb is, van 10 {nl hosszabb is, stb.), de vgtelen t nin s! !

10

DEF. Egy r pontban gykerez fa k{adik szintjnek nevezzk az r{t l k tvolsgra lv (k l ton elrhet ) pontok halmazt.

Knig{lemma: Ha egy vgtelen fa minden szintje nem-res s vges szm

26. 27.

pontbl ll, akkor van a fban vgtelen t.

!

Igazold a fenti lltst!

Mutasd meg, hogy a vgtelen Ramsey ttelekb l a Knig{lemma segtsgvel a vges Ramsey ttelek is kvetkeznek!

Gyakorl feladatok 28. Mondjuk azt, hogy egy (dntetlen nlkli) krmrk zs eredmnye a jtkosok egy fJ1 ; J2 ; Jr g rszhalmazn egyrtelm, ha i < k esetn Ji legy zte Jk {t. a) Bizonytsd be, hogy minden r{hez van olyan f r , hogy brmely n f r rsztvev s krmrk zs utn lesz r olyan versenyz , akik halmazn az eredmny egyrtelm; b) Igaz-e, hogy r 1 jtkos kztt mindig van r ilyen? !

...

()

()

2

29. Mutasd meg, a vgtelen Ramsey ttel"{b l hogyan kvetkezik, hogy minden vgtelen sorozatnak van vgtelen monoton rszsorozata!

+1

30. Bizonytsd be, hogy k l tag sorozatban mindig tallhat k tag nvekv

vagy l tag skken rszsorozat! ! 31.

s(s + 1)

2

ember gylt ssze valahol. Brmely hrmat kivlasztva, van ezek kztt legalbb kett , akik ismerik egymst. Mutasd meg, hogy biztosan van s ember, akik egymst mindnyjan ismerik! (Az ismeretsgek kl snsek.)

32. Legyen adva vgtelen sok tengely{prhuzamos tglalap supa egsz koordintj s sokkal az els (azaz jobb fels ) sknegyedben gy, hogy mindegyikk bal als s sa az orig. Igazoljuk, hogy kivlaszthat bel lk vgtelen sok olyan, melyek kztt brmely kett b l az egyik tartalmazza a msikat!


71

Szmtani sorozatok. Van der Waerden ttele. 33. Bontsuk fel a termszetes szmok halmazt kt rszre gy, hogy egyik se tartalmazzon vgtelen szmtani sorozatot! 34. (folytats) Ugyanez a feladat mrtani sorozatokra.

Van der Waerden ttele: Legyen k tetsz leges nem-negatv egsz. A term-

szetes szmok halmazt akrhogyan vges sok rszre osztva valamelyik rszben lesz k tag szmtani sorozat. Megjegyzs: rdemes fel gyelni arra, hogy | br akrmekkora vges rszsorozat van | vgtelen nem felttlenl lesz. (Lsd 33. feladat.)

Euklideszi Ramsey{ttelek. 35. A sk pontjait (egyenknt kln, tetsz legesen) kisznezte valaki pirosra, srgra s kkre. Mutasd meg, hogy mindenkppen keletkezett egyszn, egymstl egysgnyi tvolsgban lv pontpr! ! 36. (folytats) Mutasd meg, hogy az el z llts kilen sznre nem igaz! 37. (folytats) Mi a helyzet ht sznnel?

! !

38. Sznezd ki a sk pontjait kt sznnel gy, hogy semelyik egysg-oldal szablyos hromszgnek se legyen mind a hrom s sa egyszn! !

Sejts (megoldatlan): Az el z feladatnak megfelel brmely sznezsben br-

0

mely < a

s sokkal.

6= 1{hez tallhat a oldal szablyos hromszg supa egyszn

39. Tegyk fel, hogy a sk pontjait kisznezte valaki pirosra s kkre gy, hogy mindkt sznt hasznlta. Mutasd meg, hogy mindenkppen keletkezett egymstl egysgnyi tvolsgban lv pontpr, melynek egyik tagja piros, a msik kk! !

5.2. Extremlis grfok

72

Elekes Gy:

Cseresznyk, krk, hromszgek . . . 40. Egy G grfban seresznynek neveznk kt, egy pontbl indul lt (azaz egy kt lb l ll utat, ha gy tetszik). a) Ha G{nek n pontja van, melyekre rendre d1 ; d2 ; dn l illeszkedik, hny

seresznye van G{ben? b) n pont, e l grfban legalbb hny seresznye van?

) Mutasd meg, hogy ha egy n pont, e l grfban nin s hromszg, akkor

...

legfeljebb

e(n

2

2) seresznye lehet benne.

d) Bizonytsd be, hogy egy n pont, hromszgmentes grfnak legfeljebb le van! 2 e) Mutass (minden n{re) n pont, b n l, hromszgmentes grfot!

n2

4

4

41. (folytats) Tegyk fel, hogy G{ben nin s ngy pont kr! a) Mutasd meg, hogy G{ben legfeljebb n seresznye lehet! n le lehet! b) Igazold, hogy G{nek legfeljebb n3=2 ) Mutass vgtelen sok n{re olyan n pont grfot, amelyben nin s ngy pont pn le van! kr s legalbb n3=2

1 2

1 2

2 + 14

Turn ttele DEF. Jells: bx jelentse az x egsz rszt, azaz a legnagyobb, x{nl nem nagyobb egszt.

DEF. r{osztly grf: a pontokat tetsz legesen r osztlyba osztjuk s a klnbz

osztlyba es pontprokat mind sszektjk. DEF. n{pont r{osztly Turn{grf gy keletkezik, hogy az n pontot a lehet legegyenletesebben r osztlyba osztjuk (ezek egyenknt n=r pontot tartalmaznak, ha ez egsz szm; bn=r {t ill. bn=r {et, ha nem) s a klnbz osztlyba es pontprokat mind sszektjk. Az r{osztly n pont Turn{grf leinek szmt Tr n {nel jelljk. 42. Igazold, hogy az n{pont pros grfok kzl a ktosztly Turn{grfnak van a legtbb le! Mondj hasonl lltst az r{osztly Turn{grfokra is!

+1

()

llts: az

n{pont r{osztly

le. 43. Mutasd meg, hogy

grfok kztt a Turn{grfnak van a legtbb

2 , ha n = 2k ; T2 (n) = k k(k + 1) , ha n = 2k + 1. 2 n pros; = (nn2=4 1)=4 ,, ha ha n pratlan. = bn2=4

73

Kombinatorika feladatok 44. Igazold, hogy ha egy

n pont grfban nin s hromszg, akkor lszma e T2 (n) = bn2 =4 :

!

T3 (n){re a fenti, T2 (n){re vonatkozhoz hasonl kpleteket! Bizonytsd be, hogy ha egy n pont grfban nin s K4 (teljes ngypont rsz-

45. Keress 46.

grf), akkor lszma

e T3 (n) = bn2 =3 :

!

Turn ttele. Ha egy n{pont grf nem tartalmaz Kr+1 {et (teljes r+1{ pont rszgrfot) akkor legfeljebb Tr

(n) le lehet.

DEF. Azt mondjuk, hogy a G grf x pontjt szimmetrizljuk a vele ssze nem

kttt y ponthoz, ha elhagyjuk az x{b l indul leket s x{et pontosan azokkal az egyb s sokkal ktjk ssze, amelyekkel y is van.

47. Mutasd meg, hogy ha utn se lesz!

G{ben

nem volt teljes k {szg, akkor a szimmetrizls

48. Szimmetrizld egy maximlis fok ponthoz a vele ssze nem kttteket! Bizonytsd be, hogy a) minden szimmetrizlt pont ssze lesz ktve minden nem szimmetrizlttal; b) ha az eredeti grfban nem volt Kk , akkor a nem szimmetrizltak ltal meghatrozott rszgrfban nem lesz Kk 1 !

49. (folytats) Bizonytsd be ebb l Turn ttelt!

50. (folytats) Keress induk is bizonytst is Turn ttelre!

Tvolsgok a skban 51. Igazold, hogy ha egy hromszg nem hegyesszg, akkor leghosszabb oldala a p legrvidebbnek legalbb {szerese! !

2

52. Legyen adva a sk ngy pontja. Mutasd meg, hogy (a) ha nin s hrom egy egyenesen, akkor van hrom, amelyek nem hegyesszg hromszget hatroznak meg. (b) ha kztk p a legnagyobb tvolsg D, akkor van kett , amelyek tvolsga D= .

2

53. Tegyk fel, hogy a sk n pontja kztt a legnagyobb tvolsg D. Mutasd meg, hogy a) ha van a pontok kztt olyan, amelyikt l legalbb hrom msik van D tvolsgra, akkor olyan is kell legyen, amelyik sak egy msiktl van D{re! b) a D hosszsg szakaszok szma n.

74

Elekes Gy:

54. Bizonytd be, hogy ha a sk tetsz leges n pontja kztt a legnagyobb tvolsg p D, akkor legfeljebb bn2 = db. olyan pontpr van, amelyek tvolsga D= {nl nagyobb.

3

2

55. Mutassunk pldt (el szr kis n{ekre, de aztn nagy n{ek esetn is) arra, hogy valban lehet bn2 = ilyen pontpr. (S t mg a ; D{nl tvolabbiakbl is lehet ennyi!) 56. Bizonytsd be, hogy a sk n pontja kztt ugyanaz a tvolsg legfeljebb n3=2 {

3

0 999

szer fordulhat el !

. . . ; vn olyan skbeli vektorok, melyek mindegyikre jvi j 1. j prra lesz jvi + vj j 1? !

57. Legyenek v1 ; v2 ; Legalbb hny i,

ltalnostott Turn{szmok DEF. A G grf Turn{szmnak nevezzk s tG (n){nel jelljk azt a maximlis lszmot, ahny le egy n pont grfnak lehet, ha nem tartalmazza az adott G-t. (Ezzel a jellssel Turn ttele azt mondja, hogy tKr n Tr 1 n .)

( )=

58. Legfeljebb hny le lehet egy a) kr b) pratlan kr?

n pont grfnak, ha nin s benne

59. Hny le lehet egy nem sszefgg ,

()

!

n pont grfnak?

60. Hny le lehet egy n pont grfnak, ha nin s benne a) kt l t b) hrom l t? 61. 62.

! Legfeljebb hny le lehet egy n pont grfnak, ha nin s benne k l sillag? ! Hny le lehet egy n pont grfnak, ha nin s benne ngy pont kr? !

63. Mutasd meg, hogy pros grf Turn{szma o n2 , pontosabban, ha mindkt osztlyban legfeljebb k pont van, akkor tG n n2 1=k k n !

()

( )

+ 21

(n2)

64. (folytats) Igazold, hogy ha G nem pros, akkor Turn{szma nem lehet o !

!

5.3. Minimax ttelek Minimax tteleknek az olyan lltsokat nevezzk, amelyek kt mennyisgr l azt lltjk, hogy az egyik lehetsges rtkeinek maximuma egyenl a msik lehetsges rtkeinek minimumval. Ilyen pl. a 2.7. szakaszban szerepl K nig{ ttel (2.144. feladat).

75


Intervallum{rendszerek 65. Egy nap sokan megfordultak egy tenisz{telepen, de minden jtkos sak egyszer. Ha mindenki mindenkivel tallkozott, igaz{e, hogy valamikor mindnyjan egyszerre ott voltak? (ez mg nem minimax ttel) 66. (folytats) Legyenek a1 ; b1 ; a2 ; b2 ; ; an ; bn zrt intervallumok a szmegyenesen. (a) Bizonytsd be, hogy ha brmely kett nek van kzs pontja, akkor van olyan pont is, ami mindegyikben benne van. (b) Adj mdszert (rj programot) ami keres ilyen pontot, ha van; ellenkez

esetben pedig mutat kt diszjunkt (azaz kzs pont nlkli) intervallumot. Megjegyzs: a feladat (a) rsze sem trivilis! J megoldsbl a (b) alatti eljrs is kijn. 67. Egy folyn egy hajzsi vllalat sok teherhajja jr, mindegyik mindig adott kikt k kztt oda{vissza. Szeretnk a hajkat ellen rizni, valban elvgzik{e hetente az el rt szm fordult. Nem szksges a sok kis kikt mindegyikbe kln egy{egy ellen rt kldenik, mert az egyes foly{szakaszokon ltalban tbb hajjuk is jr. A parton terveznek ellen rz pontokat fellltani gy, hogy minden haj (lland, kijellt tja sorn) mindig legalbb egy el tt elhaladjon. Adj mdszert a minimlis szm ellen rz pont megkeressre! 68. (folytats) (a) adj mdszert, ami tetsz leges (a kett vel korbbi feladat felttelt esetleg nem teljest ) intervallumrendszert a lehet legkevesebb olyan soportba oszt, hogy egy soporton bell mr az intervallumoknak van kzs pontjuk. (b) Mutasd meg, hogy az ilyen soportok szma nem lehet kisebb, mint a pronknt diszjunkt (azaz kzs pont nlkli) intervallumok maximlis szma. ( ) Bizonytsd be, hogy a (b) alatti kt mennyisg egyenl ! (Ez mr minimax ttel!) 69. Adj mdszert, ami tetsz leges intervallumrendszerhez kikeres egy pontot, ami a lehet legtbb intervallumban van benne. 70. Adj mdszert, ami tetsz leges intervallumokat a lehet legkevesebb olyan soportba oszt, amiken bell az intervallumok diszjunktak. 71. Mutasd meg, hogy az el z kt feladatban szerepl maximum ill. minimum ugyanaz. 72. Igazold, hogy tetsz leges intervallum{rendszer szakaszait ki lehet hzni piros s kk tollal gy, hogy az egyenes minden egyes pontja lnyegben ugyanannyi" piros ill. kk szakaszban legyen benne. (Itt a lnyegben ugyanannyi" gy rtend , hogy brmely pontban a r illeszked pirosak ill. kkek szma kzti eltrs nem tbb egynl. Ezek a mennyisgek klnbz pontokban nagyon klnbz ek lehetnek.)

[

℄[

℄ ... [

℄

76

73.

Elekes Gy: (folytats) Mutasd meg, hogy minden k

[0 1)

[ )[ [0 1)

2{re ltezik ilyen egyenletes sznezs!

) ... [

)

74. Legyen adva ; {ben az a1 ; b1 ; a2 ; b2 ; ; an ; bn intervallumok rendszere, melyek egyestse az egsz ; . (Minden intervallum balrl zrt, jobbrl nylt!) a) Adj mdszert, ami kivlasztja a lehet legkevesebb ai ; bi {t, amelyek lefedik a teljes ; {et! b) Adj mdszert, ami megkeresi a lehet legtbb olyan pontot ; {ben, melyek kzl semelyik kett sem esik egytt egy intervallumba!

) Mi kze egymshoz az a) ill. b) rszeknek?

[0 1)

75.

[

)

[0 1)

Hrom hzaspr mind a hat tagja kln{kln megltogat egy (hetedik) beteget. Mind a hrom frj tallkozik kt felesggel. Mutasd meg, hogy valamelyik frjnek tallkoznia kellett a sajt felesgvel is.

Tobbszorosen osszef ugg}o grafok. Menger tetelei. DEF. Az sszefgg G grf k{szorosan elsszefgg , semelyik k el elhagyasa sem vgja szt; k{szorosan pontsszefgg , ha jV j k + 1 s semelyik k pont elhagyasa sem vgja szt. (A pontszmra vonatkoz felttel, mint a 2{ osszef ugg} osegnel, Kk {t zrja ki.)

76. Bizonytsd be, hogy k {szorosan pontsszefgg grf k {szorosan elsszefgg is. 77. 78.

k{szorosan pontsszefgg grfhoz egy uj su sot hozzaveve es azt legalabb k regivel osszek otve u jra k {szorosan pontsszefgg grfot kapunk. Legyen jV (G)j 2. Ha b armaly x; y 2 V (G) (klnbz ) s u sp ar kozott (a) legalabb k elidegen u t letezik, akkor a G gr af k {szorosan elsszefgg ; (b) legalabb k kozos bels}o pont nelk uli u t letezik, akkor a G gr af k {szorosan pontsszefgg .

DEF. Legyen adva egy grafban t darab elidegen x y ut: P1 ; P2 ; . . . ; Pt . Egy x{b}ol indul o P0 u t javt o u t, ha a Pi (i 1) utak eleit nem hasznalja az x ! y termeszetes ir anyban, legfeljebb fordtva.

79. Tegy uk fel, hogy x{b}ol eljuthatunk y {ba javt ou ton. Bizonytsd be, hogy letezik t darab elidegen x y u t is. !

+1

...

80. Tegy uk fel, hogy P1 ; P2 ; ; Pt maximalis sz am u elidegen x be, hogy egy-egy alkalmas el uket t orolve megsz} unik az x es osszek ottetes.

El{Menger t etel. Tetsz}oleges (iranytatlan) grafban elidegen x{y utak maximalis szama = x-et y-tol elvago elek minimalis szama.

y ut. Bizonytsd y pontok kozotti

!

77


DEF. Legyen adva egy grafban t darab kozos bels}o pont nelkuli x y ut: P1 ; P2 ; . . . ; Pt . Egy x{b}ol indul o S seta javt o seta, ha (1) x{bol indul, de nem a Pi {k valamelyik elen; (2) el nem ismetl}odhet; (3) s u s ismetl}odhet, de ... (4) ... ha egy Pi {re lep unk, akkor azon kotelez}o legalabb egy lepest vissza (x fele) menni.

Megjegyzs: (3){bol es (4){b}ol kovetkezik, hogy a Pi {ken lev}o egy-egy s u sot legfeljebb ketszer erinthet unk [legfeljebb egyszer lephet unk bele a Pi {n utana kovetkez}o pontbol es ugyan sak legfeljebb egyszer lephet unk ra k uls}o pontbol | itt hasznaljuk (3){at es (4){et℄. 81. Tegy uk fel, hogy x{b}ol letezik y {ba javt o seta. Bizonytsd be, hogy letezik t darab kozos bels}o pont nelk uli x y u t is.

=

+1 !

(xb), (by), (a ) elekb}ol =x b a b y

Megjegyzs: Ha a graf a P1 x a b y u tbol es az ll, akkor javt a o UTON nem erhet} o el y , de letezik S javt o seta; van is ket f uggetlen u t.

...

82. Tegy uk fel, hogy nin s a grafban x y el es legyen P1 ; P2 ; ; Pt maximalis sz am u kozos bels}o pont nelk uli x y u t. Bizonytsd be, hogy egy-egy alkalmas pontjukat t orolve megsz} unik az x es y pontok kozotti osszek ottetes. !

Pont{Menger t etel. Ha egy (iranytatlan) grafban nem letezik (x; y ) el, akkor

kozos bels}o pont nelk uli x{y utak maximalis sz ama = x-et y-tol elvago su sok minimalis szama.

83. Egy k {szorosan pont osszef ugg}o grafban kijelolt valaki legfeljebb k darab Ai

s u sot es legfeljebb k darab Bj s u sot. Legal ab h any kozos bels}o pont nelk uli Ai Bj ut letezik?

84.

Mutasd meg, hogy k {szorosan pont osszef ugg} o gr afban b armely egy koron van!

k

darab s u s

Reszben rendezett halmazok DEF. Azt modjuk, hogy hH; i reszben rendezett halmaz (a rela ioval), ha

irrre exv, azaz 8x 2 H {ra x 6 x; tranzitv, azaz x y es y z eseten x z . Peld aul tetsz} oleges halmazrendszer ilyen a " tartalmazasi rela iora nezve, (i) (ii)

vagy termeszetes szamok b armely reszhalmaza az oszthatos agi rela iora nezve. Persze minden (teljesen) rendezett halmaz is ilyen. 85. Mutasd meg, hogy teljes ulhet.

antiszimmetrikus is, azaz x y es y x, egyszerre nem

78

Elekes Gy:

86. De ni aljuk a kovetkez}o reszbenrendezest az intervallumokon: [a; b℄ megel}ozi [ ; d℄-t, ha b < . Igaz-e, hogy b armely reszben rendezett halmaz reprezent alhat o gy? Szokas szerint akkor nevez unk maxim alisnak" egy halmazt, ha nem b} ovthet} o; ez nem jelenti azt, hogy n ala t obb elem} u sin s. Reszben rendezett halmazok koreben pedig egy elem akkor maximalis, ha nin s n ala nagyobb ( szerint); ez nem jelenti azt, hogy minden masn al nagyobb. 87. Letezik-e olyan reszben rendezett halmaz, amelyben minden elem maximalis?

DEF. Egy reszben rendezett halmaz egy reszhalmaza lan , ha barmely ket eleme osszehasonltott. Antil an , ha semelyik ket eleme sem osszehasonltott. 88. Reszben rendezett halmaz maximalis elemei antilan ot alkotnak. 89. (folytats) (a) Mutass peld at arra, hogy ezek a maximalis elemek nem feltetlen ul alkotnak maxim alis meret} u antilan ot. (b) Mi a helyzet, ha feltessz uk, hogy minden elem benne van egy maximalis meret} u antilan ban?

esi probl 90. (Utemez ema) Egy reszben rendezett halmaz elemei reprezentaljanak egy{egy napi teend}oket, a rela io pedig azt, hogy egyiket a m asik utan lehet sak elvegezni. Tegy uk fel, hogy korlatlan sz am u munk as all rendelkezes unkre. Bizonytsd be, hogy az osszes feladat elvegzesehez sz ukseges id} o= = a legnagyobb lan merete.

91. Dilworth ttele: lan okra bont ashoz sz ukseges lan ok min. sz ama = = a legnagyobb antilan merete. 92. Ha egy reszben rendezett halmaz b armely ket maximalis meret} u antilan anak van kozos eleme, akkor az osszesnek is van. 93. Igaz-e, hogy reszben rendezett halmazokban p aronkent diszjunkt legnagyobb antilan ok max. sz ama = az osszes legnagyobb antilan ot lefog o elemek min. sz ama?

5.4. A Prfer{kd. Cayley ttele: Az

f1; 2; . . . ; ng pontokon nn 2 fa adhat meg.

Megjegyzs: 1. E ttelben klnbz nek szmoljuk az egymssal izomorf fkat is, pl. hrom ponton az 1-2-3 utat s az 1-3-2 utat. Megjegyzs: 2. Cayley ttelre sok bizonyts ismeretes. Sokig nem talltak azonban olyant, ami kzvetlen megfeleltetst ad az n (szmozott) pont fk s

79


1 2 ... 1 2 ...

2

az ; ; ; n szmokbl kpezhet n tag sorozatok kztt. Vgl Prfer jrt sikerrel; az eredmnyt tallod az albbiakban: Az f ; ; ; ng pontokon adott T1 fhoz rendeljnk n tag sorozatot a kvetkez kppen: Hagyjuk el a fa els fok pontjai kzl a legkisebb indext, s szomszdja (a vele sszekttt egyetlen pont) indext jegyezzk fel; legyen ez a1 . Ismteljk az eljrst a maradk T2 rszfra (gy tovbbi ai pontokat s Ti rszfkat kapunk), amg sak kt pont marad. Akkor lljunk le. DEF. A fenti sorozat a fa Prfer{kdja. 94. Mutasd meg, hogy az eljrs befejezsekor megmarad kt pont egyike az n index. ! 95. A Prfer{kdban az i szm ppen di {szer fordul el , ahol di az i pont foka.

96.

2

1

Mutasd meg, hogy minden kdhoz pontosan egy fa tartozik! 97. Bizonytsd be Cayley ttelt! 98. Legyen d1 d2 dn n olyan sorozat, melyre P di Mutasd meg, hogy ltezik n pont fa ilyen fokszmokkal! 99. (folytats) Hny ilyen fa van az ; ; ; n pontokon?

1

...

1 2 ...

= 2(n 1).

!

80

Elekes Gy:

6. fejezet

Algoritmusok II. (Gr af algoritmusok) Hogyan troljunk grfokat szmtgpben? DEF. Grf trolsa tmbben (szoksos az sszektttsgi mtrix" elnevezs).

n pont grfhoz n n{es ktdimenzis tmbt hasznlhatunk, melyben 1 , ha az i{edik s j {edik pont kztt van l; A[i; j ℄ =

0

, ha nin s.

[ ℄

( )

El nye: a kzvetlenl elrhet A i; j elem azonnal adja az inform it az i; j pontprrl. Htrnya: ritka" grf (sok pont, de nem nagyon sok l) esetn a tmb tlnyom tbbsgben 0{kat tartalmaz | nem idelisan hasznlja ki a helyet. Megjegyzs: rdemes megemlteni azt az el nyt is, hogy ha a tmb elemeiben az lekre vonatkoz tovbbi inform it is trolunk (pl. a menetid t adott pontok kztt, amik plyaudvarokat reprezentlnak), akkor mellkhatsknt" maguk az eredeti 0{1{ek feleslegess vlnak. Megtehetjk pldul, hogy pozitv szm valdi adatot, negatv szm pedig nem ltez let jelent. Mg logikusabb az elfajul esetek kezelse az A i; j 1, ha nin s l ( tletnapig is vrhatsz; nin s vonat") s A i; i ( i{b l nmagba: nulla id ") jellsek hasznlata. DEF. Grf trolsa l{listkkal. Minden ponthoz kln{kln listban tartjuk a r illeszked lek msik vgpontjnak sorszmt. Kell persze (egy t ombben) minden ponthoz egy-egy mutat o a bel} ole indul o elek listaj anak elejere | es neha elszer} u a vegere is. El nye: sak annyi lr l kell inform it trolnunk, amennyi tnylegesen van a grfban. Htrnya: nem tudjuk kzvetlenl eldnteni, kt adott pont kztt vezet-e l; ehhez egyikk l{listjt kell vgigvizsglnunk.

[ ℄=0

[ ℄=

Megjegyzs: Mindket valtozat alkalmas ir anytott gr afok t arol as ara is. 1. Adott n s u s u, e el} u ir anytott grafhoz kesztsd el az elek megfordt as aval keletkez}o gr af el-list ait O n e id}oben! 2. Rendezd adott n s u s u, e el} u graf el-list ait a masik vegpontok szerint O n e id} oben!

( + )

( +)

81


6.1. sszefgg sgi algoritmusok Szlessgi s mlysgi keress 3. H any lepesben tudod megkeresni egy n pont u, e el} u gr af sszefgg komponenseit, ha a grafot t ombben t aroljuk? ha el{list 4. (folytats) Es akkal?

5.

Mutasd meg, hogy t ombben t arolt graf eseten MINDEN algoritmus rakenyszerthet} o| eleg rosszindulat u" grafon |, hogy MINDEN pontpar osszek otottsegere rakerdezzen (azaz kiolvassa a t ombb} ol).

DEF. Szlessgi keress: ha minden, mar elert pontbol minden, onnan elerhet}ot megkeres unk. Szlessgi keres fa: az u jonnan elert s u sokba erkez}o elek. DEF. Mlysgi keress: ha ha minden, mar elert pontbol mindig sak egyetlen u jat keres unk es arra haladunk tovabb. Mlysgi keres fa: az u jonnan elert

s u sokba erkez}o elek.

6. A szlessgi keress szintjei a kezd}oponttol val o t avolsagnak felelnek meg.

7. Val ostsd meg a szlessgi keresst (megfelel}o t omb okkel es listakkal) O id}oben!

(n + e)

8. Hogyan keresnel legrvidebb tat ket adott s u s kozott? 9. Egy mlysgi keres f aban nem szerepl} o lek sak a fa azonos agara es} o s u sokat kothetnek ossze. 10. Val ostsd meg a mlysgi keresst (megfelel}o t omb okkel es listakkal) id}oben!

O(n + e)

11. Adj algoritmust ktszeres sszefgg sg vizsg alatara, mely sszefgg gr af eseten elsz amnyi id} oben m} uk odik. 12. Mutassunk polinomi alis algoritmust a kovetkez}o feladatra: Adott: G iranytatlan graf es harom su sa: x; y; z . Eldontend}o: letezik-e ut x-b}ol y -on at z -be? 13. Mutassunk polinomi alis algoritmust a kovetkez}o feladatra: Adott: G iranytatlan graf es negy su sa: x1 ; x2 ; y1 ; y2 . Eldontend}o: letezik-e ket, teljesen kozos su s nelkuli xi | yj ut? (Tehat x1 |y1 es x2 |y2 jo, x1 |y2 es x2 |y1 is jo, de x1 |y1 es x2 |y1 nem.)

14. Adj elsz amnyi idej} u algoritmust irnytott grf er s sszefgg sgnek eldntsre.

15. 16.

Keress ktszeresen sszefgg komponeneseket lineris id ben. Keresd meg egy irnytott grf er sen sszefgg komponenseit lineris id ben.

82

17.

Elekes Gy: Keresd meg egy ketszeresen osszef ugg}o graf (a) f ul{felbont asat; (b) s{t szamoz asat.

A max{vissza sorrend Ebben a reszben kivetelesen t obbszoros eleket tartalmazo gr afokat is megenged unk. Ilyenkor e a multipli itassal sz amolt elsz amot jel oli.

DEF. Egy G graf V su shalmazanak max{vissza sorrendje V

0

= fx1; x2 ; . . . ; xng, . . . ; xi 1 g

ha b armely i > {ra az xi s u sb ol legalabb annyi el vezet az fx1 ; x2 ; halmazba, mint b armely kes} obbib}ol ugyanide.

=

...

18. (Nagamo hi{Ibaraki lemma): Ha V fx1 ; x2 ; ; xn g egy esetleg tobbsz or os el} u gr af egy max{vissza sorrendje, akkor xn 1 es xn szetvagas ahoz legal abb annyi elet kell elhagyni, mint xn foka. 19. (folytats) (Mader t etele) Tetsz}oleges iranytatlan grafban talalhato olyan x; y pontpar, melyek kozott az elidegen utak maximalis szama eppen y foka. !

20. 21.

Keress max{vissza sorrendet

O(e) id}oben.

Keress algoritmust k {szoros osszef ugg}oseg vizsg alat ara O

(ne) id}oben.

!

6.2. A Dijkstra{algoritmus. DEF. Slyozott l irnytott grf: minden (x; y ) lhez adott egy{egy w(x; y ) 0

szm. (Ezeket a tovbbiakban sly"{nak vagy kltsg"{nek, esetleg hossz"{ nak fogjuk nevezni.)

Minimlis sszsly t problmja:

Adott: n pont, m l G(V; E ) irnytott grf w

tovbb a) kt kijellt pont, p s q ; b) egy kijellt p pont;

) nin s kijellt pont.

:

E

7! R+

Keresend

slyozssal,

a) esetben: minimlis sszsly t p{b l q {ba; b) esetben: minimlis sszsly t p{b l az sszes tbbi pontba;

) esetben: minimlis sszsly t az sszes pontpr kztt. Megjegyzs: Mr a legegyszerbbnek tn a) esetben is n klnbz t jhet szba. Ezek szma mr 20{30 pont grfban is irrelisan nagy; a leggyorsabb szmtgpekkel sem kezelhet . Intelligensebb mdszert kell kitallni.

(

2)!

83


Nem ismeretes olyan eljrs, ami az a) esetet gy oldan meg, hogy kzben ne addna ki minden q 6 p{re a minimum, vagyis mellkesen ne a teljes b) esetet oldan meg. Ezrt rgtn az utbbival kezdjk az elemzst.

=

()

22. Jelljk a b) esetben minden x 2 V {re a keresett minimumot W x {szel! Nyilvnval, hogy W p . Tudsz-e tallni egyetlen q 6 p pontot, amire W q gyorsan meghatrozhat? !

( )=0

=

=

()

...

23. Tegyk fel, hogy egy kismadr mr el si seregte, hogy a p x0 ; x1 ; x2 ; ; xk 1 pontokra mennyi a keresett W xi . a) Hogyan keresnl olyan xk 2 V pontot, amire knnyen megllapthat W xk ? b) Hny sszehasonlts kell xk kivlasztshoz?

( )

( )

24. (folytats) Tedd fel mg, hogy minden x 2 V {re megsgott a kismadr egy{ egy Wspe x rtket is, ami a p{b l x{be vezet legol sbb olyan spe ilis t sszslyt jelenti, aminek sak az x vgpontja nin s a fenti xi {k kztt. Hny sszehasonlts kell xk {nak s az sszes j Wspe x rtknek a meghatrozshoz?

()

()

Dijkstra{algoritmus:

Adott: n pont, m l G(V; E ) irnytott grf w

:

E

7! R+

tovbb egy kijellt p pont. Keresend : minimlis sszsly t p{b l az sszes tbbi pontba.

slyozssal,

()

Az el z feladat Wspe x vltozit fogjuk hasznlni, tovbb egy >jPont vltozt, ami az aktulis xk {t tartalmazza. Az elintzett xi {ket a KszPontok halmaz tartalmazza. Ini ializls: minden Wspe x W x 1, kivve Wspe p W p . >jPont p, KszPontok fpg. Ciklus n {szer: (i) Minden >jPont; x 2 E , x 2 = KszPontok{ra Wspe x fWspe x W >jPont w >jPont; x g. (ii) >jPont:= az az x 2 = KszPontok, amire Wspe x minimlis. (iii) KszPontok KszPontok [ f>jPontg (iv) W >jPont Wspe >jPont

( ) := ( ) := := := 1 ( ) ( ) := min ( ); ( := ( ) := ( )

( ) := ( ) := 0

)+ (

()

)

Megjegyzs: A Wspe s W vltozk kzl egy is elg lenne, pl. W{ben vgl gyis W spe jelenik meg. Csak a knnyebb rthet sg kedvrt hasznltuk mindkett t.

Lpsszm: Az (i) rsz d (>jPont) lps. A teljes eljrs sorn ez sszesen legfeljebb m sszehasonlts. A (ii) rsz sszesen n n 24. feladat). A tbbi egytt O n lps. Eszerint a teljes lpsszm O m

( 1)+( 2)+. . .+1 = () ( + n2).

n sszehasonltst jelent (lsd

2

84

Elekes Gy:

25. Adj eljrst arra, hogyan keresnd meg slyozott l irnytott grfban adott pontbl az sszes tbbihez nem sak a minimlis odavezet t sszslyt, hanem magukat az utakat is. ! n 26. Ritka grfokon (ahol m << ) a minimumok kivlasztshoz szksges n2

2

adja a lpsszm nagyjt. Javtsd az algoritmust gy, hogy lpsben mkdjn!

O (n + m) log n

!

6.3. Minimlis kltsg feszt fk DEF. Ha a G(V; E ) (irnytott vagy irnytatlan) grf lein adott egy w : E

! R+

slyfggvny (vagy kltsgfggvny vagy egyszeren hosszsg), akkor slyozott l grfnak nevezzk. Nha megengedjk, hogy w negatv rtkeket is felvegyen; ezek az esetek ltalban bonyolultabbak.

Minimlis feszt fa problmja:

Adott: Slyozott l irnytatlan, sszefgg grf. Keresend : Olyan F feszt fa, melynek sszslya (teht

het legkisebb.

X

e2F

w(e)) a le-

A problma megoldshoz bevezetsknt nhny szrevtelre lesz szksgnk: 27. Ha F tetsz leges fa, e pedig egy olyan l, amely F kt pontjt kti ssze, akkor tallhat f 2 F l, melyre F n f [ e is fa lesz. (Azaz f ki serlhet e{re.) !

(

)

28. Ha F1 s F2 kt fa ugyanazon a s shalmazon, f1 tallhat f2 2 F2 l, melyre F1 n f1 [ f2 is fa lesz.

(

)

2 F1 tetsz leges l, akkor !

29. (folytats) Igaz-e, hogy az el z feladat jellseivel olyan f2 l is ltezik, melyre nem sak F1 n f1 [ f2 , de F2 n f2 [ f1 is fa lesz? !

(

)

(

)

Moh algoritmusok DEF. Moh algoritmus" nven azokat az eljrsokat szoks emlegetni, amelyek

gy rakjk ssze a keresett struktrt, hogy mindig a pillanatnyilag legkedvez bb rszeket vlasztjk ki, s ks bb ezeket nem mdostjk. A fenti problmra egy ilyen megolds lehetne pldul a kvetkez :

Moh algoritmus minimlis feszt fa keressre (Kruskal):

( )

( ) ...

Rendezzk sorba sly szerint nvekv leg a grf leit: w e1 w e2 w em s menjnk vgig rajtuk. Felttlenl vegyk be a fba e1 {et s e2 {t; a tbbib l pedig pontosan azokat, amelyek az addig bevlasztottakkal egytt nem tartalmaznak krt.

( )

85


30. Mutasd meg, hogy ez az eljrs mindig feszt ft ad! (Hogy mennyire kis sszslyt, arra mg visszatrnk.) ! Megjegyzs: A mohsg ritkn vezet jra! Nhny plda: 31. Mutass pldt ngy pont, slyozott l grfra, amelyben a legol sbb ngy l kr keressekor a moh eljrs (teht mindig a lehet legkisebb sly l vlasztsa) a minimlisnl sokkal (pl. szzszor) rosszabbat ad! 32. Most slyozott pont grfban keressk a lehet legnagyobb sszsly ponthalmazt, melyek kztt nem vezet egyetlen l sem. Mutass olyan pldt, ahol a moh mdszerrel (mindig a lehet legnagyobb sly pont vlasztsval) a maximumnak sak tredkt (pl. szzadrszt) kaphatjuk! 33. Ismt slyozott l grfban keressk a lehet legnagyobb sszsly lhalmazt, melyeknek nin s kzs vgpontjuk. Mutass olyan pldt, ahol a moh mdszer a maximumnak kb. felt adja! 34. (folytats) Bizonytsd be, hogy az utols feladatban ennl rosszabb eset nem lehetsges; a maximum legalbb felt mohn is mindig megkapjuk! ! Megjegyzs: A fenti pldk alapjn lesz igazn meglep a kvetkez kt feladat lltsa: 35. Legyen a Kruskal{algoritmussal vlasztott fa K , egy minimlis sszsly pedig M ! Jelljk K leit a vlaszts sorrendjben k1 ; k2 ; ; kn 1 {gyel; M leit pedig (ugyan sak sly szerint nvekv leg) m1 ; m2 ; ; mn 1 {gyel. Tegyk fel, hogy ki mi , ha i < r, de kr 6 mr (azaz a kt fa els r le azonos, de az r{edik mr nem.) Mutasd meg, hogy ltezik msik, M 0 minimlis feszt fa, amelynek els r darab le mind kzs K {val! ! 36. (folytats) Bizonytsd be, hogy a Kruskal{fle moh fa mindig minimlis feszt

fa! !

=

...

=

...

1

A Kruskal{algoritmus nhny vltozata. 37. Kruskal vatos" algoritmusa: Rendezzk skken leg az lslyokat: w e1 w e2 w em . Vgigmenve rajtuk vlasszunk ki bizonyos eik leket a kvetkez szably szerint: ha j < k{ra eij mr megvan, akkor eik legyen az els olyan er , melyre ei1 ; ei2 , , eik 1 ; er+1; er+2, mr nem lenne sszefgg . (Ms szval az a loz a, hogy

sak akkor vesznk be egy let, ha mindenkppen szksges.) Bizonytsd be, hogy gy is minimlis feszt fhoz jutunk! ! 38. Mutass pldt arra, amikor a 31. feladatra az vatos" algoritmus a minimumnak kb. ktszerest adja! Megjegyzs: Nagyobb mret grfon brmennyire (akr szzszor) rosszabbat is kaphatunk. 39. Legyen adva a skban n pont azzal a megktssel, hogy a kzttk fellp n2 tvolsg mind klnbz . Hzzunk egyenes szakaszt minden pontbl a hozz legkzelebb es hz! (Egy szakaszt ktszer is behzhatunk.) Mutasd meg, hogy gy nem keletkezhet zrt sokszgvonal! !

( )

...

( ) ...

( )

...

86

Elekes Gy:

...

40. Vlasszuk ki egy slyozott l irnytatlan grf (ponthalmaza fv1 ; v2 ; ; vn g) minden egyes pontjhoz a bel le indul lek kzl a minimlis slyt; ha tbb ilyen van, akkor ezek kzl azt, amelynek msik vgpontja a lehet legkisebb index. Bizonytsd be, hogy a kivlasztott lek erd t alkotnak (azaz nem lehet kztk kr)! ! 41. (folytats) (Boruvka moh algoritmusa:) Tegyk fel, hogy a fenti lek kivlasztsa utn a keletkez erd komponenseit egy{egy pontt vonjuk ssze (megszntetve az egy komponensen belli leket, s meghagyva az j pontprok kztt a kt rgi komponens kztt men lek kzl a legol sbbat). A keletkez

grfra kezdjk ellr l az eljrst. Bizonytsd be, hogy a) legfeljebb 2 n ismtls utn egyetlen pontbl ll grfhoz jutunk; b) az eljrs sorn kivlasztott lek ft alkotnak az eredeti grfban;

) ez a fa minimlis feszt fa! Megjegyzs: Egyre tbb olyan szmtgpet ptenek, amelyekben tbb (gyakran sok ezer) pro esszor egyszerre vgzi a szmtsokat. (Magyarorszgon sajnos mg sak mutatban van egy{kett .) A fenti algoritmus ilyen gpekre kivlan alkalmas.

log

87


7. fejezet

Halmazrendszerek. 1. Egy ulti-versenyen tzen indultak. Mindig h arom j atekos u l egy asztaln al es egy partit jatszanak; azt an u j h armas kovetkezik. Az els}o sz unetben valaki megkerdezte t} ol uk, ki h any jatszmat j atszott. A valaszok: 4 4 3 3 2 3 4 3 2 4. Kilen en jol emlekeztek, egy rosszul | de } o is sak egyet tevedett. T obbet vagy kevesebbet mondott?

Szoks szerint jX j az X halmaz elemszmt jelli a tovabbiakban. Legyen H1 ; H2 ; ; Hm az f ; ; ; ng alaphalmaz rszhalmazainak tetsz leges rendszere. DEF. Az i elem foka (jellse di ): ahny Hj {ben i benne van. 2. Mutasd meg hogy, X X di jHj j in j m

...

1 2 ...

=

3. (folytats) Bizonytsd be az el z lltst abbl is, hogy egy XX

i

j

ai;j =

XX

j

i

(ai;j ) mtrixra

ai;j ;

azaz a sorsszegek sszege s az oszlopsszegek sszege azonos. 4. Tegyk fel, hogy minden jHj \ Hk j , ha j 6 k . Bizonytsd be, hogy

1

a)

X

b)

X

=

=

m2 ; 2

...

di

j Hi j n : 2 2

=

5. Legyen jH j n es A1 ; A2 ; ; An H (nem sajt ohiba: m n) supa k ul onb oz}o reszhalmazok. Bizonytando: letezik x 2 H , hogy A1 fxg; A2 fxg, , An fxg is supa kulonboz}oek. 6. Legyenek fA1 ; A2 ; ; A n g egy n elem halmaz sszes k elem rszei; k <

n=2.

... ( ) k

Mutasd meg, hogy kivlaszthat hogy minden i n k {ra Ai Bi .

1

n k

darab klnbz

...

k+1

elem

Bi ,

88

Elekes Gy:

7.1. Helly tpusu tetelek A most ismertetend} o tetelkor egy Hellyt}ol sz armazo eredmenyr} ol kapta nevet:

Helly tetele a skban. Ha a sk K1 ; K2 ; . . . ; Kn konvex halmazai kozul b armely h aromnak van kozos pontja, akkor az osszesnek is van.

7. Mutasd meg, hogy az allt as igaz

n = 4{re!

8. (folytats) Bizonytsd be Helly tetelet!

Helly tetele egyeb dimenziokban is kimondhat o. K ozismert az egydimenzi os valtozat: 9. Ha a szamegyenes veges sok (pl. legyenek z artak, de m as tpusokra is igaz) intervalluma koz ul b armely kett} o egymasba metsz, akkor van olyan pont, ami minden intervallumban benne van. ! d ban. Ha R K1 ; K2 ; ; Kn konvex halmazai kozul Helly tetele d dimenzio b armely d {nek van kozos pontja, akkor az osszesnek is van.

...

+1

10. Mutass az egyenesen (skban, terben, Rd {ben) a) korlatos, de nem z art; b) z art, de nem korlatos konvex halmazokbol vegtelen sokat, amelyek kozott b armely kett} o (harom, negy, ;d ) egymasba metsz, megsin s az osszesnek kozos pontja. (Vagyis tovabbi feltetelek nelk ul vegtelenre nem altalanosthat o a Helly{tetel!) ! d ban. Ha R akarhany zart korlatos Vegtelen Helly{t etel d dimenzio

... + 1

konvex halmaza koz ul b armely d is van.

+ 1{nek van kozos pontja, akkor az osszesnek

(A bizonyt as egy analitikus segedtetelb} ol kovetkezik: Ha Rd ak arh any korlatos z art halmaza koz ul b armely veges soknak van kozos pontja, akkor az osszesnek is van. (Ez a Borel{fele fedesi lemm aval ekvivalens.) Megjegyzs: Erdekes (es gyakran hasznos), hogy eleg egyetlen halmazrol megkovetelni a korlatoss agot: } s vegtelen Helly{t ban. Ha Rd akarhany zart konEro etel d dimenzio vex halmaza koz ul b armely d + 1{nek van kozos pontja a korlatos z art konvex H {ban, akkor az osszesnek is van.

11. Bizonytsd be az er}os vegtelen valtozatot a veges tetelb} ol es az emltett analitikus segedtetelb} ol!

89


12. Ha a sk veges sok pontja koz ul b armely h arom lefedhet}o egy r sugar u korlemezzel, akkor az osszes is. 13. Tegy uk fel, hogy egy skbeli ponthalmazban nem fordul el} o D{nel nagyobb t avolsag. Fedhet}o-e biztosan a) r D= sugar u korrel; b) r D sugar u korrel? ! 14. Ha egy H h aromsz o g leghosszabb oldala a , akkor H befoglalhat o alkalmas p kozeppont u r a= sugar u korbe!

= 2 =

=

3

Jung t etele. Ha egy skbeli (veges vagy vegtelen)pponthalmazban nin s D{

nel nagyobb t avolsag, akkor a halmaz lefedhet}o

D=

3 sugaru korrel.

15. Bizonytsd be Jung tetelet veges halmazokra! ! 16. (folytats) Bizonytsd be Jung tetelet tetsz} oleges vegtelen halmazokra is! ! 17. Ha a sk veges sok pontja koz ul b armely h arom lefedhet}o egy adott K konvex halmaz valamelyik eltoltj aval, akkor az osszes is. 18. Bizonytsd be, hogy a sk (ter, ; Rd) barmely korlatos konvex halmazanak van olyan pontja, mely a rajta atmen} o h urokat legfeljebb 2:1 (3:1, ; d:1) ar anyban osztja! DEF. A sk (ter, Rd ) egy korlatos ponthalmazanak entruma olyan pont, amelyen atmen} o b armely egyenes (sk, hipersk) altal levagott darabok (a z art felskokba, felterekbe es}o reszek) merete az eredetinek legalabb {a ( {e, ,

...

...

1 3

1 d + 1 {ed resze).

1 4

...

Megjegyzs: Csak korlatos halmazokkal foglalkozunk. Ezen bel ul ket alap{eset erdekes: (i) ha a halmazok veges sok pontbol allnak; ekkor a reszek merete a darabsz amuk; (ii) ha ter ulet uk pozitv; akkor ez a mer} osz am.

Tetel. Minden korlatos ponthalmaznak van entruma. 19. Egy nylt vagy z art felskra (felterre) mondjuk azt, hogy rossz, ha benne a halmaznak kevesebb, mint 1/3 (1/4, ; = d {ed) resze van. Mutasd meg, hogy egy pont akkor es sak akkor nem entrum, ha valamely rossz nylt felskban (felterben) van! ! 20. (folytats) Bizonytsd be a fenti tetelt!

. . . 1 ( +1)

Lehet-e jobbat mondani konvex halmazokra? A szabalyos h aromsz og s ulypontj an atmen} o egyenesek peld aja azt mutatja, hogy nem varhat o jobb, mint az egesz alakzat 4/9{ed resze. Ez viszont mindig el is erhet} o:

Tetel. Tetsz}oleges skbeli korlatos konvex halmaz teruletet a sulypontjan

21.

atmen} o b armely egyenes 4:5 vagy egyenletesebb ar anyban osztja.

Ha a sk bizonyos egysegkorei koz ul b armely kett} onek van kozos pontja, akkor lefoghat ok h arom ponttal.

90

Elekes Gy:

22. A sk bizonyos konvex halmazaibol b armely kett} onek van kozos pontja. Igaz-e, hogy lefoghat ok h arom ponttal? 23. Ha egy intervallumrendszer b armely osszes is.

s + 1 tagja lefoghato s ponttal, akkor az

...

24. Egy fa T1 ; T2 ; ; Tn reszf ai koz ul b armely kett} onek van kozos s u sa. Bizonytand o: az osszesnek is van. Igaz-e hasonlo allt as s u sok helyett elekre? 25. Ha egy reszben rendezett halmaz b armely ket maximalis meret} u antilan anak van kozos eleme, akkor az osszesnek is van. 26. Ha egy legfeljebb h aromelem} u halmazokbol all o halmazrendszerben b armely legfeljebb negynek van kozos eleme, akkor az osszesnek is van. Mutass peld at, hogy negy helyett nem eleg h armat megkovetelni! 27. (folytats) Ha egy legfeljebb r elem} u halmazokbol all o rendszerben b armely legfeljebb r {nek van kozos eleme, akkor az osszesnek is van. Mutass peld at, hogy r helyett nem eleg r{et megkovetelni!

+1

+1

28. Ha egy fa nehany reszf aja koz ul b armely osszes is. 29.

d

s+1

lefoghat o

s

ponttal, akkor az

2 dimenzios konvex halmazokra nem igaz hasonlo: mar R2 {ben is meg-

adhato (barmely p aratlan s{re) s darab konvex halmaz, melyek koz ul b armely s lefoghat o ket ponttal, de az osszes nem.

1

7.2. Ramsey tetelei halmazrendszerekre. Ebben a szakaszban halmazrendszerek sznezeseivel foglalkozunk. Mindig egy (veges vagy vegtelen) alaphamaz r elem} u reszeit sznezz uk, valamilyen r terme szetes sz amra. VIGYAZAT!! Ez pl. r eseten azt jelenti, hogy sem a pontok (elemek), sem a p arok (elek), sem a 3{nal t obb elem} u reszek nem kapnak sznt | sak a h armasok. Ugy is kepzelhetj uk, hogy kis edulakra rjuk a 3 elem} u reszhalmazokat, egy-egy edulara egyet-egyet, es a edulak lehetnek pirosak, kekek, esetleg mas szn} uek is. M askepp, ha az alaphalmaz elemei a h arom dimenzios ter pontjai, akkor az osszes pontharmasra egy-egy sz nes pap rbol kiv agott h aromsz oget er}ost unk (n pont eseten n3 {at). Persze r > eseten ez utobbi szemleltetes nem m} ukodik.

=3

3

30. Tegy uk fel, hogy egy H0 vegtelen alaphamaz osszes 3 elem} u reszhalmazait kisznezt uk pirosra vagy kekre. Vegy unk ki egy x0 2 H0 elemet. Biztosan letezik-e H1 H0 fx0 g vegtelen reszhalmaz, melynek b armely ket y; z elemere az fx0 ; y; z g h armas ugyanolyan szn} u? armasok azoanos (Vegtelen sok y; z p ar persze lesz, melyekre az fx0 ; y; z g h szn} uek; de nem ez a kerdes.) !

91


31.

(folytats) Lesz-e olyan vegtelen reszhalmaz is, melynek minden 3{asa azonos szn} u? !

Vegtelen Ramsey t etel halmazrendszerekre. Egy H0 vegtelen alap-

hamaz osszes r elem} u reszhalmazat kisznezte valaki pirosra vagy kekre. Bizonytsd be, hogy keletkezett olyan vegtelen reszhalmaz, melynek minden r{ese azonos szn} u.

!

32. Igazold a fenti tetelt!

Ramsey ttele vges grfokra. Tetsz leges k , l s r termszetes szmokhoz van olyan Rr k; l , hogy egy n Rr k; l elem} u alaphalmaz r{eseit pirossal s kkkel sznezve biztosan talalhat o lesz vagy olyan k elem} u reszhalmaz, melynek minden r{ese piros, vagy olyan l elem} u reszhalmaz, melynek minden r{ese kek.

( )

( )

!

33. Igazold ezt a tetelt is! Megjegyzs: A tetel t obb (akarh any) sznre is altalanosthat o.

Egy alkalmazas: nagy konvex sokszogek Az alapkerdes: Igaz-e, hogy eleg sok ( altalanos helyzet} u) pont koz ul kiv alaszthato nagy konvex sokszog? Pre zebben: Letezik-e minden m{hez olyan K , hogy ha n K pont koz ul semelyik h arom sin s egy egyenesen, akkor kiv alaszthat o m darab, amelyek egy konvex m{sz og s u sait alkotjak? } s es Szekeres vetette fel; az itt kovetkez}o eredmenyek is A problem at Erdo t} ol uk szarmaznak. Kiindul o eszrevetel uk a kovetkez}o volt: 34. A sk ot altalanos helyzet} u pontja kozott mindig van negy, amelyek konvex negyszoget hataroznak meg.

35.

A kerdes e feladatban szerepl} o, igen spe ialis esetenek segtsegevel (es felhasznalva Ramsey tetelet) megoldott ak az altalanos problem at is: Bizonytsd be, hogy a sejtes minden

m{re igaz!

K ovetkez}o kerdes uk a legkisebb alkalmas K meghatarozasa lett volna. A tovabbiakban ezt K m {mel jel olj uk. Sajnos ennek erteket nem siker ult pontosan meghatarozniuk; megoldottak viszont egy rokon feladatot, amib} ol j o be sles adodott K m {re is.

( )

( )

92

Elekes Gy:

Konvex vek. Ha az ember megprobal adott pontokbol nagy konvex reszt osszerakni, es ket kis ponthalmazt mar talalt, ezek nem feltetlen ul illeszthet} ok ossze egy nagy konvex darabba. Ehhez az is sz ukseges, hogy egym as fele" legyenek nyitottak; pl. az egyik lefele, a masik felfele. (Persze onmag aban meg ez sem elegseges!)

DEF. A Q1 ; Q2 ; . . . ; Qk pontsorozat konvex (konkav) v, ha az x koordinatak

36.

o ( s okken). M asn ovekv} oek es a Qi Qi+1 szakaszok meredeksege monoton n} szoval akkor, ha van olyan konvex (konk av) f uggvenyg orbe, amelyre a Qi pontok illeszkednek.

Mutasd meg, hogy ha n R3 k; l altalanos helyzet} u pont kozott nin s kett} o egymas alatt, akkor tartalmaznak vagy k pont u konvex, vagy l pont u konk av vet! !

( )

37. (folytats) Milyen be sles adodik

38.

K (m){re az el}oz}o feladatbol?

!

Lehetseges, hogy kevesebb pont nem is eleg? Megprobaltak nagy ponthalmazt talalni, amiben nin s se k pont u konvex v, se l pont u konk av. Mutass

k+l k

2

4 ilyen pontot!

Ennel t obbet nekik sem siker ult talalniuk. Bebizonytott ak h at, hogy nem is lehet:

l } s{Szekeres) Ha a sk k + Tetel. (Erdo k

4+1 altalanos helyzet}u pontja 2 kozott nin s kett} o egymas alatt, akkor tartalmaznak vagy k pont u konvex, vagy l pontu konkav vet!

39. Milyen be sles adodik K

(m){re a tetelb}ol?

!

A fenti tetel bizonyt asahoz egy Ramsey{tpus u segedtetelt hasznaltak.

DEF. Rendeljunk a P1 ; P2 ; . . . ; Pn pontokon adott teljes graf eleihez tetsz}olegesen

w(Pi Pj )

...

s ulyokat! Az i0 < i1 < < ir indexek altal meghatarozott pontsorozat szomszedos tagjait osszek ot}o ej Pij 1 Pij elek monoton nov}o ( sokken}o) ellan ot alkotnak, ha w e1 w e2 w er (illetve ha w e1 w e2 w er ).

( )

( ) ...

( )

} s{Szekeres Lemma. Ha n Erdo

el} u teljes gr afban vagy van

sokken}o lan .

) =( ( ) ( ) ...

( )

k k+ l 2 4 + 1, akkor a fenti sulyozott

k pontu monoton nov}o, vagy van l pontu monoton

93


!

40. Mutasd meg, hogyan kovetkezik a lemm abol a tetel!

A lemma bizonytasa:

() ()

()

I. Rendelj unk hozz a minden e elhez egy ha e ; b e i sz ampart u gy, hogy a e ill. b e jel oli a leghosszabb olyan n ov} o ill. sokken}o ell an hossz at, melynek els}o tagja e. II. Azt mondjuk, hogy az e1 Pi Pj1 jobb az azonos kezd}opontu e2 Pi Pj2 elnel, ha a e1 a e2 , b e1 b e2 es legalabb az egyik egyenl}otlenseg szigor u. III. Az e el a Pi kezd}opontbol nezve maximalis, ha nin s vele azonos kezd} opont u, n ala jobb el. IV. Veg ul minden i n {re rendelj uk hozz a a Pi ponthoz a kovetkez}o halmazt:

()

)

(

=( ) ( ) ( )

( )

=

( )

0

Hi = fha(e); b(e)i Vizsgaljuk meg a fenti

j

e kezd}oponja Pi es onnan nezve maximalisg:

Hi {k tulajdonsagait:

41. Bizonytsd be, hogy (i) i 6 j {re Hi 6 Hj ; (ii) Hi -t egyertelm} uen meghatarozz ak a szamparokban szerepl} o a-k ill. b-k halmazai.

=

=

42. (folytats) Bizonytsd be a fenti feladat segtsegevel az Erd} os{Szekeres lemm at!

Ujra a konvex sokszogek.

43.

2

Mutass k altalanos helyzet} u pontot, amelyek kozott nin s konvex k

!

Az el} oz}o es a 39. feladat szerint tehat 2m 2 + 1 K (m) 2mm 24 + 1 = O(4m=pm):

Sejtes: a bal oldali egyenl}otlenseg az eles.

+ 2{szog!

94

Elekes Gy:

7.3. Vges geometrik

(Sz}onyi Tam as nyom an)

44. Adj meg egy 7 elem alaphalmazon 7 darab olyan 3 elem rszhalmazt, hogy brmely kett nek pontosan egy kzs eleme legyen! DEF. Vges geometria egy alaphalmaz olyan rszhalmazainak rendszere, melyek kzt (i) brmely kett nek pontosan egy kzs eleme van; (ii) az alaphalmaz brmely kt eleme egytt benne van valamely kijellt rszhalmazban. Megjegyzs: Ha az alaphalmazt sknak, a kijellt rszhalmazokat egyenesek"{ nek kpzeljk, akkor (i) s (ii) ppen a pontok s az egymssal nem prhuzamos egyenesek illeszkedsnek aximi. Innen az elnevezs. 45. Mutasd meg, hogy az el z feladat feltteleinek eleget tev halmazrendszer szksgkppen vges geometria! ! 46. (folytats) Van-e ms, nem supa hromelem halmazbl ll vges geometria 7 elemen? ! DEF. Egy vges geometria szablyos, ha van benne ngy ltalnos helyzet pont, azaz ngy olyan, melyek kzl semelyik hrom nin s egy egyenesen. Ellenkez

esetben elfajul. Pldul a 44.feladat megoldsban szerepl vges geometria szablyos; az el z ben mutatott elfajul. 47. Legyen E egy vges geometria egy egyenese, p tetsz leges pont, melyre p 2 = E. Mutasd meg, hogy p{t pontosan jE j darab egyenes tartalmazza! ! Megjegyzs: A kvetkez feladatban rszben trtneti okokbl szerepel elemszmknt q (s nem q ), de mr itt is | s a ks bbiekben mg inkbb | ez a jells sokkal knyelmesebb lesz. 48. Bizonytsd be, hogy brmely szablyos vges geometrihoz van olyan (egyetlen) q termszetes szm, hogy (i) brmely E egyenesre jE j q ; (ii) minden pont ppen q egyenesre illeszkedik; (iii) az alaphalmaz q 2 q elem; (iv) a vges geometria q 2 q egyenesb l ll. DEF. Ezt a q{t nevezzk a vges geometria rendjnek. 49. Tegyk fel, hogy ltezik q elem F vges test! Vegyk az F {beli elemek hrom hosszsg sorozatait! (Ezek F felett hrom dimenzis vektorteret alkotnak.) Hagyjuk ki kzlk a ; ; vektort s a maradkon de niljuk a kvetkez

ekvivalen ia{rel it:

+1

= +1 +1 + +1 + +1 (0 0 0)

(x; y; z) (kx; ky; kz)

ha

k 2 F n f0g

95

Kombinatorika feladatok a) Mutasd meg, hogy ez valban ekvivalen ia{rel i! b) Mekkork az ekvivalen ia{osztlyok s hny van bel lk?

) q {re s 3{ra mik ezek az ekvivalen ia{osztlyok?

50.

=2

Tetsz leges (a; b; ) 2 F 3 n f(0; 0; 0)g{hoz rendeljk az

ax + by + z = 0 egyenletnek eleget tev ekvivalen ia{osztlyok halmazt! a) Hny elemek ezek a halmazok? b) hny klnbz ilyen halmaz van?

) q {re mik ezek a halmazok?

=2

!

51. (folytats) Mutasd meg, hogy az el z egyenlettel de nilt halmazok a fenti ekvivalen ia{osztlyokon szablyos vges geometrit alkotnak! Megjegyzs: q p elem vges test mindig ltezik.

=

Kvetkezmny: Ha q prmhatvny, akkor kszthet q {adrend vges geo-

metria.

Megjegyzs: Megoldatlan, hogy mely n{ekre ltezik n{edrend vges geometria. Az egyetlen ltalnos eredmny ebben az irnyban az albbi: (Bru k{Ryser ttel): Ha n vagy 2 (mod 4), akkor n{edrend vges geometria sak akkor ltezhet, ha n el ll kt ngyzetszm sszegeknt. Ebb l pldul kvetkezik, hogy hatodrend sk nin s. Tizedrend sk ltezst e ttel mg nem zrja ki; sokig megoldatlan volt, hogy ltezik-e egyltaln. 1990 kor ul bizonytottk be kanadai matematikusok (szmtgp segtsgvel), hogy ilyen sk sin s. Ez nem kis feladat! Egy 111 elem halmaz 11 elem rszeir l van sz; ilyen tbb, mint 20 darab van. Ezekb l kellene 11{et kivlasztani. Ezek vgignzshez nem elg a gp; tlet is kell.

1

10

Latin negyzetek DEF. Latin negyzetnek nevezunk egy n n{es tablazatot, melynek minden eleme

1 2 ...

52.

az ; ; ; n szamok egyike, ha minden sorban es minden oszlopban minden szam pontosan egyszer fordul el} o. Ket n n{es latin negyzet ortogon alis, ha egymasra helyezve" }oket, mind az n2 lehetseges szampar megjelenik (es gy mindegyik pontosan egyszer).

2

Mutasd meg, hogy n {re akkor es sak akkor letezik n{edrend} u vges geometria, ha letezik n darab p aronkent ortogonalis n n{es latin negyzet!

1

53. Tegy uk fel, hogy valamilyen k {ra es n{re letezik k darab, p aronkent ortogonalis n n{es latin negyzet. Igaz-e, hogy olyanok is leteznek, amelyek mindegyikeben a bal fels}o elem azonos? 54. Mutasd meg, hogy semmilyen n gon alis n n{es latin negyzet!

2{re sem letezhet n darab paronkent orto-

96

Elekes Gy:

Vegyes feladatok 55. Tegyk fel, hogy valaki kt osztlyba osztotta egy n{edrend vges geometria pontjait, pl. piros s kk sznnel sznezte ket. Jellje pE ill. kE a piros ill. kk pontok szmt egy E egyenesen, s nevezzk az egyenest egyenletesnek, ha pE kE . a) Bizonytsd be, hogy legfeljebb n2 egyenes lehet egyenletes! b) Keress minden pratlan n{re olyan pldt, ahol valban van is ennyi!

) Mutasd meg, hogy az ilyen plda lnyegben egyrtelm (a pontok permut ijtl eltekintve). 56. Az el z feladat jellseivel igazold, hogy

=

X

E

(pE

kE )2

sak a piros s kk pontok szmtl fgg. DEF. Egy szablyos n2 n -szg s sainak valamely rszhalmazt teljesen szablytalannak nevezzk, ha a pontok kztti sszes tvolsg klnbz . 57. Ha az emltett sokszgnek ltezik n pont teljesen szablytalan rszhalmaza, akkor ennek elforgatottjai mint egyenesek vges geometrit alkotnak. 58. (folytats) Mutasd meg, hogy a szablyos 43{szgnek nin s 7 pont teljesen szablytalan rsze! 59. Keress negyedrend vges geometrit! DEF. Egy ponthalmazt akkor neveznk ltalnos helyzetnek, ha semelyik hrom pontja sem illeszkedik egy egyenesre. 60. Legfeljebb hny ltalnos helyzet pontot lehet kivlasztani? ! 61. (folytats) Bizonytsd be, hogy ha n pratlan, akkor legfeljebb n {et lehet!

+ +1

+1

+1

!

DEF. Egy vges geometria pontjainak S rszhalmaza lefog pontrendszer, ha min-

den egyenes tartalmaz S {beli pontot. 62. a) Mutasd meg, hogy n pont nem foghatja le az sszes egyenest; b) n is sak akkor, ha mind egy egyenesen van;

) ltalnos helyzet ponthalmaz sose lehet j. DEF. Egy vges geometria dulist gy kapjuk, hogy az egyeneseknek pontokat, a pontoknak egyeneseket feleltetnk meg. Pontosabban: j pontok": a rgi egyenesek. j egyenesek": az j pontok" olyan rszhalmazai, amelyeknek megfelel

rgi egyenesek egy (rgi) ponton mennek t. Megjegyzs: Van olyan vges geometria, amely nem izomorf a dulisval. A legkisebb ilyen plda 91 pont.

+1

97


63. De nild a lefog egyenesrendszer fogalmt s mondj r az el z feladat a)-b)- ) rszeihez hasonl lltsokat!

p

2

64. Brmely n elem vagy kisebb ltalnos helyzet ponthalmaz kib vthet

nagyobb ltalnos helyzetv.

+1

...

65. Ha n pros, akkor brmely n darab ltalnos helyzet P1 ; P2 ; ; Pn+1 ponthoz van egyetlen Pn+2 , hogy a kib vitett ponthalmaz is ltalnos helyzet.

!

66. A mod p feletti vges geometriban adj meg (p prm.)

p + 1 ltalnos helyzet pontot!

!

67. Legyen r rgztett termszetes szm! Legfeljebb hny pontot vlaszthatunk ki egy n{edrend vges geometribl, ha minden egyenesr l sak r{et vagy kevesebbet vehetnk? !

+

68. (folytats) Mutasd meg, hogy rn n r ilyen pont sak akkor ltezhet, ha rjn. Megjegyzs: 1. A fenti mret alkalmas ponthalmaz ltezsre ltalnos elgsges felttel m esetn az rjn felttel elgsges nem ismert. Annyit lehet tudni, hogy n m is; n ,r {ra azonban kevs. 2. Az el z feladat a 61. problma ltalnostsa; ott r .

=3

=2

=3

=2

69. Kszts j aximarendszert" a vges geometrikra, amely sak a halmazok (vagyis az alaphalmaz, az egyenesek s ezek metszetei) mretre vonatkoz felttelekb l ll! (lsd 48. feladat.) ! 70.

n2 + n + 1 elemen (most n + 1{es rszt, hogy

nin s vges geometria !) keressnk lehet leg kevs

(i) brmely kett nek legyen kzs eleme, s (ii) a halmazrendszer az (i) tulajdonsgra nzve maximlis (azaz nem b vthet ) legyen! Mutasd meg, hogy a) legalbb n kell; b) ennyi elg is, ha n pratlan.

+2

2

71. Ha n > , akkor van olyan lefog ponthalmaz, ami nem tartalmaz egyenest. !

Problma: (Erd s P.) Ltezik-e olyan (n{t l fggetlen) konstans, hogy brmely vges geometriban tallhat lefog ponthalmaz, amely minden egyenesr l legfeljebb darab pontot tartalmaz? Megjegyzs: A konstans helyett n{nel az llts igaz.

log

p +1

, akkor 72. Ha a H lefog ponthalmaz nem tartalmaz egyenest s jH j > n n egy alkalmasan vlasztott pontjnak elhagysa utn is lefog marad.

Megjegyzs: (Pelikn{Bruen ttel) a H lefog ponthalmaz nem tartalpn ,Ha maz egyenest, akkor j H j n s egyenl sg sak akkor llhat fenn, p ha ltezik n elem vges geometria.

+

+1

Sejts: mod p feletti vges geometriban jH j 32 p.

98

Elekes Gy:

7.4. Klasszikus extremlis halmazrendszerek Sperner ttele

1; 2; . . . ; ng halmaznak, ha semelyik

73. Hny rszhalmazt tudod kivlasztani az f kett sem tartalmazhatja egymst?

DEF. Sperner{rendszer{nek nevezzk az fA1 ; A2 ; . . . ; Am g halmazrendszert, ha

i 6= j esetn Ai 6 Aj . DEF. Az A1 A2 . . . An

f1; 2; . . . ; ng b vl halmaz{sorozatot ln nak

nevezzk. A ln elemei az

Ai

halmazok.

74. Sperner{rendszer egy ln nak sak egy elemt tartalmazhatja.

DEF. Teljes ln n elem halmazon: ; = A0 minden

i n{re jAi j = i.

75. Hny klnbz teljes ln van az 76. 77. 78.

A1 . . . An = f1; 2; . . . ; ng, ha

f1; 2; . . . ; ng halmazon?

! !

X f1; 2; . . . ; ng hny teljes ln ban van benne? Mely X {eket tartalmazza a legkevesebb teljes ln ? n (nem felBontsd fel az f1; 2; . . . ; ng sszes rszhalmazainak rendszert bn= 2 ttlenl teljes) ln ra!

Sperner ttele: Ha A1 ; A2 ; . . . ; Am Sperner{rendszer az

halmazon, akkor

m

f1; 2; . . . ; ng alap-

n bn :

2

Egyenl sg sak akkor llhat fenn, ha minden (Pros n{re sak n2 lehet.)

Ai

vagy

b n2 , vagy d n2 e elem.

79. Bizonytsd be a Sperner{ttelben szerepl egyenl tlensget a) a 77. feladatbl; b) a 78. feladatbl! n 80. Legyen n pratlan, < k < bn=2 s vegynk k darab tetsz leges bn= elem, tovbb bn=n2 k darab tetsz leges dn= e elem rszhalmazt. Mutasd meg, hogy lesz ezek kztt kt, egymst tartalmaz!

0

2

2

81. Bizonytsd be, hogy Sperner ttelben sak az ott felsorolt halmazrendszerekre teljesl egyenl sg!

99


... )

1 2 ...

82. Legyen H1 ; H2 ; ; Hm az f ; ; ; ng alaphalmaz bizonyos rszhalmazainak olyan rendszere, hogy Hi 6 Hj ha i 6 j . Jelljk mk {val a k elem Hi {k szmt! k n: Bizonytsd be, hogy

(

=

n X

mk n k=0 k

1:

83. a1 ; a2 ; . . . ; an legyenek adott pozitv szmok, melyekre ai 1 minden i{re. A

2

bel lk kpezhet (akrhny ai {t tartalmaz) n darab sszeg kzl legfeljebb hny eshet egy egysgnyi hosszsg nylt intervallumba?

Erd s{Ko{Rado ttel 84. Legyen k s n adott termszetes szm. Hny k elem rszhalmazt tudod kivlasztani az f ; ; ; ng halmaznak, ha brmely kett nek metszenie kell egymst?

1 2 ...

85. Egy szablyos n{szg s sainak hny klnbz k elem rszt lehet kivlasztani gy, hogy (i) mindegyik egymst kvet s sokbl lljon, azaz valamely i{re fi; i ; ; i k g (mod n) alak legyen; (ii) brmely kett nek legyen kzs pontja.

1 ... +

+

1

2

Erd s{Ko{Rado ttele: Ha k n= s az A1 ; A2 ; halmazokbl brmely kett metszi egymst, akkor

m

. . . ; Am f1; 2; . . . ; ng

1: 1

n k

86. Bizonytsd be az Erd s{Ko{Rado ttelt!

Meg ket Erd s ttel Mekkora lehet egy halmazrendszer, ha sak annyit tesznk fel rla, hogy teljesti a vges geometrik (i) felttelt?

Erd s{DeBruijn ttele: Legyenek H1 ; H2 ; . . . ; Hm egy n elem alaphalmaz

=1

=

olyan rszhalmazai, melyekre jHi \ Hj j , ha i 6 j . Ekkor m n; tovbb m n akkor s sak akkor, ha a halmazrendszer egy (esetleg elfajul) vges geometria.

=

Megjegyzs: E ttel ltalnostsa (br az extrm rendszerekr l nem mond semmit) a ks bb szerepl Bose{Fisher{Ryser ttel.

100

Elekes Gy:

DEF. Egy X1 ; X2 ; . . . ; Xk halmazrendszert

i < j k{ra az Xi \ Xj

lehetnek).

{rendszernek nevezunk, ha minden kozos reszek azonosak (esetleg mindnyajan u resek is

Erd s{DeBruijn ttel. Ha egy r elem}u halmazokbol allo halmazrendszer

!(

t obb, mint r k tag u {rendszer.

1)r (klnbz ) halmazbol all, akkor kivalaszthato bel}ole k

!

87. Igazold a fenti tetelt.

} s). Letezik-e olyan > 0 konstans, hogy k darab (klnProblema (Erdo bz ) 3 elem} u halmazb ol mindig kiv alaszthato k tag u

{rendszer?

7.5. Linris algebrai mdszerek Bose{Fisher{Ryser ttel

...

Ttel: Legyenek H1 ; H2 ; ; Hm egy n elem halmaz rszhalmazai. Tegyk fel, hogy van olyan k termszetes szm, hogy jHi \ Hj j k , ha i 6 j . Ekkor m n.

=

=

88. Legyen vi a ttelben szerepl Hi halmaz karakterisztikus 0{1 vektora azaz vi vi1 ; vi2 ; ; vin {re

=(

...

)

vij =

1 0

(i m),

, ha j 2 Hi ; , ha nem.

a) Mutasd meg, hogy a vi {k linerisan fggetlenek! b) Bizonytsd be ebb l a Bose{Fisher{Ryser ttelt!

!

89. Legyen adva a skban n egyenes, melyek nem mind mennek at egy ponton es nin s kozott uk ket p arhuzamos. Biz.be: legalabb n metszespontjuk van.

Pros{ s Pratlanfalva

(Babai L aszl o { Frankl Peter nyom an)

Prosfalvn drki rendszablyokat vezettek be a tlsgosan elszaporodott klubok s trsasgok szmnak korltozsra. Az egyeslsi trvny prosfalvi vltozata hrom paragrafusbl ll: 0.x Kt klubnak, egyesletnek, trsasgnak (a tovbbiakban: klub") nem lehet teljesen azonos a tagsga. 1.x Minden klubnak pros szm tagja legyen! 2.x Ugyan sak pros legyen brmely kt klub kzs rsze (teht azok szma, akik mindkett nek tagjai)!

101


A helysg 32 feln tt lakosa (16 hzaspr) szinte osztatlan ellenszenvvel fogadta a | szerintk | szemlyi jogaikat korltoz szablyokat s termszetes reak iknt sak azrt is lzas klub-alaptsba kezdtek. Mindenekel tt bejegyeztettk az res klub{ot nulla taggal (hiszen a 0 pros szm), majd szmolgatni kezdtek, hny klubot tudnnak mg alaptani. 90. Te hnyat tudsz? 91. (folytats) Ha a ltszm prossgt gy biztostjk, hogy a hzastrsak egytt lpnek (vagy nem lpnek) be az egyes klubokba, hny egyeslet lehetsges? ! Szinte megbntja mr a helyi adminisztr it a fenti sokezer klub bejegyzsvel kap solatos rengeteg teend . Kormnybiztos kinevezst krik, aki meg is rkezik. Miutn szakrt kkel konzultlt, kihirdeti, hogy az el z hrom paragrafust a kvetkez kppen mdostja: 1.x Minden klubnak pratlan szm tagja legyen! 2.x Brmely kt klub kzs rsze (mint eddig is) pros legyen! Tovabba: az j 1.x{ra val tekintettel a helysg neve PRATLANFALV"{ra vltozik. Megjegyzs: A 0.x feleslegess vlt (mirt?). A lakosok nem tiltakoznak, hanem jt nevetnek a markukba s ismt tmeges klub-alaptsba fognak. 92. Az nfelldoz polgrmester felajnlja, hogy kilp minden klubbl, ahol eddig tag volt s belp mindegyikbe, ahov eddig nem. Megengedi-e ezt az j szably?

93. Te hny klubot tudnl most alaptani?

!

94. (folytats) s hny, supa 31 tagt? 95. Lehet-e egy 31 tag s 31 httag egyesletet szervezni?

Eddig minden vltozatban maximum 32 klub jtt ssze. A kvetkez feladatok

lja, hogy segtsnk a lakossgnak eldnteni, lehetsges-e ennl tbb.

(1

)

96. Tegyk fel, hogy m klub van. Rendeljnk hozzjuk egy{egy vi im 32 hosszsg 0{1 vektort! (Az k {edik helyen az egyes jelentse azt, hogy a | nvsor szerint | k {adik lakos tagja a megfelel klubnak; a 0 azt, hogy nem.) Fogalmazzuk t az 1. s 2.x{okat a vi vj skalrszorzatokra! !

97. (folytats) Mutasd meg, hogy a vi {k linerisan fggetlenek! (Hivatkozhatsz arra, hogy ha egy egsz egytthats homogn lineris egyenletrendszernek van nem-trivilis megoldsa, akkor van supa ra ionlis szmokbl ll is { mirt?)

Kvetkezmny: n elem halmaznak legfeljebb n rszhalmaza vlaszthat ki, ha megkveteljk, hogy Pratlanfalva trvnyei teljesljenek rjuk. 98. Mutasd meg, hogy a) ha a mod 2 test (szoksos jellse GF(2)) feletti nhny vektor linerisan fggetlen, akkor ket R feletti vektoroknak tekintve is fggetlenek lesznek! b) Ez fordtva nem igaz { mutass pldt!

102

Elekes Gy:

99. Gondold vgig a fenti Kvetkezmny bizonytst GF(2) feletti vektorokkal is! 100. Egy varosban piros es kek jelvenyes klubok m} ukodnek: P1 ; P2 ; ; Pm es K1 , K2 , , Km (ugyanannyi). Ket szabaly van: 8jPi \ Ki j paratlan es jPi \ Kj j p aros, ha i 6 j . Bizonytando: m n. 101. Egy varos lak oinak szama n, p aratlan. A klubok sz ama m, mindegyiknek p aros szam u tagja van es b armely kett} onek p aratlan sz am u kozos. Biz. be: m n. 102. Egy varos lak oinak sz ama n, p aros. A klubok sz ama m, mindegyiknek p aros szam u tagja van es b armely kett} onek p aratlan sz am u kozos. Biz. be: m n . Lehet-e egyenl} oseg? 103. Legfeljebb h any klubot alapthatnak n lakos u MOD-3-FALVA lak oi? [B armely jAi j 6 (mod 3) es 8jAi \ Aj j (mod 3).℄ ! 104. Az n lakos u MOD-6-FALVAN legfeljebb n klub m} ukodhet. [B armely jAi j 6 (mod 6) es 8jAi \ Aj j (mod 6).℄

...

...

=

1

0

0

2

0

0

103


III. RSZ

tletek s eredmnyek

104

Elekes Gy:

tletek s eredmnyek az 1. Fejezethez 1.1. 3 3 2 4 1.2. a) 5 b) 4 1.3. n . 1.4. A fldszint hromfle lehet; a tovbbiak az el z fggvnyben ktflk. Eredmny: n . 1.5. b) El szr Kov s rnak vlasztunk valamit, majd a maradk kt tisztsgre egy{egy embert: . 57! . 1.6. 51! mn 1.8. 1.10. a{b) n (minden elemr l kln dnthetnk). 1.11. Minden oszlopba egyet tehetnk gy, hogy ne kerljn kett egy sorba: lehet sg. 1.12. 2 (az els hrom jegy ennyifle lehet; a tbbit ezek meghatrozzk). 1.13. k n (minden a 2 A{rl kln dnthetnk). Vigyzat! az ember hajlamos fel serlni k {t s n{et! 1.14. n . 1.15. k k k n . Ez n tnyez . 1.16. 13 . 1.17. k1 k2 kr . 1.18. . 1.19. Nem 100! . 5. (l. mg a 1.20. A {t is rdemes termszetes szmnak venni, br kiesik: 6 2. feladat megoldst.) 10 . 1.21. 10 1.22. . Lsd 5. feladat. 1.23. a) b) mindkett ) = 1.25. 8!20! 5!7! nk )! 1.28. (nn11+!nn22+...+ ! ...nk ! 1.32. 6 1.33. n n n n n n n 2 5 1.35. 1.41. Ragasszunk sznes matri kat az dessgekre, majd vegyk le ket! 1.44. (22nn)! 4 1.45. = 48! 1.46. (12!)4 (osszuk kln az szokat, kln a tbbit). 48!3 (adjuk valakinek az szokat, majd osszuk ki a tbbi lapot) 1.47. (13!) 9! 1.55. nd(n)=2 , ahol d n az osztk szma; lsd 17. feladat. n 1.56. 2 (minden lr l kln dnthetnk). 1.63. Maximlis rossz: .
25 10 9 10 9 10 9 = 9 10 ! 3 2 3 14 13 57 56 55 54 53 52 = 2 2

8!

9 10 !

( 1) . . . ( + 1) 3 ( + 1)( + 1) ( + 1) 8 6 4 2 157 56 = 101 0 6 5 15 14 13 14 13 12 9! 4! 9! 4! 9 ( 1) ( 1) ( 9 10 9 9 8 7 6 5 52! (13!) 4! 4

2) (

10

2) . . . 2 2 1 1 = ( !)

() 2( ) 14 + 14 + 12 + 14 + 10 + 10 = 74 (4 5 + 5 2 + 6 3) 2 = 48 2 = 24

10

105


a j o oldalszakaszok szam at, akkor p aratlan szamot kapunk. Ebb}ol m ar adodik, hogy a jo kis h aromsz ogek szama is p aratlan | tehat nem nulla. P di 2e 2e = e(2e2 n) . 1.79. a) 2 . b) legfeljebb n n n 1.83. El szr azt igazold, hogy a kezd pontot tetsz legesen megkzelti a vgpontok sorozata. 1.84. 2!(nn! 2)! (l. az alapfok u s ha tbbszr is megszmoltuk?" rszt! ) 1.85. n n 1.89. 3!(nn! 3)! 1.99. a) vlassz hozz a tbbi n {b l k {et! b) vlassz a tbbi n {b l k {t! 1.104. a) serld fel x y n {ben x{et s y {t! b) minden k elem rszhez rendeljk a komplementert (azaz a maradk n k elemb l ll halmazt)! 1.105. n 1.106. Ha az alaphalmaz pratlan, az llts trivilis. Pros n{re vegyk kln az f ; ; ; ng halmaz azon rszeit, amelyek az n{et tartalmazzk s kln azokat, amelyek nem. 1.108. Az n elem halmaz k elem rszeit osztlyozd aszerint, melyik a legnagyobb elemk. Prblj olyan megoldst is keresni, ami x y hatvnyait hasznlja! 1.113. A Pas al-h aromsz og n{edik soraban lev} o n darab binomi alis egy utthato n . Koz osszege 2n ul uk a kozeps} o a legnagyobb. 1.115. V alassz (a) k tag u bizotts agot es bel} ole eln ok ot; (b) egy eln ok ot es a maradekb ol k darab bizotts agi tagot. 1.116. Hasznalj komplex szamokat! 1.117. Oszt alyozd r s elem n{eseit aszerint, mennyit tartalmaznak az els}o r{b}ol ill. az utols o s{b}ol! 30 1.125. 50 3 2 1.127. n meghatrozza a fggvnyt). k (az rtkkszlet (2n)! n n 1.131.

1 2=

(

...

1)

1

( + )

2 1 2 ... +1

1

1

+1

2 =4

+

2

2 +1

1

+

22

2

2

2 . . . 22 =

2

n

1.143. A leemelt knyvek sorszmaibl ll, a felttelt teljest k tag sorozatokhoz rendelj felttel nlkli, de azrt szigoran monoton sorozatokat. Az eredmny: n k . k 40 40 30 60 30 . Osztik szma , ill. . Kzs oszt 1.144. 40 , van. Eredmny: 2 . 1.146. 4. 1.147. 1.149.

+1 10 = 2 5 20 = 2 5 41 41 41 31 41 + 61 31 41 31 = 2301 30 (12 + 14 + 13) + (5 + 4 + 7) 3 X

jAi j

X

22X

jAi \ Aj j +

X

61 31

jAi \ Aj \ Ak j . . .+( 1)n 1 jA1 \ A2 \ . . . \ An j

32X

X + 42 jAi \ Aj \ Ak \ Alj . . .

1.160. b) jAi \ Aj j jAi \ Aj \ Ak j (Milyen azonossg kell ide?) 1.163. El} osz or oldd meg u gy, hogy a reszek sz amozottak!

106 1.165. 1.166.

Elekes Gy:

n = 1; 2{re 2 ill. 3 lehet sg van. Vlassz szt kt esetet aszerint, hogy az els

tag a vagy b. Eredmny: Fn+2 . d j Fn s d j Fn 1 esetn d j Fn 2 is igaz. Ezt ismtelve d j 1{nek is teljeslnie

kell. 1.167. Tekintsd a Fibona

i{sorozatot mod m. Peridikus lesz. p 1.170. q n qn 1 qn 2 {b l q2 q , vagyis q1;2 12 5 megfelelnek. (rdekes, hogy az egyik vltakoz el jel mrteni sorozatot ad.) 1.178. lsd a 172. feladatot. R1 1.180. A bal oldal az 0 xr dx integrl egy kzelt sszege. 1.181. f r n a 0{tl n{ig terjed integrlnak fels sszege, a 0{tl n {ig terjed nek als sszege. P i nai . 1.182. n an i P n 1.183. i ai . o{kal s hasznld az el z feladatot! Eredmny: 1.184. Forgasd el az brt jobbra P n i an a0 . i 1.187. Az el z feladatbl r szerinti teljes induk ival kvetkezik. n n 1.188. p2 n p2 n n {b l p2 n 2 1 n. n n 1.189. p3 n p3 n p2 n {b l p3 n . 3 2 1 Pd n 1.190. i=0 i .

=

+

= +1

=

()

+1

= ( 1)

120 ( + 1) = ( ) + ( + 1) ( ) = + +1 ( + 1) = ( ) + ( ) ( ) = + + +1 =

tletek s eredmnyek a 2. Fejezethez

0

1

2.2. Nin s. n pont esetn {tl n {ig minden fokszmnak el kellene fordulnia, de a kt szls egyszerre lehetetlen. 2.3. a) igen; b) nem (hny le lenne egy ilyen grfnak?) 2.4. Nin s. (Hny l menne az els ngy pontbl a msik ngybe?) 2.6. Hasznld az el z feladatot! 2.7. Egy leghosszabb u t egyik vegpontj abol indul el az u t valamelyik pontj aba. 2.9. Egy legrvidebb sta biztosan t lesz, klnben kihagyhatnnk bel le egy (vagy tbb) krstt. 2.10. Sta biztosan van; vegyl egy legrvidebbet! 2.12. Nem. Azon keresztl brmely kt pont kztt vezetne sta; egyestsk is sszefgg lenne. 2.13. Ha nem lenne az, mennyi lehetne a (leg)kisebb komponens egyik pontjnak foka? 2.14. Nem. Kt n{pont komponens ellenplda. 2.15. Igaz. 2.21. a){b) Hasznld az el z feladatot; egy maximlis sta biztosan Euler. ) Ez

sak trfa; ilyen grf nin s, lsd 6. feladat. 2.25. a) Igen. b) Nem. A 25. lps utn a kiindulval ellenttes szn mez n leszel. 2.26. Mr az a) rszre is tagad a vlasz; gyeld a ngy kzps mez t s a sarkokat! 2.30. Induk is lps: vgy egy minimlis fok x pontot s egyik y szomszdjval, melynek foka kisebb n -nl, hzd ket ssze egyetlen pontt! Ha ilyen y nin s, egyszeren hagyd el x-et.

1


107

2.35. Igen. Ha minden pont legalbb msodfok volna, lenne a grfban kr. 2.36. Teljes induk i n szerint. Az el z feladat szerint van els fok pont; azt hagyd el! 2.37. n k 2.41. Igen. Egyet tudunk (35. feladat). Indulj el bel le; sak egy msikban akadhatsz el. 2.44. A Petersen grafbol indulva keszthet} o ellenpelda 12 ponton. Haszn ald a 2.32/ . feladatot. 2.45. b) Ha nin s 3{nl nagyobb fok pont. 2.50. Nem. 2.51. lsd a 17. feladatot! 2.53. Vegyl egy feszt ft! 2.54. Csak azokbl, amelyekben van kr (nem fk). 2.55. Valamelyiknek n {nl tbb le van. 2.56. A 39. feladat szerint az j l kt vgpontja kztt pontosan egy t vezet. 2.57. Vegyl egy feszt erd t s alkalmazd az el z feladatot! 2.58. Vegyl egy feszt ft! 2.60. Ha az a{b lt elhagyva a maradk sztesne s pl. az a{t tartalmaz komponensben lenne tovbbi pont, akkor a sztvg pont volna. 2.62. Igaz. Sem az j pont, sem a rgiek nem vghatjk szt. 2.63. Vegyl a grfhoz egy j pontot s V1 tetsz leges kt pontjt ksd ssze vele. Hasznld az el z s a 61. feladatot! 2.64. a) maga a de n i; b) az el z feladat szerint igaz, ha G ktszeresen sszefgg . Visszafel, ha pl. az x s u s sztvgn y {t s z {t, akkor az x{b}ol y {ba men}o utak nem erinthetnek z {t. 2.65. Igaz! 2.68. Tegyk fel, hogy lenne kt klnbz kzs pont. Ekkor a kt blokk egyestse is ktszeresen sszefgg volna, mert egyetlen pontja sem lehetne sztvg. 2.72. Vegyl egy maximlis krt s bizonytsd be, hogy minden pont benne kell legyen! 2.74. A nyertes (aki a legtbb gy zelmet aratta) biztosan ilyen. 2.75. A gy ztes legy z i kztt lesz ilyen. 2.78. n=3{ra a krbevers j. Minden jhoz hozzvehetsz kt jabb pontot; gy induk ival minden pratlanra van. Kell mg n=6{ra (prbld meg!) s onnan jabb induk i. 2.79. pn = n 2 n2 2.85. Mindkt irnyban megy legalbb egy l. 2.86. Az el z megolds elgsges is: ha x{b l nem minden pontba lehetne eljutni, akkor a bel le elrhet ek halmazbl nem vezetne ki l. 2.88. Egy hromszg vagy egy sillag. Ha nem ktjk ki, hogy sszefgg legyen, akkor mg nhny izollt pontot is hozzvehetnk. n 2.89. 2 2.93. Izollt pontokbl, utakbl s krkb l.

1

(3 4)

2( )

108

Elekes Gy:

2.94. Tedd fel, hogy nin s. Vegyl egy legrvidebb utat, amely a kt eredeti t valamely pontjait kti ssze. Ennek segtsgvel az els kett nl hosszabbat rakhatsz ssze. 2.95. a){b) Tekints egy leghosszabb utat! d) Nem. 2.98. Prostsd ssze valahogy a pratlan szmokat! 2.101. A pros sszeg mellett szksges (s azzal egytt elgsges is) brmely k n{re n k X X f ; di k g di . i=1 i=k+1 2.103. Teljes induk i n szerint. d1 biztosan 1. Ksd ssze az 1{es s az n{edik pontot s hagyd ki az el bbit; az n{edik j foka legyen dn . 2.105. Ha ktosztly, akkor nyilvn pros. Msrszt, ha az el z feladatra j mdszert adtl, az pontosan akkor fogja azt jelezni, hogy a kettoszts lehetetlen, ha pratlan krt tall. 2.106. Egy legnagyobb lszm pros rszgrf minden pontjnak foka legalbb az eredeti grfbeli fokszm fele (klnben ttennnk). 2.112. a) sereld ki a kor F1 {beli eleit a nem{F1 {beliekre! b) ugyanaz az u tra. 2.113. A B1 [ C1 {beli pontok sak B2 {beliekkel lehetnek osszek otve. 2.115. Vegyel egy maximalis elsz am u p arost ast! 2.118. Hasznld az el z Hall{ttelt (115. feladat)! 2.120. Reprezent ald az }oroket egy-egy s u

sal, az } orhelyeket ket{ket s u

sal! 2.123. Hasznld az el z Hall{ttelt (115. feladat)! 2.125. Igen. Az el} oz}o otlet akkor is m} ukodik. 2.137. Repezent ald a nem-nulla elemeket p aros gr aal: x 2 V1 {et es y 2 V2 {t kosd ossze, ha a m atrixban aij 6 . 2.143. Keress lefog pontrendszert annyi ponttal, ahny le F {nek van s alkalmazd az el z feladatot! 2.148. Legfeljebb n d f uggetlen el letezhet. 2.156. ppen a pros grfok. 2.157. Vedd sorra a pontokat. Mindegyiknl legfeljebb d tiltott szn van; legalbb egy lehet sg mindegyikhez lesz. 2.158. Vlassz egy a sztvg pontot s sznezd a rszeket (mindegyikbe belertve a{t is) gy, hogy a mindig piros legyen! 2.161. Vedd sorra a pontokat nvekv x{koordinta szerint! 2.162. Nem. 2.163. Vedd a s sokat olyan sorrendben, hogy az utols foka k {nl kisebb legyen s rajta kvl brmely msikbl vezessen l ks bbi pont(ok)ba! 2.164. Ha az sszektttsg" rel i tranzitv volna, a grf teljes lenne. 2.166. Nem. Egy pratlan kr ellenplda. 2.167. a){b){ ) normlisak; d) a Petersen grfban ! , ; e) s f) sem normlis, ha hromnl tbb pontak. 2.170. Igen. 2.176. a) lerajzolhat; K3 s K4 is; a tbbi nem. 2.177. Ugyanaz.

max 0

(

1)

1

(

)

=0

=2 =3

109


2.180. Szmolj ssze minden lt ktszer gy, hogy minden lapra sszeadod az t hatrolkat; l e. Ebb l s az Euler{ttelb l: e n . 2.181. Hzz be tlkat addig, amg minden lap hromszg lesz; erre a grfra hasznld az el z feladatot! 2.182. Ha minden pont foka legalbb hat lenne, az lszm legalbb n volna. 2.185. a) kt pont kztt annyi l, amennyi az eredeti krnek volt; b) maga; ) s d) egyms dulisai. 2.187. Igen. Pl. kss ssze kt pontot ngy klnbz hosszsg ttal. 2.188. Igaz. 2.191. Az Euler{grfokra; azaz amelyekben minden pont foka pros. 2.192. Nggyel. 2.193. Hasznlj dulis grfokat!

3 =2

=3

6

3

tletek s eredmnyek a 3. Fejezethez 3.1. El szr pl. az 500{adikkal hasonltsd ssze! Felezgetssel tz (!) alkalmas elem vizsglata elg. 3.2. 17 sszehasonlts kell. 3.3. Egy kivtelvel mindegyikr l ki kell dertened, hogy van nla nagyobb. Ehhez legalbb n sszehasonlts kell. Ennyi elg is. 3.6. k l . 3.7. Egy-egy menetben kett} o, negy, nyol , , stb. hossz usag u reszeket osszefes ulve a lepesszam menetenkent O n es osszsesn d 2 ne menetre van sz ukseg. Lepesszam: O n n.

+

1

1

( log )

()

...

log

tletek s eredmnyek a 4. Fejezethez 4.4. Lsd az el z feladatot! 4.6. Lsd a 182. feladatot. 4.8. Tkrzzk Mary lakhelyt a part vonalra; arra kell indulnia Billynek. (A Billy | Mary-tkrkpe" utak szksgkppen metszik a partot, gy kl snsen egyrtelmen megfelelnek a Billy{folypart{Mary" utaknak.) 4.10. a) 5 b) 14 4.11.

27 27 12 162n 4.12. 2nn n+1 4.27. a0 = 0, an = 2an 1 + 1, mert n 1 {et ttve, a legnagyobb is elmozdthat lesz (korbban nem), majd az n 1 kisebbet kell jra a legnagyobbra juttatni. 4.28. 0 = 0, n = 3 n1 + k n. 4.29. t0 = 1, t1 = 1. A rekurzi: tn = tn 1 + 2tn 2 . 4.35. a) anP =na0 n!; b) an = a02n. 4.36. a0 + i=1 bi . 4.37. A0 = a0 ; An = An 1 + b(n)=n . 4.38. an = 2n 1. Ez persze teljes induk ival is igazolhat. 4.39. an = 2n+1 n 2. Ez is igazolhat teljes induk ival.

110

Elekes Gy:

:=

=

+

4.40. Q Cn 3 nn {re Cn Cn1 k 3nn , ahonnan 4.41. i . n Y i {vel rdemes leosztani. 4.42. i=1 4.43. Osszl vgig n {sal! Eredmny:

Cn = kO(1).
!

an =

1 + 1 + . . . 1 e n! 1 + 2 1! 2! (n 2)! 2

n!

4.47. Lehet, hogy sak egyfle van, ha a2 b; az is lehet, hogy sak komplex hnyadossal tallsz (ha a2 < b), de ekkor biztosan ktfle van. A mrtani sorozat kezd tagja persze tetsz leges lehet. 4.48. Legyen a kt gyk q1 ill. q2 . Ha xn {et 1 q1 n 2 q2 n alakban keressk, a

=4

4

+

1 + 2 = x0

1 q1 + 2 q2 = x1 4.49. 4.50. 4.55.

=

egyenletet kell megoldanunk. A megolds q1 6 q2 miatt ltezik (s egyrtelm).

1 qn 2 nqn alakban kereshetjk. A 1 x0 , 1 q 2 q x1 egyenletek megoldhatak, ha q 6 , vagyis ha b 6 , szval ha a rekurzi valdi msodrend. n. xn n a) 1 12x ; b) e2x . n=2 , ha n pros; , ha n pros; n ; b) n ; ) an a) d) an , ha pratlan. , ha pratlan. n! n n n n= , ha n pros; (n=2)! an , ha pratlan. X n xn .

+ =0 = ( + 3)2

=0

=

+

=

= 01 = (0 1) 4.58. = 0 = ( 1)( 2) . . .( 2 + 1) 4.59. 13 1 2 = 31 ( 23 ) 1 + 3x 4.60. Az 1+ x + x2 +. . . vgtelen mrtani sort akr P tagonknt derivlva, akr nmagval (minden tagot minden taggal) szorozva 1)xn addik. n (n + P P n+r 1 n 4.61. (n + r 1)(n + r 2) . . .(n + 1)=(r 1)! x = r 1 x . X 1 n +2 n 1 1 4.62. a) an = (n + 1)2n ; b) 25 = (5) x . (1 x5 )2 n 4.63. an = ( 1)n+1 3 2 1 . 4.57.

( 1)

3

tletek s eredmnyek az 5. Fejezethez 5.3. Lsd a kvetkez vgtelen Ramsey ttelt! 5.4. Lsd a kvetkez vgtelen Ramsey ttel tfogalmazst! 5.10. Hny msikkal kell egynek{egynek azonos tmrl leveleznie? Akiknek valaki nem az els tmrl r, azok kztt hogy lehet elosztva ez a bizonyos tma?

111


5.13. 5.15. 5.19. 5.20. 5.21. 5.22. 5.25. 5.26. 5.28. 5.30. 5.35.

5.36. 5.37. 5.38. 5.39. 5.45.

Esetleg mskpp megprblhatod a tudsokat egy telem halmaz pros elemszm rszhalmazaival kdolni. 6. Lsd 6. feladat. M k; l R k; l megfelel: az ; ; ; n pontok kztt hzzl piros lt az i s j pontok kz (i < j ), ha ai < aj ; kket egybknt. Hasznld Ramsey ttelt! Hasznld a 12. feladatot! Azon sznezsek szma, amelyekben van egyszn Kk , legfeljebb annyi, mint az egyenl tlensg bal oldala; a jobb oldalon az sszes sznezsek szma szerepel. Ha n k=2 , akkor teljesl a fenti egyenl tlensg. s {re tudjuk. Tovbb s szerinti induk ival, az s {edik s s{edik szneket egyetlen (pl. infravrs) sznnel helyettestve. Illessz r minden n{hez egy{egy n l utat egy kzs gykrre! Minden pontbl vezet t a gykrbe. Ez vgtelen sok t; a gykrre illeszked

vges sok l kzl valamelyiket ezen utak kzl vgtelen sok tartalmazza. Ennek msik vgpontjra ismteled a gondolatot, . a) Ramsey ttelb l kvetkezik. b) Ez is igaz. Teljes induk i r{re. Rendelj minden elemhez egy szmprt: a vele kezd d leghosszabb nv ill.

skken rszsorozat hosszt. Klnbz tagokra nem lehet mindkt szm azonos. Egy egysgnyi oldal o {os rombuszt (ez kt szablyos hromszgb l ll) forgass el egy hegyesszg s sa krl gy, hogy a szemkzti s s eredeti helyt l ppen egysgnyi tvolsgra kerjn. Az gy keletkez sszesen ht pontot vizsgld! Egy alkalmas mret ngyzetr s lapjait sznezd az egyik sorban periodikusan 1{es, 2{es s 3{as, a msik sorban 4{es, 5{s s 6{os, a harmadik sorban 7{es, 8{as s 9{es sznre; s megint ellr l. Egy hatszgr s (vgtelen mhsejt{bra) lapjait prbld sznezni. Alkalmas szlessg, egyik oldalrl nylt, msikrl zrt svokat sznezz felvltva pirosra s kkre! Ha nem lenne ilyen, akkor pl. egy piros pont krli egysgkr is piros lenne, annak pontjai krliek is, stb. De a sk brmely kt pontja elrhet egymsbl egysgnyi lpsekkel; az egsz sk piros lenne. Az lszm:

( )= ( )

=2

1 2 ...

2

1

...

60

8 <

3k2 , ha n = 3k ; T3 (n) = 3k2 + 2k , ha n = 3k + 1; : 2 3 k + 4k + 1 , ha n = 3k + 2; 2 n oszthat hrommal; = n(n2=3 1)=3 ,, ha ha nem. = bn2=3 (

3)

5.46. Mint a 44.feladatnl, sak "hrom lpsenknti" induk ival n {rl n{re. Az induk is lpsnl egy hromszgb l indulj, ha van. (Ha nin s, hasznld fel a 44.feladat eredmnyt!)

112 5.51. 5.57. 5.58. 5.60.

Elekes Gy: pl. osinus{ttellel a legnagyobb szgre; elemileg (Pythagoras{ttellel) is lehet. A rossz" pontprok nem alkothatnak hromszget. a) n , mert erd . b) T2 n bn2 = , mert pros grf. a) bn= . b) n, ha minden komponense hromszg; tbb nem.

1 ( )= 4 2 n(k 1) , mert minden pont foka legfeljebb k 1. 5.61. 2 5.62. lsd a 41.feladatot.

5.63. Elg teljes pros grfokat nzni. De niljunk s hasznljunk k { seresznyket! 5.64. Kn=2;n=2 nem tartalmazhatja G{t.
0

1

tletek s eredmnyek a 6. Fejezethez 6.19. Egy max{vissza sorrend utols o ket s u sa megfelel. 6.20. Vedd a pontokat egyenkent, tartsd nyilv an {tol e{ig indexelt listakban, melyik pontok azok, amelyekb} ol eppen t el megy vissza. ( t e). Az ilyen el u listakat neha v odr oknek" nevezik. 6.22. A p{b l indul lek kzl a legkisebb sly(ak) msik vgpontja(i) legol sbban egy lpsben rhet (k) el. 6.25. Minden x pontbl hzz irnytott let abba a pontba, ami W x utols skkentsekor volt >jPont! 6.26. Tartsd a Wspe rtkeket egy kupa ban! Mind a trls, mind a skkents O n id ; a minimum kivlasztsa konstans. 6.27. F [ e {ben egyetlen kr van; ennek brmely le megfelel. 6.28. F1 n f1 kt komponense kztt F2 {nek megy le. Ezek brmelyike megfelel. 6.29. Az el z megoldsbl add f2 ezzel a tulajdonsggal is rendelkezik, ha gy vlasztjuk, hogy benne legyen F2 [ f1 (egyetlen) krben. 6.30. Nyilvn krmentes, mert gy vlasztottuk az leket. Ha nem lenne sszefgg , akkor kt komponense kztt kihagytunk volna legalbb egy let. Ezek azonban nem zrhatnak krt semmifle korbban vlasztottal sem; ellentmonds. 6.34. Egy mohn vlasztott l az optimlis lrendszerb l legfeljebb kt, az vnl nem nagyobb slyt zr ki.

0

0

()

(log )

113


6.35. kr {et a 27. feladat szerint be serlhetjk M {be gy, hogy elhagyjuk M [ kr egyetlen krnek valamelyik lt. Ez a kr azonban tartalmaz i r index lt, mert ellenkez esetben K {nak is kre lenne.
sak maga lehet. 6.37. Ugyangy, mint az eredeti algoritmusnl, sak itt a 28. feladatot kell hasznlni. 6.39. Leghosszabb lt nem hzhattuk be. 6.40. Mint az el z feladatban, a kr maximlis sly lei kzl az egyiket nem lehet bevenni.

=(

)

tletek s eredmnyek a 7. Fejezethez 7.9. A bal vegpontok koz ul a jobbszels}o (vagy a jobb vegpontok koz ul a balszels}o) j o. 7.10. a) A ; =n nylt intervallumok i ; ; ; b) Az x n felskok. 7.13. a) pl. egy D oldal u szabalyos h aromsz og nem; b) igen (barmely pontja kor ul rajzolt kor jo). 7.15. Az el} oz}o feladat koreire a a 14. feladat szerint hasznalhatod Helly tetelet. 7.16. Mint az el} oz}o feladat, sak most a vegtelen Helly{tetelre van sz ukseg. 7.19. Hogy valamely rossz z art felsk (felter) hatar an van, az a de n i o. Rossz z art felskot eleg kevessel eltolva rossz nylt vagy z art felskot (felteret) kapunk. 7.30. Igen. De ni ald H0 fx0 g p arjainak sznet aszerint, hogy x0 {lal egy utt milyen (eredeti) szn} u h armast alkotnak es hasznald a vegtelen Ramsey tetelt (5.21. feladat). 7.31. Igen. Az el} oz}o feladat H1 -eb}ol valassz egy x1 {et, hozz a egy H2 {t, , stb. 7.32. Induk i o r szerint. Induk i os lepeskent az el} oz}o ket feladata altalanosthat o. 7.33. A vegtelen valtozatb ol ugyan ugy kovetkezik a K} onig lemma segtsegevel, mint a gr af{teteleknel lattuk. 7.36. Sznezd a pontharmasokat aszerint, hogy konvex vagy konk av (harom pont u) vet alkotnak. 7.37. K m R3 m; m , mert ennyi pont biztosan eleg. m , mert mar ennyi pont is biztosan eleg. 7.39. K m m 7.40. A gr af s u sai a pontok; a Pi Pj el s ulya az } oket osszek ot}o szakasz meredeksege. N ov} o ( s okken}o) ellan konvex (konk av) vnek felel meg. 7.43. A 38. feladatban de nialt halmazokbol helyezz el megfelel} o pontsz am u, eleg lapos" es eleg ki si" peld anyokat egy eleg nagy" kor majdnem f ugg} oleges" ven! 7 klnbz prt kell fednie. 7.45. A ht hrmasnak egytt 32 2 7.46. Igen, pl. f ; ; ; ; ; g s az fi; g i prok. 7.47. E minden pontjn t pontosan egy egyenes megy, ami illeszkedik p{re; ezek az egyenesek mind klnbz ek. 7.50. ) ppen a 44. feladatban szerepl Fano{sk.

(0 1 )

( = 1 2 . . .)

...

( ) ( )

2

(

) 4 +1 2

123456

7

= 21 = 7 (1

6)

114

Elekes Gy:

+2 +2

7.60. n darabot. 7.61. n pont esetn minden egyenes vagy 0{t, vagy 2 {t tartalmazna kzlk. 7.65. Hasznld fel egyrszt, hogy n egyenes sak akkor foghatja le az sszes pontot, ha egy ponton mennek t; msrszt egy ltalnos helyzet ponthalmazt pontosan egy pontban metsz egyenesek fedik az alaphalmazt. 7.66. Pldul f x; y; y x2 g [ f ; ; g. 7.67. r n rn n r{et. 7.69. Mg az is elg, ha a kzs rszekre sak azt tesszk fel, hogy pl. legfeljebb egy elemek. (Nem kell kiktni, hogy nem resek.) 7.71. a) Hrom, nem egy ponton tmen egyenes pontjai, kivve a hrom metszspontot: n pont. b) Kt egyenes pontjaibl hagyj ki egy{egy pontot (nem a kzset) s vegyl hozz a kt kihagyott pontot sszekt egyenesr l egy jat: n pont. 7.75. Az res halmazhoz egyenknt kell az n elemet hozzvenni; n lehetsges sorrend van. 7.76. Ha jX j k , akkor k n k {ban. Valban, A0 ;{tl X {ig k rszln van; X {t l a teljes n elem halmazig n k . 7.87. Teljes induk i o r szerint. 7.88. P Ha van pontosan k elem Hi , akkor trivilis. Ellenkez esetben tedd fel, hogy i vi s emeld ngyzetre ezt az egyenletet! 7.91. 16 2 7.95. Igen. elemen van (negyedrend) vges geometria. Ennek minden egyeneshez vegyk hozz a harmin kettedik elemet! 7.96. vi vj pros, ha i 6 j ; pratlan, ha i j . 7.103. Legfeljebb n{et; pl. az egyelem} uek jok. Tobbet nem lehet; a bizonyt as hasonlo P aratlanfalva tetelenek GF feletti bizonyt as ahoz; persze most GF felett.

1+(

+1

( 1); = 1)( + 1) =

3(

(0 1 0) +

1)

!

=

2

!(

)!

=0 31 = 5 +5+1 =

(

)!

=

2

!

=

(2)

(3)

115


IV. RSZ

Megoldsok

116

Elekes Gy:

Megoldsok az 1. Fejezethez 1.52. Eredmny: kett . Feltehetjk, hogy a tetrader gy ll, hogy az alap piros. Fordtsuk magunk fel a kk lapot! A maradk kett re kt lehet sg van. 1.61. Rossz, ha nin s se kt fekete, se kt kk. Magyarul: mindkt fajtbl legfeljebb egy van, vagyis legfeljebb kett t hoztl. Hrom zokni kztt lesz pr. 1.62. Rossz: legfeljebb egy kk van; hozz legfeljebb 12 fekete lehet. Maximlis rossz: 13 darab. Teht 14 elg. 1.98. a) rendre 1, n, n, 1

b) a kt szls

1.102.

96

n(n 1) n(n 1)(n 2) n! 6 2!(n 2)! = 2 ; a kzps k rtke

I. megolds:
103 = 12 10

1

k+

k

2

k

i 3 + . . . + ( 1)

k i

+... = 0

{szor szmoltuk, vagyis vgl is egyszer sem. 1.150. Ai jellje azt, hogy az i{edik dosszi res marad.

jAj = 420 jAi j = 320 jAi \ Aj j = 220 jAi \ Aj \ Ak j = 120 jA1 \ A2 \ A3 \ A4j = 0, mert minden paprlap kerlt valahova.

420 41 320 + n(n 2) + n = n(n

Eredmny:

1.151.

n

3

42 220 43 4)(n 5) 6

I. megolds: sszes hrmas: n Ai esemny: Az i{edik s a rkvetkez benne van; ekkor a harmadikra n lehet sg marad. ; ha i s j szomszdok a krn. (Ilyen prbl n van); jAi \ Aj j ; ha nem.

(

2)

3

= 10

117


3

Ai \ Aj \ Ak s a tovbbiak lehetetlenek, ha n > . II. megolds: Egyet n flekppen vlaszthatunk. Szomszdait nem vehetjk, gy a knyvespol os 143. feladatra jutunk, n elemmel, kzlk k vlasztand. Mindhrom lehetett els , teht osztunk hrommal is. Legyen A az osszes kiv alasztas halmaza; Ai pedig jel olje azokat, amelyeknel kivett uk az i{edik p a rt ( i ). 10 8 10 6 10 . Eredmeny: 10 6 1 4 2 2 3 Fn+1 . Teljes induk ival bizonythat: I. n {re igaz. II. Tegyk fel, hogy n, vagy kevesebb lp s esetn az llts igaz. n lp s n felmenve el szr vagy egy lp s t, vagy kett t lpnk. Az induk is felttel szerint az els vltozat Fn+1 , a msodik Fn klnbz mdon folytathat. Ez sszesen Fn+2 . Az el z feladat jellseivel Fn

1 q1 n 2 q2 n {et n ; {re alkalmazva 1 1 p5 megfelel.

1 p5 , ill. 2 a) Fn+2 ; klnbztesd meg azt a kt esetet, hogy az els knyvet levetted-e, vagy sem. b) n kk ; A leemelt knyvek sorszmaibl ll, a felttelt teljest k tag sorozatokhoz rendelj felttel nlkli, de azrt szigoran monoton sorozatokat. Az an f 4 n sorozatra an negyedfok polinom lesz.
3

1.152. 1.164.

1.172. 1.173.

= 1 . . .10 +

=2

1

=1

+1

=

=

=

+

=01

+1

1.191.

6

= ()

n f 4 (n) = 24

n

n

n

n 5 + 60 4 + 50 3 + 15 2 + 1

1.192. a) Nem. Ngy kr sak 14 rszre oszt. b) n2 n . Ha k0 {t 2{nek vesszk, akkor kn+1

+ +2

:

= kn + 2n.

Megoldsok a 2. Fejezethez 2.11. Igen. egymagban sszefgg rszgrf. Ha nem maximlis ilyen, akkor b vtsk, amg lehet. Vgl egy, tovbb mr nem b vthet sszefgg rszt kapunk. 2.16. Tegyk fel, hogy az elhagyott l a maradk grf kt klnbz komponenst kti ssze! Ekkor kt vgpontja kztt nem lehet ms t; nem egy kr le volt. 2.17. Igaz. Az el z feladat szerint amg a grfban van kr, addig elhagyva egy kr egyik lt a grf tovbbra is sszefgg marad. Ha mr nin s tbb kr, a maradk rszgrf fa. Rviden: egy minimlis sszefgg rszgrf nem tartalmazhat krt. 2.61. Legyen a s b kt tetsz leges pont. (Ha vezet kztk l, akkor az el z feladat szerint kszen vagyunk.) Mivel G sszefgg , van kzttk t, pl. a v1 ; v2 ; ; vk b. Legyen j a legnagyobb index, amelyre van kt, kzs bels

pont nlkli a{vj t. Megmutatjuk, hogy j k . Tegyk fel, hogy j < k s vegynk kt a{vj utat! Ha valamelyiken lenne j {nl nagyobb index v , akkor oda is vezetne kt j t, ami lehetetlen. Mivel vj nem

...

=

=

=

118

2.69.

2.81. 2.82. 2.84.

2.124. 2.153. 2.154. 2.159.

2.178. 2.183. 2.196.

Elekes Gy: vg szt, van t elkerl t vj +1 {b l vissza a{ba; ennek pedig van egy legels

pontja a kt a{vj t valamelyikn. Az eddig terjed rszttal ill. a vj vj +1 llel kiegsztve az eredeti a{vj utak egy{egy rszt, kt j a{vj +1 utat kapunk. Teljes induk i n, a versenyz k szma (vagyis a grf pontszma) szerint: I. n=1{re (vagy n=2{re) igaz. II. Tegyk fel, hogy az n{nl kisebb szmokra mr tudjuk s tekintsnk egy n{rsztvev s versenyt! Vegyk ki az egyik versenyz t, pl. a{t. A tbbiek az induk is felttel szerint megfelel en sorballthatk. Ha a sor elejn ll kikapott a{tl (ill. ha a sor vgn ll legy zte a{t), tegyk a{t az els (ill. utols) helyre; egybknt pedig az els olyan el, akit legy ztt. Nyilvn szksges, hogy minden pont foka pros legyen. Ez elg is, mert ekkor van (irnytatlan) Euler{krsta; ennek sorrendjben irnytsuk az leket. Az lek irnytst elfelejtve a grfnak sszefgg nek kell lennie; minden x

s sra pedig dG x d+G x legyen. E kt felttel egytt elg is. Els rsz: egy pontbl elrhet k keresse. Msodik rsz: fordtsd meg az sszes let s ugyanabbl a pontbl jra keress. Ha mindktszer minden pontba eljutottl, er sen sszefgg ; egybknt nem. Lpsszm: lszm. (Lsd mg a 4. feladatot.) Az egyik osztly tetsz leges k pontjbl k r l indul. Ezek nem gylhetnek ssze a msik osztly k {nl kevesebb pontjba, mert ott is r a pontok foka. Nem. Legalbb kt olyan soport lenne, ahol senki se prja se Kar sinak, se Mar inak. Ezekben pratlan szm gyerek van; kzlk egynek{egynek nem jut pr. Ha nem teljeslne, akkor nem juthatna minden pratlan komponensbe a kijellt k pontbl pr; egy ilyen komponensb l legalbb egy elem nem kaphat prt. (a) pratlan kr; (b) pratlan oldal kerk" (kr s benne egy tengely kll kkel"); ( ) pratlan kr s egy teljes grf; a kt rsz kztt minden mindennel sszektve. Ha G lerajzolhat, akkor az sszehzott is. Visszafel nem igaz; akr K5 {b l, akr a hrom{hz-hrom{kt"{bl skbarajzolhat grf keletkezik, ha egy lt sszehzzuk. Teljes induk i n szerint. Hagyj ki egy legfeljebb tdfok pontot, sznezd a maradkot; vgl a kihagyott pontnak is jut egy a hat sznb l, mert t szomszdja legfeljebb t sznt zr ki. Fogalmazzuk meg, milyen G0 grfokra vonatkozik a fenti bizonyts": egy r{ regulris s egy {regulris egyestsre. A hiba ott van, hogy nem minden r {regulris grfot kaphatunk meg gy! (Pl. hat ponton kt hromszg nem ilyen, br 2{regulris; ez persze ellenplda az lltsra is.) Az llts igaz; a bizonyts se teljesen rossz, sak hinyos. (A hiba ugyanaz, mint az 196. lltsnl, sak ez javthat.) Az hinyzik, hogy minden n pont fa el ll alkalmas n pontbl egy l hozzvtelvel. Ezt gy mutathatjuk meg, hogy az n pontbl indulunk: elhagyva egy els fok pontot (tudjuk, hogy

( )= ( )

1

+1

2.197.

+1

+1

119


ilyen ltezik), a maradk szksgkppen sszefgg (s nyilvn krmentes is) lesz. 2.198. A hiba ugyanaz, mint az el z feladatokban; itt az llts igaz, de a bizonyts teljesen rossz. Sok ms n pont grf is van, nem sak azok, amelyek egy n pont teljesb l plusz mg egy lb l llnak. I.J megolds: Induk i n szerint. a) n {re igaz. b) Tfh. n{re igaz, s tekintsnk egy n pont G grfot! Hagyjuk el G egy olyan x pontjt, melynek d x foka minimlis. (Ekkor d x , mivel ellenkez}o esetben nem lehetne eleg el G{ben.) Ha d x n , akkor a tbbi pont foka is ennyi, teht a grf teljes. Ha d x n , akkor legalbb

1

=2

()

+1

() 1

( )= 1 () 2 (n 1)(n 2) + 1 (n 2) = (n 2)(n 3) + 1 2 2 l marad egy n 1 pont rszen, amire az induk is felttel mr alkalmaz1

hat: G x sszefgg , s x{et | a bel le indul legalbb egy llel egytt | visszavve sszefgg grfot kapunk. Ha d x , akkor legfeljebb n n = l lehet | ellentmondas. II.J megolds (Elemi szls rtk{feladattal): Ha G nem sszefgg , akkor kt nem-res rszre oszthat, melyek kztt nem megy l. Legyen az egyik rsz pontszma k , a msik n k (nyilvn k; n k n ). Hny l lehet a kt rszben sszesen?

( )=0

(

1) 2

1

1

e

k

2 +

n k

2

=k

2 k + (n k)2

2

(n

k)

2 = k + (n2

k)2

n

2

2 + (n 1)2 n n2 3n + 2 n 1 1 = 2 ; 2 2= 2 mert a k 2 + (n k )2 sszeg maximuma k = 1{re (vagy k = n 1{re) addik.

2.199. Nem szabad alkalmazni az induk is felttelt, mert a maradk grf nem felttlenl j"! Helyes megolds: Vegyl egy maximlis krt s erre hasznld a fenti tletet!

Megoldsok a 3. Fejezethez 3.11. Cskkentsnl a gykr fel indulva ellen rizzk, hogy az egyenl tlensg megsrlt-e. Ha nem, lellunk; ha igen, ki serljk az aktulis s sot a szl vel s a szl t ellen rizzk tovbb. Nvelskor hasonl az eljrs, de ellenkez

irnyban haladunk; ha valamelyik gyereknl kisebb a sly, mint az j rtk, akkor a kisebbik gyerekkel serlnk. A trls olyan, mintha 1{t rnnk be; a

120

Elekes Gy:

beszrs olyan, mintha egy j, 1 sly levelet vennnk a grfhoz, majd annak slyt skkentennk. 3.12. nlogn nyilvnval, ha n{szer vesznk be j elemet. Ennl jobb, ha egy majdnem teljes binris ft ksztnk, ami az egyenl tlensgeket nem teljesti, aztn a levelek fel l indulva szintenknt javtunk.
2

X

X h h k2h k 2h k < 2 2 2n:

2

Megoldsok a 4. Fejezethez 4.1. a) r 1 . Egyik rsz sem res, s minden valdi rszhalmaz pontosan egy kettvgsban szerepel. b) r2 . Ahny lehet sg van az egyetlen ktelem rsz vlasztsra. 4.2. S r; k , ha k < vagy > r. Egybknt S r; k S r ;k k S r ; k , ugyanis az r{edik elemvagy nmaga egy rsz, vagy kisebb indexekhez kerl. k k r r 4.3. a) k r k k 2 b) k S r; k . Eszerint az a) alatti kifejezs oszthat k {sal. 4.9. A rossz utak szma egyenl a ; {bl a ; {be (azaz a (7,11) tkrkpbe vezet ) utak szmval. Eredmny: sszes { rossz 4.13. Osztlyozd a lehet sgeket aszerint, hnyadik pr utn fogy el el szr az sszes tizes. Ha nem rgtn az elejn, akkor addig rendre F t; F t; F t; ; F t; F t; F t kellett hogy legyen a gyerekeknl s, mivel kzben nem rlt ki a pnztr, a F t; F t; F t; ; F t; F t szakasz egy rvidebb j sorozat. n X n 4.30. Sn S , ha n . (Vlassz szt eseteket aszerint, hogy hny s k n k k=1 pontosan mely x n{ekre lesz f x .) Qn+1 n , teht az An+1 an+1 = n helyettests lszer. Ebb l 4.44. i=1 i n(n 1)(n 2) . n 2) , vagyis a A1 , An+1 An n , teht An (n 1)( n 2 2 Ez megsejthet az els nhny tag felrsa utn a dieren ia{sorozatokbl is; utna teljes induk ival igazolhat. P n n+1 xn . 4.64.

2

1

( )=0 1 ( 1) + ( ! ( )

( )= ( 1

2) . . . (0 0)

20 20

(14 4)

! = 187 18 14 10 10 ? . . . ?

10 ? ? . . . ? 20 = 1 1 ( )=1 ( ) = +1 = ( + 1) =0 = +( 1) =

1 3 1 1 1 3 1 (1 + x)(1 + 3x) = 2 (1 + 3x) 2 (1 + x) = ( 1) 2

4.70. A msodik kplethez hasznld fel a

g(x) =

1 ekx 1 ex X 1 1 = 1X k = k+1 2 1 e2 2 k=0 2 k=0 2 x

azonossgot!

Megoldsok az 5. Fejezethez

1)+ ( 1 )

=

121


5.5. Jelljk a vgtelen teljes grf pontjainak halmazt V {vel s vlasszunk ki egy tetsz leges x1 2 V pontot! A bel le indul lek kztt a kt szn valamelyike vgtelen sokszor fordul el (esetleg mindkett ). Vlaszthatunk teht egy V1 V n fx1 g ponthalmazt gy, hogy az sszes x1 ; y l egyszn, ha y 2 V1 . Vlasszuk ebb l az x2 2 V1 pontot tetsz legesen s ehhez a V2 V1 n fx2 g halmazt gy, hogy az sszes x2 ; y l egyszn legyen, ha y 2 V2 . (Ez a szn klnbzhet az el z t l, az x1 {b l a V1 pontjaiba men lek sznt l!) Az eljrst folytatva olyan

(

(

)

)

xn 2 Vn 1 Vn 2 n fxn 1 g

(

)

pont{ s rszhalmaz{sorozatot kapunk, melyben rgztett n{re az sszes xn ; y lek egysznek, ha y 2 Vn . (Ez a szn persze n{t l fgghet.) Kvetkezskppen k > n esetn az sszes xn ; xk l azonos, sak n{t l fgg szn. Kt rszre osztva az fxn n < 1g sorozatot aszerint, hogy ez a szn piros vagy kk, egyszn K1 {t kapunk. 5.12. R ; t R t; t trivilis. Tovbb az el z feladat alapjn az R k; l {ek tblzatnak tlin ( k l szerinti") induk ival. El szr a mr ismert R ; addik, majd R ; s R ; , stb. 5.14. A 11. feladat gondolatmenett hasznlva megmutathatod, hogy ha egy grf leit pirossal s kkkel sznezve nin s se piros hromszg, se kk K4 , akkor minden pontra legfeljebb hrom piros s t kk l illeszkedhet, ami kilen (teht pratlan) pont grfban lehetetlen. Nyol ponton nem nehz piros hromszg s kk K4 nlkli sznezst tallni, ha gyelembe vesszk az el z fokszm{felttelt. 5.16. Nem. Mg R d ;d sem, mert akkor lenne a pontok kztt d , melyek kztt minden tvolsg azonos; ez pedig a feladat elejn szerepl llts miatt lehetetlen. A pontos maximum nem ismert, sak annyit tudnak, hogy n

( ) ;1 (2 ) = ( 2) = + (3 4) (4 3) 10

( ) (3 3)

( + 2 + 2)

+2

+1 + +1= +2 2 2 !

+1 2

n kztt van. n s n 5.24. N(s) = des e megfelel. Legyen adva ugyanis az N {ig terjed termszetes szmok egy tetsz leges s{osztlyozsa. Rendeljk ehhez az ltaluk fesztett teljes grf leinek azt a sznezst, ahol az a; b l az annyiadik sznt kapja, ahnyadik osztlyban az ja bj van. Az el z feladat szerint lesz egyszn hromszg, pl. az a < b < pontokon. Ekkor x b a, y b s z

a j megolds lesz. 5.27. Alkalmazd a Knig{lemmt arra a fra, melynek n{edik szintjn az ; ; ; n pontokon rtelmezett teljes grf piros Kk s kk Kl nlkli sznezsei vannak; a szomszdos szinteken kt ilyen sznezst kss ssze llel, ha a nagyobbik ugyangy sznezi a kisebb pontjai kztti leket, mint a kisebbik. Ha R k; l nem ltezne, a fa minden szintje nem-res s vges lenne. Egy vgtelen t azonban K1 olyan sznezst adn, amiben nin s se piros Kk , se kk Kl ; a vgtelen Ramsey ttel szerint azonban egyszn K1 is van. Tbb sznre a bizonyts hasonlan megy. 5.29. Az a1 ; a2 ; ; an sorozathoz rendeljk a V v1 ; v2 ; ; vn pontokon

( ) =

=

=

1 2 ... ( )

...

...

=

...

...

122

Elekes Gy: adott vgtelen teljes grf kvetkez sznezst: ha

(xi ; xj )

piros; ha ai kek; ha ai

Az egyszn K1 monoton rszsorozatot jelent. 5.42. Igazold (s hasznld fel), hogy x n x < y n

(

)

(

i < j , akkor

aj ;

> aj . y), ha x < y n=2.

Bizonyts: az el z eredmnyb l igazold (s hasznld fel), hogy maximlis lszm n{pont r{osztly grfban kt osztly mrete kztt a klnbsg nem lehet 2 vagy tbb. 5.44. Teljes induk ival "kt lpsenknt": I. n {re s 3{ra (vagy 1{re s 2{re, zls szerint) igaz. II. induk is lps (n-2){r l n{re: tegyk fel, hogy az lltst mr ellen riztk n {re s vegynk egy n{pont, hromszg nlkli grfot. lszma legyen e. Vegyk ki egy a; b lt. (Ha nin s egy le sem, az llts nyilvn igaz.) A maradk n pontbl legfeljebb n l jn sszesen az els kett be, t.i. mindegyikb l sak egy{egy, hiszen ha x ssze volna ktve a{val is s b{vel is, akkor abx hromszg lenne. Ez teht eddig az a; b len kvl max. n l. Vgl az n pont maradk grfnak legfeljebb T2 n le van az induk is felttel szerint, hiszen sem tartalmaz hromszget.
=2 ( 2)

( )

2

2

( ) ( 2)

( 2)

e 1 + (n 2) + T2(n 2) = T2(n 2) + n 1 = b(n 2)2=4 + n 1 = b((n2 4n + 4) + (4n = bn2=4 = T2(n)

2

4))=4

(lsd mg a 40.feladatot.) 5.49. Amg a grfban van l, szimmetrizld egy maximlis fok ponthoz a vele ssze nem kttteket, s ismteld ezt a maradk (mg nem szimmetrizlt, de minden korbbival sszekttt) pontok ltal meghatrozott rszgrfra! Amikor az eljrs lell, egy r osztly(!) grfot kapunk (mirt?), melynek lszma legalbb az eredeti e, s legfeljebb Tr n . 5.50. Bizonyts{vzlat: r szerinti teljes induk i; r=2{re mr tudjuk. Az induk is lpsen bell n{re "r-lpsenknti" induk i, mint T2 n {nl. A bels induk is lpsnl ( n r{r l n{re ) egy Kr {b l indulj, ha van. (Ha nin s, hasznld fel az r{re vonatkoz induk is felttelt.) Mskpp fogalmazva ugyanezt a gondolatot: tegyk fel, hogy lenne ellenplda. Vegyl egy olyat, hogy r a lehet legkisebb legyen (azaz kisebb r{re mr semmilyen n{nel nin s ellenplda). Persze erre a minimlis r{re mg tbbfle n{nel is ltezhetnnek ellenpldk. Vegyl ezek kzl egy olyat, ahol n is minimlis; erre a grfra mondd el az r {re ill. 3{ra mr ltott bizonytst.

()

()

=2

123


90

5.52. a) Ha a konvex burok ngyszg, valamelyik szge legalbb Æ . Ha hromszg, Æ. akkor a negyedik s snl keletkez hrom szg kzl valamelyik legalbb b) Ha hrom egy egyenesre esik, akkor a legkisebb tvolsg D= . Ha ltalnos helyzetek, hasznld (a){t s az el z feladatot. 5.53. a) hrom kzl a kzps megfelel. b) Induk i n szerint. Induk is lps: ha van fok pont, hagyd el. Ha ilyen nin s, akkor a) szerint minden pont foka plesz. 5.54. Kss ssze kt pontot, ha tvolsguk nagyobb, mint D= . A 53.feladat szerint e grfban nem lehet teljes ngyszg; alkalmazhatod r a 46.feladat lltst. 5.55. n {ra bn2 = , teht egy D oldal szablyos hromszg s sai megfelelnek. Nagyobb n{ek esetn e hromszg s sai krl egy{egy ; D sugar krvvel a hrom sarokban hrom Æ {os kr ikket jellnk ki, s ezekben osztjuk el a pontokat a lehet legegyenletesebben. 5.56. Egy pontprra legfeljebb kt seresznye illeszkedthet (elemi geometria). Folytats a 41.feladathoz hasonlan. Megjegyzs: Ennl tbb is igaz! n4=3 {os fels be sls mr van [Szemerdi℄. 2 Minden k {ra O n1+1=k {t sejtenek. tG n b n .

1

=3

2

120 2

2

3 =3

0 001

60

(

)

()

4 1 1=0

5.86. Nem. 5.95. Kt pont fa kdja res; mindkt szm {szor fordul el . Tovbb teljes induk ival: az elhagyott els fok pont nyilvn 0{szor fog szerepelni, szomszdjnak (amit lertunk) foka pedig eggyel sokken. 5.99. Ahny klnbz Prfer{kdot kszthetsz az el z feladat megoldsban:

(n 2)! (d1 1)! (d2 1)! . . . (dn 1)! Megoldsok a 6. Fejezethez

=2

sa): Induk io n szerint; n 6.18. (Frank A. bizonyta trivi alis. Ha kevesebb elet hagyunk el, akkor marad xn 2 xn u t is (mert x1 ; x2 ; ; xn 2 ; xn egy max{vissza sorrendja G fxn 1 g{nek) es marad xn 2 xn 1 u t is (mert x1 ; x2 ; ; xn 1 egy max{vissza sorrendja G fxn g{nek). Marad tehat xn 1 xn seta; gy ut is. 6.23. a) Vlaszd azt az x 6 xi i < k {t, amelyre 0i
...

...

=

()

(

)

()

min =

( )+ (

( ) ( )+ ( )

)

124

Elekes Gy: b) Nyilvn vgig krmentes marad, s amikor az eljrs lell, mr sak egy komponense lehet.

) A Kruskal{hoz hasonl be serlssel igazolhat.

Megoldsok a 7. Fejezethez 7.6. Reprezentljuk egy pros grf als pontjaival az n elem halmaz sszes k {ast; a fels kkel a k {eseket. Kssk ssze llel az egymst tartalmazkat! Minden als pont foka n k (ennyiflekppen vehetnk hozz egy elemet); a fels k pedig k (ennyiflekppen hagyhatunk el). Ekkor n k k miatt teljesl a Hall{felttel. 7.7. A feltetel szerint leteznek olyan P123 , P124 , P134 es P234 pontok, hogy Pijk kozos pontja a Ki , Kj es Kk halmazoknak. Ha konvex burkuk negyszog, akkor atloinak metszespontja mind a negy Ki {ben benne lesz; ha h aromsz og, akkor a bele es} o negyedik pont jo; ha szakassza fajul, akkor a ket bels}o b armelyike megfelel. 7.8. n {re az el} oz}o feladat. Tovabb teljes induk i oval n szerint: Adott K1 ; K2 ; ; Kn+1 konvex halmazokhoz de nialjuk a

+1

+1

=4

+1

...

Hi = Ki \ Kn+1

(i = 1; 2; . . . ; n)

ugyan sak konvex halmazokat. H arom Hi kozos resze negy Ki (espedig a megfelel} o index} uek, valamint Kn+1 ) metszete, gy az n eset miatt nem u res. Ebb}ol es az induk i os feltetelb} ol az kovetkezik, hogy

=4

K1 \ K2 \ . . . \ Kn+1 = (K1 \ K2 \ . . . \ Kn ) \ Kn+1 = H1 \ H2 \ . . . \ Hn 6= ;: 7.14. A leghosszabb oldal(ak egyikenek) ket vegpontja kore rt a sugar u kor ok (len se alak u) kozos reszenek egyik fele (ahol a harmadik s u s van)ptartalmazza H {t. sugar u. Kisebb Ennek az velt h aromsz ognek" a kor ulrt kore eppen r a= korbe az a oldal u szabalyos h aromsz og nem fer bele. (Tompasz og} u h aromsz og eseten nem a kor ulrt kor adja a minimumot; a legnagyobb oldal Thalesz{kore kisebb.) 7.20. Az el} oz}o feladat szerint eleg annyit megmutatni, hogy a rossz nylt felskok (felterek) nem fedik az egesz skot (teret); bel atjuk, hogy meg a halmaz konvex burkat (hat araval egy utt ertve) sem fedhetik. Mag at a halmazt nyilv an semelyik d egyestese sem fedi. Helly tetelet a komplementerekre es a | korlatos | konvex burokra (hat araval egy utt ertve) alkalmazva, az osszes rossz nylt felter komplementerenek es a konvex buroknak van kozos pontja; veg ul is ez j o lesz entrumnak. 7.34. Ha a konvex burok ot- vagy negyszog, keszen vagyunk. Ha h aromsz og, akkor a belsejebe es}o ket pontot osszek ot}o egyenes sak ket oldalt metsz; a harmadik oldal ket vegpontja es a bels}ok egy utt jo pontnegyest alkotnak. 7.35. K R4 m; megfelel; ha ennyi pont negyelem}u reszhalmazait pirosra ill. kekre sznezz uk aszerint, hogy a pontnegyes konvex-e vagy konk av, a 34. feladat

=

+1

=

( 5)

3

125


alapj an nem lehet ot pont minden negyese kek. Ramsey tetele szerint van teh at

7.38.

m pont, melyek minden negyese piros. Ezek konvex m{szoget alkotnak. Kett} os induk i o k {ra es l{re. Ha k = 3 vagy l = 3, akkor egy l 1 pont u konk av (ill. k 1 pont u konvex) v megfelel. Ha mindkett} o nagyobb, akkor k + (l 1) 4 tegyel egymas melle egy konvex k {as es konk av l 1{es nelk uli k 2 ( k 1) + l 4 pont u es egy konvex k 1{es es konk av l{es nelk uli (k 1) 2 pontu

halmazt u gy, hogy az el} obbi balra fent", az utobbi jobbra lent" legyen olyan nagy szintk ulonbseggel, hogy a ket halmaz egy-egy pontj at osszek ot}o szakaszok mind meredekebbek legyenek az egy{egy halmazon bel uli pontparok osszek ot}o szakaszainal. 7.41. (i) azert igaz, mert az e Pi Pj elt tekintve vagy az ha e ; b e i, vagy egy n ala is jobb szampar benne van ugyan Hi {ben, megsem szerepelhet sem } o, sem n ala jobb Hj {ben. Ugyanis b armely Pj {b}ol indul o f elre

=

7.42.

() ()

a(e) a(f ) + 1; ha w(e) w(f ); b(e) b(f ) + 1; ha w(e) w(f ): (ii) Nagyobb a{hoz kisebb b tartozik a p arok maximalit asa miatt. Ha legfeljebb k 2 tag u n ov} o es l 2 tag u sokken}o ellan lenne, akkor minden a(e) az 1; 2; . . . ; k 2 es minden b(e) az 1; 2; . . . ; l 2 halmazbol kerulne ki. A pontosan t szampart tartalmazo Hi {k sz ama teh at az el} oz}o feladat (ii) resze l 2 k 2 alapj an legfeljebb t t lehetne. Ezeket osszegezve az osszes lehetseges k + l 4 t{re, sak k 2 adodna a pontszamra.

7.44. Pldul

7.48. 7.49. 7.64. 7.73. 7.77.

7 1 2 7 3 4 7 5 6 2 4 6 1 3 6 2 3 5 1 4 5 Vegyl egy ltalnos helyzet pontngyest s hasznld az el z feladatot! (iii){ hoz tekints egy pontot s az sszes, t tartalmaz egyenest! b) q elemek s q 3 =q q2 q darab van.

) q {re ez ppen egy{egy elemet jelent ekvivalen ia{osztlyonknt; q { ra viszont az osztlyok prok. p2n p2n(p2n 1) 2n p2n n p n < n, teht a pontok ltal meghat2 2 2 2 rozott egyenesek nem fedhetik az alaphalmazt. Brmely k n{re a k elem rszek megfelelnek. Ezekb l k b n2 {re ill. n n k d 2 e{re (pros n esetn 2 {re) van a legtbb. Tbbet lehet-e? Lsd ks bb Sperner ttelt! Mivel k n k n = nk , ezrt nk {t kell maximalizlni. Ez a binomilis egytthat pedig akkor a legnagyobb, ha k b n2 ill. k d n2 e (pros n esetn n) 2

=

1 =2

(

=

=

1) (

1) = + + 1

=3

=

0

! (

=

)! = !

=

=

126

Elekes Gy:

2 1

7.78. A 6. feladat szerint az bn= elem halmazokhoz prosthatsz egy{egy, ket tartalmaz bn= elemt; az bn= {esekhez b vebb bn= {eseket; stb. n= esetn lehet az sszeset; k n= {re pedig pldul az sszes olyat, amely az utols elemet tartalmazza: nk 11 darabot. Tbbet lehet-e? Lsd az Erd s{Ko{Rado ttelt. 7.85. k > n= {re az sszes, (i){et teljest rsz j; ez n darab. k esetn legfeljebb k darabot lehet. Az fi; i ; ; i k g (mod n) halmazba ugyan n hasonl alak msik metsz bele, de ezek kzl a fj k; j k ; ;j g (mod n) s fj; j ; ; j k g (mod n) tpus prokbl (ii) miatt sak az egyik szerepelhet. Ez k k. 7.86. Szemlletesen: brmilyen sorrendben helyezzk is el az n elemet egy szablyos n{szg s saiba, a 85. feladat szerint a keletkez n darab, szomszdos s sokbl ll k {as kzl sak k darab szerepelhet az Ai {k kztt, azaz legfeljebb k {ed rszk.
2

2

...

2 2 2 + +1

2

2+

2!

2!

1

2!

2!

2!

2 +1

!

2!

2

2

2

=

2

2

2

2

2( + 1 ...

1) 1

2

2

+1 ... + +1 ... + 1 1 + ( 1) =

2

1

=

!

! ! (

)!

(

!

=0

=0

)!


127

tehetjk fel, mert a Gauss{elimin i ilyeneket ad.) A kzs nevez vel Pvgigszorozva s a legnagyobb kzs osztval osztva lesz pratlan j . Ekkor i vi vj , s a bal oldalon sok pros mellett egyetlen pratlan tag ll | ellentmonds. 7.98. a) Az el z feladatban mr hasznltuk, hogy ha R felett van nem-trivilis lineris kombin i, akkor van supa ra ionis is, teht supa egsz is. Ami pedig egsz szmknt 0{t ad, az mod 2 is.

0

=

128

Elekes Gy:

129


nlott irodalom Aja

Bevezet}o

Andr asfai Bela: Grafelmelet. Polygon konyvtar, 1997. Hajnal Peter: Grafelmelet. Polygon jegyzett ar, 1997. Hajnal Peter: Elemi kombinatorikai feladatok. Polygon konyvtar, 1997. Hajnal Peter: Osszesz aml al asi problem ak. Polygon jegyzett ar, 1997.

Algoritmusok

R onyai Lajos{Ivanyos G abor{Szabo Reka: Algoritmusok. TypoTEX Kiad o, 1998. (Kit} un} o bevezet}o) Cormen{Leiserson{Rivest: Algoritmusok. (Monogra a) M} uszaki K onyvkiad o, 1997.

Linearis algebrai modszerek { sok geometriaval.

L aszl o Babai { Peter Frankl: Linear Algebra Methods ... (Meg nem jelent meg; fenymasolva terjed.)

Mely eredmenyek, feladatok formajaban

Lovasz L aszl o: Kombinatorikai problem ak es feladatok. TypoTEX Kiad o, 1999. (A veges matematika legnevezetesebb | es legjobb | monogr a aja.)

Kezikonyv

Handbook of ombinatori s. Edited by R. L. Graham, M. Grots hel and L. Lovasz. Elsevier S ien e B.V., Amsterdam; MIT Press, Cambridge, MA, 1995.

¾ Ð Ý

Recommend Documents