Sokszínű Matematika 11 Megoldások

= 1024, tehát 1023 mérkõzésre van szükség. n = 2 765 289, tehát 2 765 288 mérkõzésre van szükség. A második legjobb kiválasztása nehezebb probléma. Feltesszük, hogy játékosainknak van egy erõsorrendje, és mindig az erõsebb nyer. (Ez a „valódi” sportban nincs mindig így) 18 A második „legerõsebb” versenyzõ kiválasztását a valódi sportesemények rendezõi nem vállalják, hanem az utolsó mérkõzést döntõnek nevezik és a vesztest tekintik a második legjobbnak. Azt, hogy a két legerõsebb versenyzõ az elsõ mérkõzésen találkozzon, azt elõzetes erõsorrendek alapján megtervezett tornákkal küszöbölik ki. A második legerõsebb versenyzõ azok közül kerülhet ki, akik csak a legerõsebbtõl kaptak ki. Így kell egy tornát rendezni a legerõsebb kiválasztására, majd egy külön tornát azok számára, akiket a legerõsebb gyõzött le. 6. a) Igaz, ha legalább 2 pont van b) Hamis . c) Hamis, ha legalább 2 pont van. d) Hamis,

Sokszínû matematika 11. A KITÛZÖTT FELADATOK EREDMÉNYE

3 Tartalom Kombinatorika, gráfok. Hatván, gök, logaritmus. A trigonometria alkalmazásai. 9 Függvének. Koordinátageometria. Valószínûségszámítás, statisztika.

4 Kombinatorika, gráfok. Fibonacci-számok SOKSZÍNÛ MATEMATIKA A KITÛZÖTT FELADATOK EREDMÉNYE. Legen a n az n-edik lécsõfokra való feljutások száma. a =, a =, a =, a =, a 7 =. Ha az n-edik lécsõfokra léünk, akkor az utolsó léésünk lehetett eglécsõs, illetve kétlécsõs. Ez alaján a n = a n + a n. Ebbõl adódik, hog a n = f n+.. Legen b n az n szintes ház kifestéseinek száma. a) b = ; b) b = ; c) b =. Ha n szintes a ház (n > ), akkor két egmást kizáró lehetõség elõtt állunk: ) tetszõlegesen kifestjük az alsó n szintet, majd eg kék szint jön, és legfelül fehér szint lesz; ) tetszõlegesen kifestjük az alsó n szintet, és a legfelsõ szint kék színt ka. Ez alaján b n = b n + b n. Ebbõl adódik, hog b n = f n+. Rejtvén: A hiba a bal oldali kéen van. A kérõl úg tûnik, hog a iros háromszög átfogója és a traéz egik oldala kiadja az összerakott téglala egik átlóját. Ez azonban nem igaz. Számoljuk ki a két szakasz meredekségét! A bal oldali kéen látható 9 összterületû nég alakzat az átló körnékén eg kicsinke részt többszörösen fed.. Permutációk, variációk. a)! = ; b)!! =, mert arra, hog Bea és Cili egmás mellé üljön,! féle lehetõség van. A kerek asztal esetén elõször is értelmezni kell, hog mikor tekintünk két leülést különbözõnek. Több lehetõség van. Ha a nég ozíciót (széket) megkülönböztethetõnek gondoljuk, akkor bármel két ültetést is meg tudunk különböztetni, amikor valaki különbözõ székre kerül. Ekkor teljesen új ültetést kaunk, ha mindenki eggel balra átül. A második lehetõség, hog mindenki megjegzi, ki ül tõle balra és jobbra. Ha ez az információ két ültetés esetén különbözik, akkor a két ültetést különbözõeknek tekintjük. Ekkor ha mindenki eggel balra átül, akkor az új ültetést nem tekintjük az elõzõtõl különbözõnek. Ha viszont eg ültetést tükrön keresztül nézünk (legalább három résztvevõ esetén), akkor más ültetéshez jutunk, mert a jobb és bal szomszédság felcserélõdik. A harmadik lehetõség, hog mindenki csak annit jegez meg, hog kik között ül. (Tehát éldául Anna annit jegez meg, hog Bea és Cili között ül, de nem tudjuk meg, hog ki ül a balján és ki a jobbján.) Ekkor eg ültetés tükörkéét nem tekintjük új ültetésnek. A megoldásban mi a közésõ megállaodással élünk, azaz az elforgatott ülésrendet nem tekintjük különbözõnek, de a tükörkéet igen. c) Megkérjük Annát, hog sorolja fel, ki ült a jobbján és annak a jobbján, illetve ki ül a balján. (A körszerû ülésrendet felvágjuk Annánál, íg a másik három résztvevõ közt eg sorrendet kaunk.) Ez ontosan leírja az ülésrendet. Összesen! = lehetõség van. d) Beának és Cilinek szemben kell ülni. Két lehetõség van aszerint, hog Anna Bea jobbjára vag baljára ül.

5 . Minden jegre lehetõség van, íg féle négjegû szám lehet. Minden heli értéken mind a számjeg -szor fordul elõ, íg az összeg ( ) + ( ) + ( ) + ( ) = = = db.. 0 = ozitív osztói a a b c alakú számok, ahol a Î, b Î és c Î. Ez lehetõség. 00-nak, -nek edig darab ozitív osztója van.. A jó elhelezésnél a básták különbözõ sorba és különbözõ oszloba esnek, azaz minden sorban eg básta áll (és minden oszloban is). Az elsõ sor bástája nolc helen állhat. Ezek után a második sor bástája már csak hét ozíciót foglalhat el és íg tovább. Összesen 7. = 00 lehetõség van db.. Az eges jegekre a lehetõségek száma ; ; ; ; ;. Íg a számra = lehetõség van. 9. a) = ; b) + = ; c) + = 9; d) legalább beteg kell. 0. a) = 00; b) A tankönv. kiadásában: Csoortosítsuk a megszámlálandó számokat utolsó nég számjegük szerint. Erre a nég számjegre 0 lehetõség van. Ezek közül 9 nem tartalmazza a -as számjeget, 0 9 darab tartalmazza a -as számjeget. Ezen utóbbi lehetõségek közül bármelikhez három összeszámlálandó szám tartozik, hiszen az <. 7,, 9>számjegek közül kell eg elsõt kiválasztani, és már csak a -mal való oszthatóságra kell ügelnünk. A 9 kiterjesztés közül ontosan három lesz jó. Ez (0 9 ) lehetõség. A9 darab -ast nem tartalmazó végzõdés között lesznek -mal oszthatók és -mal nem oszthatók. A hárommal oszthatók -mal, -tal vag 9-cel kezdve maradnak -mal oszthatók. Ahhoz, hog a -as számjeget is tartalmazzák, ahhoz a -as számjeget kell a kezdetnél használnunk. Minden ilen végzõdés eg összeszámlálandó számot ad. A -mal nem osztható végzõdések nem adnak összeszámlálandó számot (ebben az esetben a -as számjeg felhasználása és a -mal való oszthatóság nem összeegeztethetõ). A megoldás befejezéseként belátjuk, hog a 9 darab végzõdés közül ontosan / 9 = = 9 darab lesz -mal osztható. Ehhez a -ast nem tartalmazó végzõdéseket utolsó három számjegük szerint csoortosítjuk. Ezek mindegike a eg elemével kezdhetõ, amel kilenc lehetõség közül ontosan három vezet -mal osztható eredménhez. Íg a válasz: (0 9 ) + 9.

6 SOKSZÍNÛ MATEMATIKA A KITÛZÖTT FELADATOK EREDMÉNYE A. kiadástól: Inkább azt számoljuk össze, amelik nem tartalmazza a -as számjeget. Ezek száma 9. Összesen 9 0 darab ötjegû ozitív egész szám van a tízes számrendszerben. Tehát = 7 darab ötjegû szám tartalmazza a -as számjeget. Rejtvén: Igen, megszabadulhatnak. A feladatnak két változata van: tudják, hog megérkezésükkor milen állaotban van a láma, illetve nem tudják. Az elsõ változat (amikor feltesszük, hog leoltott lámához érkeznek a rabok) eg kicsit könnebb. Ezzel kezdjük. A rabok kijelölnek maguk közül eg számlálót, aki információt gûjt és aki az összes rab sétáltatását be fogja jelenteni. Az összes többi (99) rab feladata, hog elküldje azt az információt, hog volt már sétálni. Ehhez mindegikük a következõt teszi: Az elsõ alkalommal, amikor sétálni meg és a láma nem ég, akkor felgújtja a lámát. A felgújtott láma lesz az üzenet, hog õ már volt sétálni. A további sétálásoknál a leoltott lámát úg hagja (csak egszer küld üzenetet). Ha a sétáltatásnál felgújtott lámát lát, akkor úg hagja. (Tudja uganis, hog ez eg üzenet, amelet nem szabad megzavarni.) Ha a számlálónak kinevezett rab felgújtott lámát lát, akkor leoltja (jelzi a többieknek, hog újból várja az üzeneteket), és megjegzi, hog eg rab jelzett neki. Amikor 99-szer leoltotta a lámát (99 rab eg-eg üzenete eljutott hozzá), akkor bejelenti, hog mindenki sétált. Ha a rabok nem ismerik a láma kezdeti állaotát, akkor a fenti megállaodás nem lesz jó. A számláló a 99-edik lámaoltás után nem tudja, hog 99 üzenetet kaott-e, vag edig egszer leoltotta a kezdetben égõ lámát, és csak 9 üzenet jutott el hozzá. Ebben az esetben abban állodhatnak meg, hog a számlálón kívül minden rab kétszer üzenjen. Azaz az elsõ két olan sétáján, amikor leoltott lámával találkozott, gújtsa fel azt. (Elõfordulhat, hog a raboskodása során az 000-edik és edik sétája.) Máskor ne tegen semmit. A számláló 9 lámaleoltás után jelezzen. Ekkor sem tudja megkülönböztetni azt a két esetet, amikor 9 üzenetet kaott, illetve eg kezdeti lámaoltás után csak 97 üzenetet gûjtött össze. Abban azonban biztos lehet, hog mind a 99 rabtársától kaott jelzést a sétálásról.. Ismétlés nélküli kombinációk, Pascal-háromszög. a) 0 00 =. b) A iros hetes mellé választunk még 7 laot. 7 = 9 7 c) Az összes lehetõségbõl kivonjuk azok számát, amelekben nincs iros.. háromszög van, ezek közül különbözõ. = =. 0 7 =.. Maimum metszésont lehet. =

7 . Egeneseinket egesével rakjuk le az üres síkra. Kezdetben eg részbõl áll a sík, majd minden egenes új síkrészeket alkot a korábbiak szétvágásával. Minden új egenesnél számoljuk össze, hog legfeljebb hán új síkrészt alakít ki: + ( ) =. Enni síkrész ki is alakul, ha egeneseink között nincsenek árhuzamosak, és nincs három olan, amel közös onton halad át.. a) 70 -féle út. léésbõl db jobbra = léést választunk. b) Minden csúcshoz odaírjuk, hánfélekéen juthatunk oda. Ez összesen -féle út. c) -féle út. b) A A B B c) A bal felsõ M-tõl kell indulnunk, és léést kell megtennünk. Minden léésben lehetõségünk van. Tehát a hó -félekéen olvasható le. 9. A testátlók számolásához összeszámoljuk a csúcsok által meghatározott szakaszokat. Ezek tartalmazzák a test éleit, a laok átlóit és a testátlókat. A többletet levonjuk a csúcsárok számából. 0 a) A dodekaédernek = 0 csúcsa van. Ezeket -félekéen köthetjük össze. 0 Ezek közül = 0 él, az ötszöglaokon edig laátló van. Íg összesen testátló van. = 0 b) Az ikozaédernek = csúcsa és = 0 éle van. A háromszöglaoknak nincsenek átlói. Íg az ikozaéder 0 testátlója van. = 7

8 SOKSZÍNÛ MATEMATIKA A KITÛZÖTT FELADATOK EREDMÉNYE 0. k db csaat szereel, k k az összes meccsek száma, hátra van k meccs, és már megtartottak 77 meccset, íg k k + 77 =, innen k =. Tehát csaat szereel.. a) A legkevesebb forduló esetén háromszor kell személlel felmennie a liftnek. Az elsõ két lift utasait kell kiválasztanunk (a harmadik liftben a kimaradtak utaznak). Ez lehetõség. 0 = b) A legkevesebb fordulóhoz négszer meg fel a lift. Egszer három, a többi esetben edig nég emberrel. Nég lehetõséget különböztetünk meg aszerint, hog melik fordulóban lesz a hármas utazás. Mindegik esetet az elõzõ rész alaján számolhatjuk ki. A válasz: Szorozzuk össze az eges embereknek való osztások lehetõségeinek számát: Minden keresztezõdõ kézfogásban nég ember vesz részt, és az emberek közül bármel nég esetén ontosan eg keresztezõdõ kézfogás lesz. Íg a keresztezõdõ kézfogások száma azonos a 0 emberbõl kiválasztható négesek számával, azaz 0 0 = -zel.. Binomiális egütthatók, ismétléses kombináció. a) b) 0 n + n + n + n + n c) n n n n d) a n a n b a n b n ( ) n b n. a) ( ) ; b) (a +).. A feladat nem szól arról, hog ki az a Péter. Ezt a megoldás elõtt tisztázni kell. A legegszerûbb megállaodás, hog a csaatnak egetlen tagját hívják Péternek. Más megállaodás lehet az is, hog egik tagot sem hívják Péternek (l. nõi csaatról van szó). Az is elkézelhetõ, hog olan férfi csaatról van szó, amelben mindegik játékosnak Péter a keresztneve. Ezek a megállaodások természetesen mind más-más feladathoz vezetnek. Mi a legegszerûbb megállaodással élünk. a) = ; b) = ; c) =.

9 . ( + 7)! = ! 7! Analóg feladat: golót helezünk el rekeszben. A golót és a 7 rekeszfalat ermutáljuk úg, hog sem a golókat, sem a falakat nem tudjuk megkülönböztetni egmástól. Lásd a. élda megoldását.. a) Minden megoldáshoz rakjunk le darab + jelet, majd eg elválasztójelet, azután darab + jelet, ismét eg elválasztójelet, s végül z darab + jelet. Íg jellel leírtunk eg megoldást (ahog leírtunk eg növénrendelést a. éldában). A megoldások száma =. b) Az + + z = 9 egenlet ekvivalens az ( ) + ( ) + (z ) = egenlettel. Az + + z = 9 egenlet megoldása a ozitív egészek körében ekvivalens az ‘ + ‘ + z’ = egenlet megoldásával a természetes számok körében. Ebbõl adódik a két egenlet megoldásszámának azonossága. A második egenletnek az a) ont megoldási módszerével megoldása van. = c) Végtelen sok, minden (; ; 9 ), ÎZ alakú számhármas.. Veges összeszámlálási feladatok (kiegészítõ anag). lán és fiú, íg + =, + + = +. Tehát lán és 0 fiú tanuló volt.. A második, harmadik és negedik tulajdonságoknak minden (m) (m ÎZ + ; m ¹ ) alakú szám megfelel, és ezek nem kétjegûek és nem rímek. Végtelen sok ilen szám van.. = -félekéen.. Elõször se a tigrisek, se az oroszlánok között ne tegünk különbséget. Legen n db oroszlán és k db tigris. Állítsuk sorba a tigriseket, és tegünk közéjük – oroszlánt. Íg n (k ) db oroszlán marad, meleket ezek után a tigrisekhez kéest róbálunk elhelezni. Ezt ( k+ n ( k ))! -félekéen k!( n ( k ))! tehetjük meg. Mivel az állatok különbözõek, szorzunk k!-sal, ill. n!-sal. A sorbaállítások száma tehát ( k+ n k+ )! ( n+ )! n! n! k! = k!( n k+ )! ( n k+ ). oroszlán és tigris esetén = 00 lehetõség van.! 9

10 SOKSZÍNÛ MATEMATIKA A KITÛZÖTT FELADATOK EREDMÉNYE Más megoldás: Kézeljük el, hog az idomár elõször az oroszlánokat helezi el, majd a tigriseket illeszti az oroszlánok közé. Íg elõször az öt oroszlánt állítja sorba (! = 0 lehetõség). Ezek meghatároznak hat (oroszlánokhoz viszonított) ozíciót: legelsõ hel, nég darab köz és legutolsó hel. Két tigris az oroszlánokhoz kéest nem kerülhet uganoda, mert akkor egmás mellett állnának. A hat ozícióból ki kell választanunk azt a néget ( = lehetõség), ahová tigris kerül, majd a kiválasztott helekre el kell heleznünk a tigriseket (! = lehetõség). Összesen 0 = 00 lehetõség van. A megoldás menetébõl (is) következik, hog nincs megoldás, ha a tigrisek száma nagobb, n + mint az oroszlánok száma. Ha k n +, akkor az általánosítás egszerû: n! k!. k. Elõször ne legen különbség a iros és a kék golók között. Tegük le a fehér golót, majd rakjunk közéjük – golót. A megmaradt golót kell elheleznünk a lehetséges helen, majd ki kell választanunk, hog melik kettõ legen kék. Tehát ( + )! 7 7. = Más megoldás: Elõször rakjuk le a iros és kék golókat. ( 7 lehetõség, hiszen a hét goló sorában = a két kék goló helét kell kiválasztanunk.) A lerakott hét golóhoz viszonítva kialakuló nolc ozíció egikébe sem eshet több fehér goló. Íg a fehérek elhelezéséhez a nolc ozícióból ki kell választanunk azt a hármat, ahová a fehér golók kerülnek ( = lehetõség). Ez összesen = 7 lehetõség.. a) 0 ( 0 + )! ( 7 + )!. (Minden almánál lehetõség.) b) =. c) = 7. 0!! 7!! d) Ha n gerek és k különbözõ alma van, akkor n k lehetõség van a szétosztásra. Ha n gerek és k megkülönböztethetetlen alma van, akkor edig n+ k lehetõség van n a szétosztásra. Ha ráadásul mindegik gereknek akarunk almát adni (tegük fel, hog k ³ n), akkor osszunk ki n almát, majd a maradék k n almát osszuk szét tetszõlegesen. Íg k lehetõség van. n 7. Legen a maimális tartománszám a n, ahán tartománra n darab kör felvágja a síkot. A kis araméterek vizsgálata egszerû: a =, a =, a =, a =, a =. Ha n darab kör mellé rakunk eg új (n + -edik) kört, akkor ezt a korábbi körök mindegike legfeljebb két ontban metszi. Ez a legfeljebb n metszésont legfeljebb n ívet alakít ki az új körön. Ezek az ívek korábbi tartománokat vágnak ketté. A szétvágott tartománok száma lesz a többlet a korábbi tartománszámhoz viszonítva. Ez alaján a n+ a n +n, sõt egenlõség áll fenn: a n+ = a n +n. Íg a n = (n ) = n n +. Vessük össze a.. feladattal és annak megoldásával. 0

11 . a) Minden csúcs azonos színû db színezés; b) ont más színû db; c) ont db; d) ont db; e) ont 7 db. Összesen eset van. 9. a) A tízszög csúcsai 0 szakaszt határoznak meg. Ezek közül 0 a sokszög oldala, = a maradék 0 = darab edig a tízszög átlója. b) Minden átlómetszéshez tartozik nég csúcs (a metszõ átlók végontjai), és minden csúcsnégeshez tartozik ontosan eg átlómetszés (a nég közül a kerületi sorrendben szemköztes elemek által meghatározott átlók metszése). Ha minden csúcsnéges különbözõ átlómetszést határoz meg (ez lehetséges), akkor 0 átlómetszés alakul ki. Ennél több nem lehetséges. Vessük össze ezt a feladatot a.. feladattal és annak megoldásával! c) A legtöbb tartomán akkor alakul ki, ha nincs három eg onton átmenõ átló. Sokszögünket helezzük a koordinátasíkra úg, hog egik oldal és egik átló se legen vízszintes. A kialakuló tartománokat két csoortba osztjuk: az egikbe azok tartoznak, amelek legalsó csúcsa a sokszögnek nem csúcsai, a másikba azok, amelek legalsó csúcsa a sokszög egik csúcsa. Az elsõ tíusú tartománok legalsó csúcsa két átló metszésontja. Megfordítva: minden átlók által kialakított metszésonthoz tartozik eg elsõ tíusú tartomán, amelnek ez a metszésont a legalsó ontja. Íg az elsõ tíusú tartománból ugananni van, mint ahán metszésont az átlók között: esetünkben 0 = 0. A második tíusú tartománok összeszámolásához csoortosítsuk õket a legalsó csúcsuk szerint. Fussunk végig a legfelsõ csúcson kívüli kilenc csúcson. Mindegik csúcsnál a hozzá fentrõl befutó átlók és oldalak számából -et levonva kajuk meg az oda tartozó második tíusú tartománokat. Ezeknek a számoknak az összege az összes átló és oldal számából levonva 9, azaz 0 9 Ez a második tíusú =. tartománok száma. Összesen 0 + = tartomán van. n d) n-szög esetén összesen n átló van, az átlók közötti metszésontok száma legfel- jebb n a kialakuló tartománok száma legfeljebb, n n n + ( ). Rejtvén: A zsinórokat nevezzük el balról jobbra haladva, és -nak. Eg lövési sorrendhez elég tudnunk, hog melik zsinórról lövünk, hiszen mindig az aktuálisan legalsó léggömb a cél. Íg eg lelövési sorrend lehet éldául:. Általában eg lelövési sorrend eg olan hat hosszú sorozat, amelben három darab -es, két -es és eg -as szereel. Ilenbõl 0 0 van. = =

12 SOKSZÍNÛ MATEMATIKA A KITÛZÖTT FELADATOK EREDMÉNYE. GRÁFOK ontok, élek, fokszám. Nincs, mert eg gráf áratlan fokszámú ontjainak száma áros.. a) Szabálos tetraéder. b) Élek száma: e = Z nem lehetséges. 7 d) e = Z nem lehetséges. c) Két azonos élhosszúságú tetraéder összeillesztve eg laja mentén. e) Szabálos oktaéder.. Legenek eg gráf ontjai az ötszöglaok és a hatszöglaok, az élei edig jelentsék a szomszédságot. Az ötszöglaok fokszáma, a hatszöglaoké. Az ötszöglahoz illeszkedõ élek száma = 0. Minden ilen él eg ötszöglahoz és eg hatszöglahoz illeszkedik, és eg hatszöglahoz ilen él illeszkedik. 0 Íg a hatszöglaok száma: = 0.. Legenek a városok eg gráf ontjai, a járatok edig az élek. a) II. Ha a londoni járat Budaestre meg, akkor a másik két járatot Budaestrõl háromfélekéen választhatjuk. L L L P P P A A A B B B M M M II. Ha a londoni járat nem Budaestre meg, akkor ez háromfélekéen valósulhat meg. L L L P P P A A A B B B M M M b) Ez nem lehetséges, mert a áratlan fokszámú ontok száma nem lehet áratlan. c) Ha eg ontú egszerû gráfban db fokszámú ont van, akkor a többi ontnak legalább a fokszáma, íg ez az eset sem lehetséges.. Legenek eg gráf ontjai a városok, az élek edig a városokat összekötõ útvonalak. Ha a gráf összefüggõ, akkor bármel városból el lehet jutni a fõvárosba. Ha nem összefüggõ, akkor tekintsük a fõvárost tartalmazó komonenst. Ebben a komonensben kell még eg áratlan fokszámú ont, mivel eg komonens áratlan fokszámú ontjainak száma csak áros lehet. Tehát Messziút is ehhez a komonenshez tartozik, hiszen a többi város áros fokszámú. Ekkor is el lehet jutni a fõvárosba Messziútból.

13 7. a) A b) ont seciális esete. b) Ha van 0 fokú csúcs, akkor a fokszámok a halmaz elemei (azaz ilenkor nem lehet n fokú csúcs). Ha nincs 0 fokú csúcs, akkor a fokszámok a <. n, n >halmaz elemei. Mindkét esetben az n fokszámra n lehetõség van, íg lesz egbeesés köztük.. Legenek a résztvevõk eg gráf ontjai, az osztáltársi kacsolatok edig az élei. Az osztáltársak eg teljes gráfot alkotó komonens tagjai. Akik -ot mondtak, azok eg 7 ontú teljes gráfhoz tartoznak. Mivel ilen válasz volt, legalább két ilen komonens van, tehát legalább hat -os válasz hiánzik. Akik -et mondtak, azok eg ontú teljes gráf tagjai. Mivel 7 ilen válasz volt, legalább két ilen komonens van, tehát legalább három -es válasz hiánzik. Akik -at mondtak, azok eg ontú teljes gráf tagjai. Mivel ilen válasz volt, legalább két ilen komonens van, tehát ilen válasz hiánzik. Akik -t mondtak, azok eg ontú teljes gráf tagjai. Mivel ilen válasz volt, legalább ilen válasz hiánzik. Íg megkatuk a hiánzó választ. 9. () Þ () a nagvadak szimatikusak Þ () a nagvadaknak nincs agaruk Þ () a nagvadak nem kellõen felfegverzettek Þ () a nagvadak nem elefántok Þ () bemehetnek a orcelánboltba. Igen, következik. 0. Legenek a bálon részt vevõ diákok eg gráf ontjai, és az él jelezze, hog ki kivel táncolt. Ha minden él eg fiú és eg lán között húzható meg, akkor a fiúk fokszámának összege és a lánok fokszámának összege egenlõ kell, hog legen. Ha évfolamonként a fiúk és a lánok száma egenlõ, akkor a fiúkra és a lánokra vonatkozó iskolai átlagnak egenlõnek kell lennie, de ez a diagram alaján nem teljesül. Íg vag az adatfelvételkor nem emlékeztek jól, hog hán emberrel táncoltak, vag a fiúk nem csak (az iskolabeli) lánokkal táncoltak, vag a fiúk nem csak lánokkal táncoltak.. Jelöljük a ontot rendre u, v, w. z-vel Elõször azt látjuk be, hog van eg egszínû háromszög. Tekintsük a v csúcsot és az ebbõl induló öt élt. A színek szimmetriája miatt feltehetõ, hog színeik közt a iros van többségben. A legalább három iros él elvezet v három iros szomszédjához. Ha ezek között van iros él, akkor ennek két végontjához v-t hozzávéve eg olan hármast kaunk, ameleket összekötõ mindegik él iros. Ha a három ontot összekötõ élek között nincs iros él, akkor olan háromszöghöz jutottunk, amelnek minden éle kék. A második egszínû háromszög keresésénél induljunk ki eg z egszínû (feltehetjük, hog kék) háromszögbõl. Legen v eg negedik csúcs. Ha a v-bõl az -hez, -hoz és z- hez vezetõ három él nem mind iros, akkor az elõzõ bekezdés gondolatmenete eg olan egszínû háromszöghöz vezet, amel a kiindulási háromszöghöz kéest új, és már készen is vagunk. Ha mindhárom él iros, és ugancsak ez teljesül a maradék u és w két csúcsra, akkor az u, v és w közti éleket nézzük meg. Ha mindhárom él kék, készen vagunk. Ha valamelik él iros, akkor is megtaláljuk az új egszínû háromszöget, ha a iros él két végontjához -et (vag -t vag z-t) hozzáadjuk.

14 SOKSZÍNÛ MATEMATIKA A KITÛZÖTT FELADATOK EREDMÉNYE. a) Az elõzõ feladat alaján, ha eg csúcsból azonos színû él futna ki, akkor ott egszínû háromszög keletkezne. b) Ha a gráfból töröljük a iros éleket, akkor a gráf összefüggõ, és minden ontjának a fokszáma. Tehát van a gráfban zárt Euler-vonal. E A B D C. Legenek a tudósok eg gráf ontjai, és az élek jelezzék, ha leveleznek. Az élek színe jelentse a témát. A skatulaelv szerint eg tudóstól legalább azonos színû (iros) él indul. Ha ezt a ontot összekötõ élek mindegike a másik két színbõl való, akkor az elõzõ feladat alaján van egszínû háromszög. Ha legalább az egik él iros, akkor is van egszínû háromszög.. Ha a csónakból való kiszállás után valamelik onton több a misszionárius, akkor a túlarton több a kannibál, és baj van. Ha eg kiegenlített helzet elõtt a csónakban több a kannibál, akkor az indulási oldalon volt baj, ha edig kevesebb, akkor az érkezési oldalon volt baj. Tehát a csónakban eg kannibál és eg misszionárius lehet csak, íg edig nem lehet átjutni. Más megoldás: Vegük azt a feltételezett legelsõ illanatot, amikor a csónaknak a jobb artra való visszatérése után a bal arton legalább két misszionárius van. Mivel a másik arton is kell misszionáriusnak lenni, ezért biztos, hog ekkor mindkét arton ugananni a kannibálok és a misszionáriusok száma (- és -, vag -, és -). A -, – eset nem lehet, mert akkor (mivel a legelsõ olan esetet néztük, amikor legalább misszionárius van itt) ezt megelõzõen a bal artra két misszionáriusnak kellett volna érkeznie. Akkor viszont elõtte az ott lévõ misszionárius kisebbségben lett volna. A -, – eset azért nem lehet, mert akkor ezt megelõzõen a jobb artra (az egensúli robléma miatt) csak olan csónak térhetett volna vissza (illetve ettõl kezdve a két art között csak olan csónak közlekedhet), amelben se misszionáriusból, se kannibálból nem ülhet több. Íg azonban nem lehet átkelni a folón. Ellentmondásra jutottunk, a feladatnak nincs megoldása.. A kannibál átevez, majd visszahozza a csónakot. A misszionárius átevez, majd kannibál visszameg a társáért.. Legenek a diákok eg gráf ontjai, és iránított él mutasson arra, akibe szerelmesek. Fiúk: A, B, C, D. Lánok: E, F, G, H. A feladat feltételei szerint minden ontból eg él fut ki, és minden ontba eg él fut be. Íg minden ont fokú, és íg van olan kör a gráfban, melen a fiúk és a lánok felváltva követik egmást. Mivel a szerelem nem lehet kölcsönös, nincs két ontú kör. Tehát vag két ontú van, vag eg ontú. (*) A feltételek: () A X Y E X Î; Y Î () B X Y F X Î; Y Î X ¹ X Ü Y ¹ Y () C X D () X ¹ G Þ X = E vag X = H () H Y X X ¹ GY ¹ A

15 I. Ha X = H Þ Y = Y és X = F és Y ¹ B A X Y E X Î B H Y F Y Î C X D Ha Y = D Þ X = H ß Ha Y = C Þ F = X Þ X = G Y ¹ C Þ Y = D B H C F D II. Ha X = E Þ Y = B Þ ontú kör van. A X B E X X D F C Ü () Ý Ý () () () Þ X ¹ H ß X = G Þ X = H Aladár Hannába szerelmes. Más megoldás: (*)-ig uganaz, majd a feltételekbõl következõen A és E, B és F, továbbá C és D eg-eg körben van. Elõször kizárjuk azt, hog két nég hosszú körünk van (amelekben két csúcs lánnak, két csúcs fiúnak felel meg). Tegük fel, hog mégis kialakul ez a helzet. Ekkor C és D eg kör fiúi, íg a másik körben szerelõ fiúk A és B, ahol a két lán E és F. Azaz H és G eg nég hosszú körre esik. De ekkor az a fiú, akit Hanna szeret, az Grétát szeretné, ami edig kizárt. A nolc hosszú kör esetében haladjunk végig a körön, és nézzük a fiúk sorrendjét. Feltételeink szerint C után D jön, majd A és B következik valamilen sorrendben. A két eset egszerûen analizálható, és azt kajuk, hog csak az egik eset lehetséges, íg a sorrend AHBECFDG, azaz Aladár Hannába szerelmes. 7. a) b) c)

16 SOKSZÍNÛ MATEMATIKA A KITÛZÖTT FELADATOK EREDMÉNYE 7. GRÁFOK út, vonal, séta, kör, Euler-vonal (kiegészítõ anag). a) Minden ont fokszáma, és a gráf összefüggõ, íg van (zárt) Euler-vonala. b) ont fokszáma áratlan, tehát nem járható be. c) ont fokszáma áratlan, a többi áros. Íg van nitott Euler-vonala, tehát bejárható.. ont fokszáma áratlan, íg nem lehetséges.. Legenek eg gráf ontjai a bank heliségei, és az élek jelezzék az ajtókat (csak a B és a H heliség fokszáma áratlan). Az Euler-vonalnak nitottnak kell lennie a B és H csúcsok közt. Mivel B-bõl indult, H-ban van a széf.. a) Mivel -nél több áratlan fokszámú ont van, nem rajzolható meg. b) Mivel ont fokszáma áratlan, a gráfot vonalra lehet felbontani, íg -szor kell felemelni a ceruzát. c) A tartománok alkossák eg gráf csúcsait. Minden szakasz feleljen meg eg élnek a két oldalán lévõ tartománok között. A kívánt görbét követve gráfunkban eg Eulervonalat járnánk be, amel viszont nincs, hiszen nég csúcs/ tartomán foka is áratlan. Tehát nincs ilen görbe. F A D G B I E C H. A három legrövidebb él mellé uganolan hosszal rakjunk be eg-eg árhuzamos élt. A kaott gráfban minden fok áros, íg van benne zárt Euler-vonal, amel megfelel az eredeti gráf eg bejárásának, ahol a három legrövidebb élt dulán járjuk be. Ennél jobb útvonalunk nem lehet, mert gráfunkban hat áratlan fokú ont van. Íg legalább három élt többszörösen be kell járnunk. A lehetséges útvonal: AGHBCHDCHIDEIFEIGFABGA.. Az élvázon biztos lesz áratlan fokú ont, íg nem lehet zárt Euler-vonala. Ha csak áratlan fokú ont van, akkor a drótot elég helen elvágni és két helen forrasztani. Pl. 7. a) Eg ontú gráfban legalább élnek kell lenni, hog a gráf összefüggõ lehessen. Legfeljebb 7 élt lehet törölni, hisz 0 él van. b) 7 élt elhagva még összefüggõ lehet a gráf, és a körök is megszûnnek.. a) igaz; b) hamis, l.: ; c) igaz; d) hamis, l.: ; e) igaz.

17 . Fagráfok (kiegészítõ anag). Legalább út kell, hog összefüggõ legen.. A fa teljes gráfja nem rajzolható meg, hiszen végtelen. Az elsõ év az ábrán látható. f 0 =, f =, f n = f n Þ f n = n Þ f =.. év.. a) A szénhidrogéneknek megfelelõ gráfok olan gráfok,. év amelekben eg (H) és nég (C) fokú csúcsok szereelnek, nincs bennük hurokél, de árhuzamos élek lehetnek bennük. etán: fagráf, db fokú és db fokú ont; ciklobután: van benne kör, nincs többszörös él, db fokú és db fokú ont; etilén: nincs benne kör, van többszörös él, db fokú és db fokú ont; acetilén: nincs benne kör, van többszörös él, db fokú és db fokú ont; benzol: van benne kör, van többszörös él, db fokú és db fokú ont. b) fokszámok összege: + 9 = áratlan, nincs ilen vegület; élek száma: élek száma: 0 + = él Þ fagráf Þ alkán; ont + 0 = él van benne kör ont cikloalkán; kétszer anni H, mint C (nem lehet kettõ kötött él) 0 élek száma: + = él van benne kör van többszörös éle, tehát arén ont több C, mint H c) Ha h darab hidrogénatom szereel, akkor a szénhidrogénnek megfelelõ gráfban h + csúcs van, a fokok összege edig h +. A fokok összege a kétszeres élszám, amel most a csúcsszámnál eggel kisebb szám kétszerese (gráfunk fagráf), azaz (h + ). A fokok összegének kétféle felírásából h =. A lehetõségek:. év H H H H H H H H H C H H H H C C H H H H H H H H H H H C C C H H C C C C H H C C C C H H C C C C C C H H C H H C H H H H C H H H H H C H H H H H H H H H H H H H 7

19 A második legerõsebb versenzõ kiválasztását a valódi sortesemének rendezõi nem vállalják, hanem az utolsó mérkõzést döntõnek nevezik és a vesztest tekintik a második legjobbnak. Azt, hog a két legerõsebb versenzõ az elsõ mérkõzésen találkozzon, azt elõzetes erõsorrendek alaján megtervezett tornákkal küszöbölik ki. A második legerõsebb versenzõ azok közül kerülhet ki, akik csak a legerõsebbtõl katak ki. Íg kell eg tornát rendezni a legerõsebb kiválasztására, majd eg külön tornát azok számára, akiket a legerõsebb gõzött le.. a) Igaz, ha legalább ont van. b) Hamis. c) Hamis, ha legalább ont van. d) Hamis, mert akkor lenne benne kör. 7. I. Eg csúcsból él indul ki Þ -félekéen. II. Eg csúcsból él indul ki Þ hog mel -ba, majd a negediket -félekéen köthetjük össze velük, mind az csúcs esetén 0 -félekéen. = III. Ha eg csúcsból legfeljebb él indul ki, akkor a falvak eg útvonalra vannak felfûzve.! Sorbarendezésük -félekéen történhet (osztunk -vel, hiszen ha eg sorbarendezést tükrözünk, az uganazt az úthálózatot határozza meg). Összesen -féle úthálózat lehetséges.. Kétjegû boldog számból indulva az utolsó elõtti szám 0 vag 00. Gondolkozzunk visszafelé haladva! Az összes kétjegû boldog szám tehát: 0; ; 9; ; ; ; ; ; ; ; ; 9.. Rejtvén: Feltehetjük, hog a felmenõim között nem történt rokonházasság. Ebben az esetben a dédaáim nagajai (összesen személ) közül a naganáimnak a dédaja. Õk nilvánvalóan különbözõ személek, mint a nagaáim dédajai. (A nagaák dédajai is -an vannak, közöttük viszont szereel a dédanáim nagaja. A két halmaznak tehát vannak közös elemei, de – elemben különböznek.). Rejtvén: Toljuk be az A onthoz a Q kocsit, kacsoljuk ott le, és B felõl toljuk hozzá a P kocsit. Mindent egbekacsolva húzzuk ki a kocsikat az egenes szakaszra, ahol C-n túl lekacsoljuk Q-t. A P kocsit visszavisszük az eredeti helére, sõt betoljuk A-hoz, ahol lekacsoljuk. C felõl megközelítve A-t P-t behúzhatjuk a célhelére, majd a keleten lévõ Q-t is egszerûen a célhelre vezethetjük. 9

20 SOKSZÍNÛ MATEMATIKA A KITÛZÖTT FELADATOK EREDMÉNYE 9. A kombinatorika gakorlati alkalmazásai. szoba: , ,7 = 000, Ft félanzió: , ,7 = 000, Ft biztosítás: 000 = 000 Ft arkolás: 00 = 9000 Ft benzin:, = 0, Ft Síbérlet nélkül a költség, Ft. Síbérlet: 7, +, = 0, nara:,7 +, = 7,7, -t kockáztatnak.. A vízgûjtõ terület: dm = 0 9 dm. A hó vastagsága: dm. A hó térfogata: 0 9 dm. A víz térfogata: 0, 0 9 dm. A tóba kerül:, 0 9 dm. A tó felszíne:, dm =0 0 dm. A vízszint emelkedése:, dm. 0