Gráfok

a) Az állítás igaz.
Ha egy összefüggő gráfban nincs kör, akkor az a gráf egy fagráf. Minden fagráfnak azonban van legalább két elsőfokú (1-es fokszámú) pontja (levele). Mivel a feladat feltétele szerint minden pont fokszáma legalább 2, a gráf nem lehet fagráf, így az összefüggőség miatt biztosan tartalmaz kört.

b) A megfordítás: Ha egy (kilencpontú, összefüggő, egyszerű) gráfban van kör, akkor minden pontjának fokszáma legalább 2.
Ez az állítás hamis. Készíthetünk például egy olyan gráfot, amelyben egy 3 hosszú körből indul ki egy "lánc" (út), amelynek a legutolsó pontja elsőfokú. Ebben a gráfban van kör, mégis létezik benne 1-es fokszámú pont.

c) Tegyük fel, hogy Balázs és Attila eddig csak egymással játszott, tehát a többi 7 versenyző egyikükkel sem mérkőzött meg.
Ebben az esetben a többi 7 játékos egymás között játszhatta le az összes eddigi mérkőzést. 7 játékos összes lehetséges egymás elleni meccsének száma legfeljebb $\binom{7}{2} = 21$.
Ezzel és Balázsék egyetlen meccsével együtt a bajnokságban legfeljebb $21 + 1 = 22$ mérkőzésre kerülhetett volna sor.
Mivel azonban már 23 mérkőzés lement, a feltételezésünk ellentmondásra vezetett. Így nem lehetséges, hogy még csak egymás ellen játszottak.

d) A bajnokságban összesen $\binom{9}{2} = 36$ mérkőzés van.
Ezekből a 3 balkezes egymás közötti mérkőzéseinek száma $\binom{3}{2} = 3$. Ezek a nem kívánt (balkezes a balkezes ellen) események.
Azt akarjuk, hogy a kiválasztott 23 mérkőzés mindegyike a maradék $36 - 3 = 33$ meccs közül kerüljön ki. A kedvező esetek száma tehát $\binom{33}{23}$.
A keresett valószínűség: $$ P = \frac{\binom{33}{23}}{\binom{36}{23}} = \frac{ \frac{33!}{23!10!} }{ \frac{36!}{23!13!} } = \frac{13 \cdot 12 \cdot 11}{36 \cdot 35 \cdot 34} = \frac{1716}{42840} \approx \mathbf{0,04006} $$ Mivel $\frac{1}{30} \approx 0,0333$, ezért a vizsgált valószínűség nem kisebb $\frac{1}{30}$-nál. Tehát az állítás nem igaz.

a) Építsük fel szisztematikusan az úthosszok alapján az érvényes útvonalakat (amelyek önmagukat nem metszik):

• 3 él hosszú utak: ABDF, ACDF, ACEF (3 lehetőség)
• 4 él hosszú utak: ABCDF, ABCEF, ABDEF, ACBDF, ACDEF, ACEDF (6 lehetőség)
• 5 él hosszú utak: ABCDEF, ABCEDF, ABDCEF, ACBDEF (4 lehetőség)

Összesen $3 + 6 + 4 =$ 13 megfelelő út van.

b) Rendezzük át a bizonyítandó kifejezést teljes négyzetté alakítással:

$$ a^2 + 2ab + b^2 - c^2 = (a+b)^2 - c^2 $$

A kapott különbséget szorzattá alakítva:

$$ (a+b+c)(a+b-c) $$

Mivel a feltétel szerint $a, b, c$ egy háromszög oldalhosszai, ezért érvényes rájuk a háromszög-egyenlőtlenség, azaz $a+b > c$, amiből $a+b-c > 0$ adódik. Továbbá az oldalhosszak pozitivitása miatt $a+b+c > 0$ is teljesül.
Két pozitív szám szorzata pozitív, így az állítás valóban igaz.

c) A megfordított állítás: „Ha $a, b$ és $c$ olyan pozitív valós számok, amelyekre $a^2 + 2ab + b^2 - c^2 > 0$ teljesül, akkor létezik olyan háromszög, amelynek oldalhosszai $a, b$ és $c$.”

Az állítás hamis. Ezt egyetlen ellenpéldával beláthatjuk. Legyen például $a = 2$, $b = 1$, $c = 1$.
Ekkor az egyenlőtlenség fennáll, hiszen $2^2 + 2(2)(1) + 1^2 - 1^2 = 8 > 0$.
Azonban $a = 2, b = 1, c = 1$ hosszúságú szakaszokból nem alkotható háromszög (a háromszög-egyenlőtlenség sérül, mert $b+c = 2$, ami nem nagyobb $a$-nál).

a) Merőlegest állítunk az \( A \) csúcsból az \( EB \) átlóra, ez az átlót az \( F \) felezőpontban metszi. Ekkor \( AF = 10 \text{ cm} \).
Az \( AFE \) derékszögű háromszögben: $$ \cos FAE\sphericalangle = \frac{10}{20} = 0,5 \implies FAE\sphericalangle = 60^\circ $$ Ebből adódik, hogy az egyenlőszárú háromszögből az \( A \) csúcsnál lévő szög \( BAE\sphericalangle = 120^\circ \), míg a másik kettő \( ABE\sphericalangle = AEB\sphericalangle = 30^\circ \).
Mivel a \( BCDE \) húrtrapéz alapon fekvő szögei 40°-osak, a másik két szög \( 180^\circ - 40^\circ = 140^\circ \).
Összeadva a szomszédos szögeket, az ötszög belső szögei: 120°, 70°, 140°, 140°, 70°.

b) Az \( EB \) átló hossza Pitagorasz-tétellel: $$ EB = 2 \cdot \sqrt{20^2 - 10^2} = 20\sqrt{3} \approx 34,64 \text{ cm} $$ Az \( ABE \) háromszög területe: $$ T_{ABE} = \frac{EB \cdot FA}{2} = \frac{20\sqrt{3} \cdot 10}{2} = 100\sqrt{3} \approx 173,2 \text{ cm}^2 $$ Ha a húrtrapéz \( CD \) oldalának hossza \( x \), akkor mivel a szárak is \( x \) hosszúak, a vetületek \( x \cos 40^\circ \)-ak lesznek. Felírhatjuk: $$ x + 2x \cos 40^\circ = EB \implies x(1 + 2 \cos 40^\circ) = 34,64 \implies x \approx 13,68 \text{ cm} $$ A trapéz magassága \( m = x \sin 40^\circ \approx 8,79 \text{ cm} \).
A trapéz területe: $$ T_{trap\acute{e}z} = \frac{34,64 + 13,68}{2} \cdot 8,79 \approx 212,4 \text{ cm}^2 $$ Az ötszög teljes területe a két rész összege: \( 173,2 + 212,4 = \mathbf{385,6 \text{ cm}^2} \).

c) A gráf élbejárása egy Euler-vonal megkeresését jelenti. Megfigyeljük a csúcsok fokszámait: az \( A \), \( C \) és \( D \) csúcsok fokszáma 2, míg a \( B \) és \( E \) csúcsok fokszáma 3 (ugyanis az \( EB \) átló is egy él). A bejárás kezdőpontja így csak a páratlan fokszámú \( B \) vagy \( E \) lehet.
Ha például a \( B \) pontból indulunk, akkor 3 lehetőségünk van (az \( E \), az \( A \) vagy a \( C \) felé). Ahhoz, hogy az összes élet bejárjuk elakadások nélkül, a gráfszerkezet egyszerűsége miatt észrevehetjük: a \( B \)-ből minden esetben az \( E \)-be kell végül megérkeznünk 3 él megtétele után (egyik esetben közvetlenül az \( EB \)-n), ahonnan a fennmaradó két élből álló kört bejárjuk.
Egy alapos leszámlálásból megkapjuk, hogy a \( B \)-ből indulva pontosan \( 3 \cdot 2 = 6 \) lehetőség van. (Például: BCDEBAE, stb.)
Szimmetria okokból az \( E \)-ből indulva is ugyanennyi, így összesen 12 bejárási lehetőség van.

a) Számítsuk ki a kért függvényértékeket: $$ f(-2) = 3^{-(-2)} = 3^2 = 9 $$ A 9 pozitív egész szám, tehát a Természetes számok (\( \mathbb{N} \)) halmazába kerül. $$ f(0,5) = 3^{-0,5} = \frac{1}{\sqrt{3}} $$ Mivel a \( \sqrt{3} \) irracionális, a hányados is az, így a Valós, de nem racionális számok (\( \mathbb{R} \setminus \mathbb{Q} \)) halmazába írjuk. $$ f(5) = 3^{-5} = \frac{1}{243} $$ Ez a szám két egész szám hányadosa (tört), de nem egész, ezért a Racionális, de nem egész számok (\( \mathbb{Q} \setminus \mathbb{Z} \)) halmazába, a legnagyobb belső téglalapba kerül.

b) Az \( A = \frac{1}{9} \), \( B = \frac{1}{2187} \) és \( C = 3^{-12} \) számok mind racionálisak. Mivel racionális számok összege racionális, az \( A \), \( B \) és \( C \) csúcsok között minden él be van húzva (ez 3 él). A \( D = 1 - \sqrt{2} \) irracionális szám. Az \( E \) szám értékét gyöktelenítéssel egyszerűsítjük: $$ E = \frac{1}{\sqrt{2}-1} = \frac{\sqrt{2}+1}{(\sqrt{2}-1)(\sqrt{2}+1)} = \frac{\sqrt{2}+1}{2-1} = \sqrt{2} + 1 $$ Ez szintén irracionális. Ha egy racionális számhoz (\( A, B, C \)) egy irracionális számot (\( D, E \)) adunk, az eredmény irracionális, így közöttük nincs él. Nézzük meg a két irracionális szám összegét: $$ D + E = (1 - \sqrt{2}) + (\sqrt{2} + 1) = 2 $$ Mivel a 2 racionális szám, a \( D \) és \( E \) csúcs között is be van húzva az él. A gráfnak tehát 4 éle van.

c) A megadott egyenlőtlenséget írjuk fel a \( g(x) = 3^{-x} \) függvény alakjában: $$ 3^{-n} - 3^{-(n+1)} > 10^{-6} $$ Kiemelve a kisebb hatványt: $$ 3^{-(n+1)} \cdot (3^1 - 1) > 10^{-6} $$ $$ 2 \cdot 3^{-(n+1)} > 10^{-6} \implies 3^{n+1} < 2 \cdot 10^6 $$ A két oldal 10-es alapú logaritmusát véve (a logaritmus szigorúan monoton nő): $$ (n+1) \cdot \log_{10} 3 < \log_{10} (2 \cdot 10^6) \approx 6,301 $$ $$ n+1 < \frac{6,301}{0,477} \approx 13,2 \implies n < 12,2 $$ A legnagyobb megfelelő pozitív egész szám \( n = 12 \). A téglalapok egységnyi (1) szélesek, a k-adik téglalap magassága \( g(k) = 3^{-k} \), így a területe is \( 3^{-k} \). Az első 12 téglalap területének összege egy mértani sorozat első 12 tagjának összege (\( a_1 = \frac{1}{3} \), \( q = \frac{1}{3} \)): $$ S_{12} = \frac{1}{3} \cdot \frac{1 - \left(\frac{1}{3}\right)^{12}}{1 - \frac{1}{3}} = \frac{1}{3} \cdot \frac{1 - 3^{-12}}{\frac{2}{3}} = \mathbf{\frac{1}{2} \cdot \left(1 - 3^{-12}\right) \approx 0,5} $$

a) Az összes találkozás száma: \( \binom{12}{2} = 66 \). Ebből a fiúk egymás közti kézfogásainak száma: \( \binom{7}{2} = 21 \). A maradék mind ölelés volt, így \( 66 - 21 = \mathbf{45} \) találkozás volt öleléssel. (Vagy összeadva: lányok egymás közt \( \binom{5}{2} = 10 \), plusz lány-fiú párosítások \( 5 \cdot 7 = 35 \), ami szintén 45.)

b) Modellezzük a lejátszott mérkőzéseket egy 6 csúcsú egyszerű gráffal. A 9 mérkőzés miatt a fokszámok összege \( 2 \cdot 9 = 18 \). Mivel mindenki páratlan számú meccset játszott (a fokszámok 1, 3 vagy 5 lehetnek), és András (A) fokszáma 1, a többiek fokszámainak összege \( 18 - 1 = 17 \).
Ahhoz, hogy az 5 maradék csúcs fokszámainak összege 17 legyen, legalább egy 5-ös fokszámú csúcsnak lennie kell. Csak Bori (B) lehet az (mivel A csak vele játszott, így A másokhoz nem fut be élként, másnak nem lehet mindenkihez éle).
Ebből adódóan a maradék négy ember (C, D, E, F) fokszámösszege \( 17 - 5 = 12 \). Páratlanságuk miatt mindannyiuknak kötelezően 3 a fokszáma.
A feltételek szerint C és E még nem játszott egymással (nincs él közöttük). Mivel C-nek és E-nek is 3 éle van, ezek az élek szükségképpen B-hez, D-hez és F-hez futnak.
Tehát a D csúcsba be van húzva él B-től, C-től és E-től is. Így meg is van D mind a 3 éle, ami azt jelenti, hogy az F-hez már nem fut be éle.
Tehát Dóra és Fanni még nem játszott egymás ellen.

c) A három másik dobó (András, Csaba, Dóra) összes lehetséges dobáskombinációjának száma \( 6^3 = 216 \).
Bori pontosan akkor nyer, ha:

• a többiek mindhárman kisebbet dobnak 5-nél (tehát csak 1, 2, 3 vagy 4-est). Ennek esetek száma: \( 4^3 = 64 \).
• a többiek mindhárman 6-ost dobnak (ekkor a 6-osok kiejtik egymást, és az 5 a legnagyobb egyedi). Ez \( 1^3 = 1 \) eset.
• pontosan ketten dobnak 6-ost, egy valaki pedig kisebbet 5-nél (ekkor szintén a 6-osok érvénytelenek). A két 6-ost dobó kiválasztása 3-féleképpen történhet, a harmadik dobása 4-féle lehet, így ez \( 3 \cdot 1^2 \cdot 4 = 12 \) eset.

Összesen \( 64 + 1 + 12 = 77 \) kedvező eset van.
A valószínűség: \( P = \frac{77}{216} \approx 0,356 \).

a) A \(D\), \(E\), \(F\) csoport egy 3 csúcsú részgráfot határoz meg, amiben \(\binom{3}{2} = 3\) lehetséges él van. Bármelyik él vagy létezik, vagy nem, így az ismeretségi hálók száma: \(2^3 = 8\).

b) A teljes háló elemzése:

• Az \(A\) pont fokszáma 5, ami azt jelenti, hogy minden más ponttal (\(B, C, D, E, F\)) össze van kötve.
• A \(D, E, F\) pontok egymás között egy teljes részgráfot alkotnak a friss információk szerint (tehát \(D\) ismeri \(E\)-t és \(F\)-et is stb.). Ezzel a \(D, E, F\) pontokból már 3-3 él kiindul (kettő a csoportjuk felé, egy pedig az \(A\) felé).

Két esetet vizsgálunk aszerint, hogy a \(B\) és \(C\) között van-e él:
1. eset: Nincs él \(B\) és \(C\) között.
A \(B\) pont fokszáma 4, és az 1 ismert élen (\(BA\)) kívül a maradék 3 élet kötelezően a \(D, E, F\) pontok felé kell behúzni. Ekkor \(B\) is kötött.
A \(C\) pont fokszáma 3, ebből 1 az \(A\)-hoz megy. Maradék 2 élet kell húznia a \(D, E, F\) halmazból kiválasztott két pontba. Ezt \(\binom{3}{2} = 3\)-féleképpen teheti meg.

2. eset: Van él \(B\) és \(C\) között.
A \(B\) pontnak így már 2 éle van (\(A\)-hoz és \(C\)-hez). A hiányzó 2 élet a \(D, E, F\) három pontja közül kettőhöz kell húznia. Ezt \(\binom{3}{2} = 3\)-féleképpen teheti meg.
A \(C\) pontnak így szintén 2 éle van. Neki a harmadik élét kell bekötnie a \(D, E, F\) pontok valamelyikébe, ami \(\binom{3}{1} = 3\)-féleképpen lehetséges.
Ebben az esetben tehát \(3 \cdot 3 = 9\) lehetőség van.

Összesen az első és második esetet összeadva: \( 3 + 9 = 12 \)-féle ismeretségi háló lehetséges.

c) Alkalmazzuk a komplementer módszert. Hat személyből a 3 fős csoportok teljes száma \(\binom{6}{3} = 20\).
Ebből le kell vonni azokat a csoportokat, amelyekben \(A\) és \(B\) együtt vannak. Ha az \(A\) és a \(B\) is a kiválasztott 3 tag része, a 3. tagot a fennmaradó 4 főből (C, D, E, F) kell kiválasztani. Ennek a lehetősége \(\binom{4}{1} = 4\).
A megfelelő kihallgatások száma tehát \(20 - 4 = 16\).

a) Az $f(x) = g(x)$ egyenlet megoldásával keressük meg a két függvény grafikonjának metszéspontjait: $$ (x + 4)(2 - x) = x + 4 \implies (x + 4)(2 - x - 1) = 0 \implies (x + 4)(1 - x) = 0 $$ A metszéspontok x-koordinátái tehát $-4$ és $1$.
A bezárt területet a határozott integrál adja meg: $$ T = \int_{-4}^{1} ((x+4)(2-x) - (x+4)) \, dx = \int_{-4}^{1} (-x^2 - 3x + 4) \, dx $$ $$ T = \left[ -\frac{x^3}{3} - \frac{3x^2}{2} + 4x \right]_{-4}^{1} $$ A határokat behelyettesítve: $$ = \left( -\frac{1}{3} - \frac{3}{2} + 4 \right) - \left( \frac{64}{3} - \frac{48}{2} - 16 \right) = \frac{13}{6} - \left( -\frac{56}{3} \right) = \frac{13 + 112}{6} = \frac{125}{6} \approx \mathbf{20,83} $$

b) A függvények zérushelyei:
$f$: $-4$ és $2$
$g$: $-4$
$h$: $-2$ és $2$
$i$: $-4$ és $4$
A közös zérushelyek alapján a következő élek húzhatók be: $(f, g)$, $(f, i)$ a $-4$ miatt; $(f, h)$ a $2$ miatt; és $(g, i)$ a $-4$ miatt.

c) A megadott három függvény ($k, m, n$) zérushelyei közti kapcsolatok egy fát (utat) alkotnak: $n$ (-5, 5) - $k$ (-5, 3) - $m$ (3, -3).
A gráf akkor marad fagráf, ha az új $p(x) = x + c$ elsőfokú függvény (amelynek egyetlen zérushelye $-c$) pontosan egy meglévő csúcshoz kapcsolódik be új levélként. Ehhez $p$-nek pontosan egy közös zérushelye kell legyen a $k, m, n$ valamelyikével úgy, hogy ne zárjon be kört.
- Ha $p$ zérushelye a $3$ vagy a $-5$ lenne, akkor az a $k$-hoz és egy másik ponthoz is kapcsolódna, így kör jönne létre (nem lenne fagráf).
- A zérushelye tehát csak a kimaradó ágvégek, azaz a $5$ vagy a $-3$ lehet.
Ha a zérushely $5$, akkor $c = -5$; ha $-3$, akkor $c = 3$.
A $c$ konstans tehát 2-féleképpen választható meg.

a) Az 5 négyzet összterülete $500 \text{ cm}^2$. Ebből a gúla alaplapja fixen $100 \text{ cm}^2$, a 4 oldallapot pedig a maradék $400 \text{ cm}^2$-ből vágjuk ki.
Az oldallapok háromszögek, amelyek alapja $10 \text{ cm}$. A legnagyobb lehetséges magasságuk $h = 10 \text{ cm}$ (ekkor épp kitöltik a külső négyzeteket). Ekkor az oldallapok területe: $$ 4 \cdot \frac{10 \cdot 10}{2} = 200 \text{ cm}^2 $$ A minimális hulladék ekkor: $500 - 100 - 200 = \mathbf{200 \text{ cm}^2}$.
Ugyanakkor a gúla felépíthetőségéhez a háromszögek magasságának nagyobbnak kell lennie, mint a $10 \text{ cm}$ oldalú alaplap középpontjából az oldalhoz húzott merőleges vetület, azaz $h > 5 \text{ cm}$. Ebből következően a 4 oldallap területe minimálisan: $$ > 4 \cdot \frac{10 \cdot 5}{2} = 100 \text{ cm}^2 $$ Így a hulladék biztosan kevesebb lesz, mint: $$ < 500 - 100 - 100 = \mathbf{300 \text{ cm}^2} $$ Az állítást ezzel igazoltuk.

b) A 8 csúcs közül 2 csúcsot $\binom{8}{2} = 28$-féleképpen választhatunk ki (összes eset).
Ebből kedvező esetek azok, amikor a kiválasztott csúcspárt él köti össze. A gráfnak megszámlálhatóan 12 éle van (4 a középső négyzetben, és $4 \times 2 = 8$ a külső háromszögekben).
A valószínűség tehát: $$ P = \frac{12}{28} = \mathbf{\frac{3}{7}} $$

c) A gráfunk 8 csúccsal rendelkezik. Ismert gráfelméleti tétel, hogy egy 8 csúcsú erdőnek (körmentes gráfnak) legfeljebb 7 éle lehet (ha összefüggő, akkor fa, melynek élszáma $v - 1 = 7$).
Mivel mi 9 élet színeztünk kékre, a kék élek által alkotott részgráfban az élek száma (9) meghaladja a körmentességhez megengedett maximális élszámot (7). Így a kék színű részgráfban biztosan van kör.

a) Minden fagráf egyben összefüggő gráf is, ezért az $F$ halmaz a $G$ halmaznak részhalmaza. Az a részhalmaz lesz üres, amely azokat a fagráfokat tartalmazza, melyek nem összefüggőek. Halmazművelettel kifejezve: $F \setminus G = \emptyset$. Az ábrán ez a rész satírozva látható:

b) Példák az egyes régiókba eső gráfokra:

c) A K és L épület fix, ezeken kívül még további $5 - 2 = 3$ épületet kell kiválasztani az 5 megmaradt (M, N, O, P, Q) épületből. Ezt $\binom{5}{3} = 10$-féleképpen teheti meg az őr. A kiválasztott 5 épületet egy meghatározott útvonalon, sorrendben járja be, ennek a permutációinak száma $5! = 120$. A két érték szorzata adja az összes útvonal számát: $$ 10 \cdot 120 = \mathbf{1200} \text{ útvonal.} $$

d) Tegyük fel indirekt módon, hogy van olyan csúcs, amelyből legalább 3 azonos színű él indul ki (mondjuk zöld él). Legyen ez a csúcs $A$, a 3 másik végpont pedig $B$, $C$ és $D$. Mivel a feladat feltétele szerint a gráfban nincsenek egyszínű háromszögek, a $B$, $C$ és $D$ csúcsokat összekötő élek között egyik sem lehet zöld (különben például az $ABC$ háromszög minden éle zöld lenne). Így a $BC$, $CD$ és $DB$ szakaszok szükségszerűen a másik színt, a kéket kapják. Ekkor azonban a $BCD$ egy teljesen kék háromszög lesz, ami ismét ellentmond a feltételnek, miszerint nincs egyszínű háromszög az ötszögben. Az indirekt feltevés hamis, az eredeti állítás tehát igaz.

a) I. állítás: hamis.
Az öt számjegy között a skatulyaelv miatt biztosan lesz három azonos paritású. Két számjegy különbsége pontosan akkor páros, ha azonos paritásúak. Ezért a három azonos paritású számjegyhez tartozó csúcsok mindegyike össze lesz kötve egymással, ami egy kört (háromszöget) alkot a gráfban. Egy köröket tartalmazó gráf viszont nem lehet fagráf.
II. állítás: igaz.
Megfelelő példa: ha választunk négy páratlan és egy páros számjegyet (pl. 1, 3, 5, 7 és 2). Ekkor a páratlan számok egy összefüggő részgráfot (teljes gráfot) alkotnak, míg a páros számnak megfelelő csúcs izolált lesz, így a gráf nem összefüggő.

b) Legyen a célállomások száma a két évvel ezelőtti időpontban \( n \), jelenleg pedig \( 1{,}5n \).
Mivel bármely két célállomás között van repülőjárat, a járatok száma egyenlő az \( n \) csúcsú teljes gráf éleinek számával. A feltétel szerint: $$ \binom{1{,}5n}{2} - \binom{n}{2} = 60 $$ Kifejtve a binomiális együtthatókat: $$ \frac{1{,}5n(1{,}5n - 1)}{2} - \frac{n(n - 1)}{2} = 60 $$ $$ 2{,}25n^2 - 1{,}5n - n^2 + n = 120 $$ $$ 1{,}25n^2 - 0{,}5n - 120 = 0 $$ Nullára rendezett másodfokú egyenletet megoldva a pozitív gyök \( n = 10 \).
Jelenleg tehát \( 1{,}5 \cdot 10 = \mathbf{15} \) célállomásra közlekednek.

c) A modell szerint 0,968 annak a valószínűsége, hogy egy utas megjelenik az indulásnál.
Binomiális eloszlást alkalmazva, annak a valószínűsége, hogy 169 utas jelenik meg (1 marad le): $$ P(169) = \binom{170}{169} \cdot 0{,}968^{169} \cdot 0{,}032^1 \approx 0{,}0223 $$ Annak a valószínűsége, hogy 170 utas jelenik meg (2 marad le): $$ P(170) = \binom{170}{170} \cdot 0{,}968^{170} \cdot 0{,}032^0 \approx 0{,}0040 $$ Annak a valószínűsége, hogy legfeljebb 168 utas jelenik meg (mindenkinek jut hely): $$ 1 - P(169) - P(170) \approx 1 - 0{,}0223 - 0{,}0040 = \mathbf{0{,}9737} $$ A légitársaság által fizetendő kártérítés várható értéke: $$ P(169) \cdot 600 + P(170) \cdot 1200 \approx 0{,}0223 \cdot 600 + 0{,}0040 \cdot 1200 \approx 13{,}38 + 4{,}80 = \mathbf{18{,}18 \text{ euró}} $$ (A hivatalos javítókulcs az eredmények kerekítésével 18 eurót is elfogad.)

a) A modell egy \( 3 \times 3 \)-as rácsgráfot eredményez. Ebben a gráfban: - 4 sarokcsúcs van, mindegyiknek a fokszáma 2. - 4 élközépi csúcs van, mindegyiknek a fokszáma 3. - 1 darab középső csúcs van, amelynek a fokszáma 4. A gráfban a fokszámok összege: $$ \sum = 4 \cdot 2 + 4 \cdot 3 + 1 \cdot 4 = 8 + 12 + 4 = \mathbf{24} $$ (Alternatívan: a gráfnak 12 éle van, így a fokszámösszeg \( 2 \cdot 12 = 24 \).)

b) A felrajzolt gráf csúcsai kiszínezhetők sakktáblaszerűen (például két színnel) úgy, hogy minden él csak különböző színű csúcsokat kössön össze. Az ilyen gráfokat páros gráfoknak nevezzük. A matematika egyik alapvető tétele szerint a páros gráfokban nincsenek páratlan hosszú (páratlan sok élből álló) körök.

c) Például: Ha elhagyjuk az A2 és a B1 jelű csúcsokat, a megmaradó 7 elem által alkotott gráf nem lesz összefüggő, hiszen az A1 sarokelem elszigetelődik a gráf többi részétől, így két komponens jön létre.

d) A három közvetlenül összekapcsolódó elem elrendezése háromféle alakzatot adhat ki a \( 3 \times 3 \)-as rácsban: vízszintes, függőleges, vagy L-alakú. - Vízszintes: minden sorban található pontosan 1 ilyen elemhármas (összesen \( 3 \)). - Függőleges: minden oszlopban található pontosan 1 ilyen elemhármas (összesen \( 3 \)). - L-alakú: minden \( 2 \times 2 \)-es blokkban \( 4 \) darab ilyen forma helyezkedik el. Mivel a táblán \( 4 \) darab \( 2 \times 2 \)-es rész van, ez \( 4 \cdot 4 = 16 \) lehetőséget ad. A kiválasztások teljes száma így: \( 3 + 3 + 16 = \mathbf{22} \).

a) Az állítás megfordítása: Ha egy pozitív egész \( a \) szám osztója egy pozitív egész \( b \) szám négyzetének (\( a|b^2 \)), akkor a \( b \) számnak is osztója (\( a|b \)).
Ez a megfordított állítás hamis. Jó ellenpélda például az \( a = 4 \) és \( b = 2 \). A \( 4 \) osztója a \( 2^2 \)-nek (azaz a 4-nek), de a 4 nem osztója a 2-nek.

b) A feladat szerint az \( n^2 - pn = n(n - p) \) szorzatnak egy \( q \) prímszámot kell adnia.
Mivel prímről van szó, a szorzat egyik tényezőjének \( 1 \)-nek, a másiknak egy prímnek kell lennie. Mivel \( n \) és \( p \) is pozitív, ezért \( n > n - p \), tehát a kisebbik tényező az 1. Így \( n - p = 1 \) és \( n = q \) prím.
Ebből következik, hogy \( n = p + 1 \). Tehát a \( p \) és az \( n \) két szomszédos prímszám. Mivel a 2 az egyetlen páros prím, az egyetlen egymást követő prímszám páros a 2 és a 3. Így \( p = 2 \) és \( n = 3 \) az egyetlen megoldás. Összesen 1 ilyen szám létezik.

c) A gráf csúcsait összekötöttük az összes osztójukkal. Mivel minden egész szám önmagának is osztója, a gráf minden csúcsa össze van kötve önmagával is, azaz hurokéleket tartalmaz. Mivel tartalmaz hurokélt, nem lehet egyszerű gráf.

d) Egy adott szám osztóinak száma határozza meg, hány él fut be hozzá az osztók felől. Mivel minden él pontosan egyszer jön létre két csúcs között (a nagyobb osztja kisebbel viszonya miatt), a gráf éleinek teljes száma egyenlő az 1-től 10-ig terjedő számok osztóinak darabszám-összegével.
Tudjuk, hogy minden négyzetszámnak páratlan számú osztója van, az összes többi számnak pedig páros. 1-től 10-ig pontosan három négyzetszám található: az 1, a 4 és a 9.
Az élek összege három páratlan szám és hét páros szám összege lesz, ami egy páratlan számot eredményez. Ezzel igazoltuk, hogy az élek száma páratlan (pontosan 27).

a) Alkalmazzunk indirekt bizonyítást. Tegyük fel, hogy minden csúcs fokszáma legfeljebb 2. Ekkor a fokszámok összege maximum \(8 \cdot 2 = 16\) lenne.
Tudjuk azonban, hogy bármely gráfban a fokszámok összege az élek számának kétszerese, vagyis jelen esetben \(2 \cdot 9 = 18\).
Mivel \(18 > 16\), ellentmondásra jutottunk, tehát kell lennie legalább egy olyan csúcsnak, melynek fokszáma legalább 3.

b) A szabályos nyolcszög összes szakaszának (oldalak és átlók együttes) száma a nyolc csúcsból választható kétpontos részhalmazok száma: \(\binom{8}{2} = 28\).
Ebből a 28 szakaszból választunk 4-et, így az összes esetek száma: \(\binom{28}{4} = 20\,475\).
Egy adott csúcsból (pl. az \(A\)-ból) pontosan \(8 - 1 = 7\) szakasz indul ki. Ahhoz, hogy mind a 4 kiválasztott szakasz az \(A\)-ból induljon, ebből a 7-ből kell kiválasztanunk 4-et. A kedvező esetek száma: \(\binom{7}{4} = 35\).
A keresett valószínűség: $$ P = \frac{\binom{7}{4}}{\binom{28}{4}} = \frac{35}{20\,475} = \mathbf{\frac{1}{585} \approx 0,0017} $$

c) A párosítások számát logikusan lépésenként is felépíthetjük. Válasszunk ki egy tetszőleges sakkozót az első párba, őt 7-féleképpen sorsolhatjuk valakivel. A maradék 6 emberből egyet ismét kiemelve, neki 5-féleképpen választhatunk ellenfelet. A fennmaradó 4-ből egy kiválasztottnak 3 ellenfele lehet, míg az utolsó 2 ember kötelezően egymással játszik (1 lehetőség).
Mivel ez a gondolatmenet a sorrendet nem veszi figyelembe, csak magukat a párokat alakítja ki, a teljes szám egyszerűen a lehetőségek szorzata: $$ 7 \cdot 5 \cdot 3 \cdot 1 = \mathbf{105} $$ (Ugyanez megkapható a \(\frac{\binom{8}{2}\binom{6}{2}\binom{4}{2}\binom{2}{2}}{4!}\) formulával is.)

a) A harmadik sor harmadik mezője a \( 2 \cdot 7 + 3 = 17 \). tag, tehát \( a_{17} = 91 \).
Az ötödik sor ötödik mezője a \( 4 \cdot 7 + 5 = 33 \). tag, tehát \( a_{33} = 11 \).
A különbségük: \( a_{33} - a_{17} = 16d \implies 11 - 91 = -80 \implies d = -5 \).
Ebből az első tag: \( a_1 = 91 - 16 \cdot (-5) = 171 \).
A 49 elem összege a számtani sorozat összegképletével: $$ S_{49} = \frac{2 \cdot 171 + (49-1)(-5)}{2} \cdot 49 = \frac{342 - 240}{2} \cdot 49 = \mathbf{2499} $$

b) Az egyes sorok elején rendre a sorozat \( a_1, a_8, a_{15}, a_{22}, a_{29}, a_{36}, a_{43} \) tagja áll. Minden egyes oszlopból csak egy szám választható, így a kiválasztott szám a saját sorának elején álló számból úgy keletkezik, hogy ahhoz \( 0d, 1d, 2d, \ldots, 6d \)-t adunk hozzá, és e hét oszlop-eltolás mindegyike pontosan egyszer fordul elő.
Ha tehát összeadjuk a táblázatból kiválasztott hét számot, az összegben fixen megjelenik a sorok elején álló hét szám összege, továbbá a \( 0d + 1d + 2d + 3d + 4d + 5d + 6d = 21d \) eltolás.
Mivel ez az érték a konkrét oszlop-kiválasztások sorrendjétől függetlenül ugyanazokat a komponenseket tartalmazza, a hét szám összege minden esetben ugyanannyi lesz.

c) Péter összesen \( 7! = 5040 \)-féleképpen választhat ki a táblázatból számokat a megadott szabály (minden sorból és oszlopból egyet) szerint.
Ha a 91 (3. sor, 3. oszlop) és a 11 (5. sor, 5. oszlop) is a kiválasztott számok közt van, akkor a maradék 5 sorhoz és 5 oszlophoz kell hozzárendelni a számokat. Ezt \( 5! = 120 \)-féleképpen teheti meg.
A kérdéses valószínűség így: $$ P = \frac{120}{5040} = \mathbf{\frac{1}{42} \approx 0,024} $$

a) Az állítás hamis.
Ellenpélda: egy 6 pontú gráf, amely két diszjunkt körből (pl. két különálló háromszögből) áll. Ebben minden pont fokszáma 2, de a gráf nem összefüggő.

b) A megfordítás: Ha a gráf összefüggő, akkor minden pontjának fokszáma legalább 2.
Ez az állítás is hamis.
Ellenpélda: bármely véges fa (pl. egy 3 pontból álló út, vagyis láncgráf), amely összefüggő, de vannak elsőfokú pontjai (levelei).

c) A megadott gráfok sorszámait a halmazok definíciói alapján, a megfelelő metszetekbe kell beírni a Venn-diagramba. (A sorszámok elhelyezése a gráfok tulajdonságai alapján történt).

d) Egy tetszőleges 6 pontú fa rajzolása a feladat. Mivel a fák összefüggő, de kört nem tartalmazó egyszerű gráfok, így ezt a gráfot a \( (P \cap Q) \setminus R \) halmazrészbe kell elhelyezni.

a)
(1) Az állítás hamis. Egy ötpontú egyszerű gráf éleinek maximális száma akkor van, ha a gráf egy teljes gráf. A teljes gráf éleinek száma: \( \binom{5}{2} = 10 \), vagyis nem létezik 11 élű ötpontú egyszerű gráf.
(2) Az állítás igaz. Tételezzük fel az ellenkezőjét, hogy a feltétel teljesülése mellett nincs negyedfokú csúcs. (Az ötödiknél nagyobb fokszám az ötpontú egyszerű gráfban lehetetlen.) Ez azt jelenti, hogy minden egyes csúcs pontosan harmadfokú lenne. Ekkor a fokszámok összege \( 5 \cdot 3 = 15 \). Azonban bármely gráfban a fokszámok összege mindig páros (hiszen minden élet két csúcsnál számolunk a fokszámokhoz), ez a páratlan összeg lehetetlen. Biztosan lennie kell legalább egy negyedfokú csúcsnak.

b) Az ötpontú teljes gráfnak 10 éle van. Véletlenszerűen beszínezünk ezekből 6 élt. Az összes lehetséges élkiválasztás (színezés) száma: $$ \binom{10}{6} = 210 $$

Keressük azon esetek számát, amikor a színezett 6 él nem alkot összefüggő gráfot. Egy ötpontú nem összefüggő gráf legalább két komponenst tartalmaz. A maximális élszámot a különböző pontelosztású komponensek adhatják, vizsgáljuk meg az eseteket:
- Ha a komponensek 3 és 2 pontosak: A két részben lévő maximális élszám egy-egy teljes gráfként \( \binom{3}{2} + \binom{2}{2} = 3 + 1 = 4 \) lehetne. Így ez nem tartalmazhat 6 élt.
- Ha a komponensek 4 és 1 pontosak: A 4 pontos komponens egy 4 pontú teljes gráf, aminek az élszáma \( \binom{4}{2} = 6 \). A magányos csúcs izolált pont, nincs rajta él. Tehát pont be lehet színezni azt a 6 élt úgy, hogy egy K_4 gráfot kapjunk.

Csak az utóbbi eset megfelelő a 6 színezett él felosztására. Egy izolált pont kiválasztására \( \binom{5}{1} = 5 \) lehetőség van, ami a fennmaradó 4 ponthoz tartozó 6 élt egyértelműen kijelöli. A megfelelő színezések száma így 5 darab.
A valószínűség tehát: $$ P = \frac{5}{210} = \frac{1}{42} \approx \mathbf{0,0238} $$

a) Minden fiú (3 fő) 5 lehetőség közül választhat (3 étterem + 2 fagyizó). Így ez együtt \( 5^3 \) lehetőség.
Minden lány (2 fő) 4 lehetőség közül választhat (2 fodrászat + 2 fagyizó). Ez együtt \( 4^2 \) lehetőség.
Mivel a döntéseik függetlenek, az elhelyezkedések száma összesen: \( 5^3 \cdot 4^2 = 125 \cdot 16 = \mathbf{2000} \).

b) Mivel a 3 fiú különböző munkahelyekre akar menni, a számukra rendelkezésre álló 5 hely közül kell 3-at választani, sorrenddel (ismétlés nélküli variáció): \( 5 \cdot 4 \cdot 3 = 60 \)-féleképpen helyezkedhetnek el.
A 2 lány a számukra lehetséges 4 helyre ugyanezen elv alapján \( 4 \cdot 3 = 12 \)-féleképpen mehet.
Az összes eset e kettő szorzata: \( 60 \cdot 12 = \mathbf{720} \).

c) A körmérkőzésen egy 4 pontból álló teljes gráf éleit választjuk ki (összesen 6 mérkőzés lehetséges). Most ebből 3 élt (mérkőzést) játszanak le.
A feltétel szerint 2 játékos játszott 2-2 mérkőzést, azaz a gráfban pontosan két csúcs foka 2. A fokszámok összege \( 2 \cdot \text{élek száma} = 2 \cdot 3 = 6 \). Tehát a fokszámok csak a (2, 2, 1, 1) sorozatot alkothatják (ez egy 4 hosszú utat jelent).
A legegyszerűbb, ha kiválasztjuk a 6 lehetséges mérkőzésből (élből) a 3 lejátszottat, ami \( \binom{6}{3} = 20 \) lehetséges kiválasztás.
Megszámoljuk, hány olyan gráf van, ami NEM felel meg:

• Amikor egy játékos mindhárom meccset lejátssza (csillaggráf, fokszámok: 3, 1, 1, 1). Ez 4-féleképpen lehetséges.
• Amikor három játékos játszik egymással egy háromszöget, egy pedig egyet sem (fokszámok: 2, 2, 2, 0). Ez is 4-féleképpen lehetséges.

Így a feltételeknek megfelelő párosítások száma: \( 20 - 4 - 4 = \mathbf{12} \).

a) Jelöljük egy gráffal az ismeretségeket! Egy 41 pontú gráfunk lesz, ahol minden pont fokszámát ismerjük, hiszen Anna mind a 40-et ismeri (az ő fokszáma 40). A többi 40 ember pontosan egy embert nem ismer a másik 39 közül, és Annát mind ismeri, ezért az ő fokszámuk egységesen 39.
A fokszámtétel (a fokszámok összege az élek számának duplája) alapján: $$ 2e = 40 + 40 \cdot 39 = 1600 $$ Tehát összesen 800 ismeretség (él) van köztük.

b) Ha Anna 40 ismerőse mindegyike ismerné az összes többi 39 embert, akkor a 40 pontú (rész)gráf éleinek száma \( \frac{40 \cdot 39}{2} = 780 \) lenne. (Ezek az összes esetek).
Mivel mindenki pontosan egyet nem ismer ebből a körből, a hiányzó élek száma \( \frac{40 \cdot 1}{2} = 20 \). (Ezek a kettesével párbarendezett nem-ismerősök).
A fennálló ismeretségek (kedvező esetek) száma a 40 ember között: \( 780 - 20 = 760 \).
A keresett valószínűség: $$ P = \frac{760}{780} = \mathbf{\frac{38}{39} \approx 0,974} $$

c) A kiválasztott két személy a 41-ből kerül ki. Az összes lehetséges kiválasztások száma: \( \binom{41}{2} = \frac{41 \cdot 40}{2} = 820 \).
A feltétel szerint a két kiválasztott személy NEM ismeri egymást. Mivel Anna mindenkit ismer, Anna nem lehet ezen párosítások egyike sem. Így a "nem ismerősök" csak Anna 40 barátja közül kerülhetnek ki.
Ahogy a b) részben megállapítottuk, pontosan 20 olyan pár van a barátok között, akik nem ismerik egymást (mivel a 40 ember pontosan egy embert nem ismer, egyértelműen kettesével párba állíthatók).
Így a kedvező esetek száma 20. A keresett valószínűség: $$ P = \frac{20}{820} = \mathbf{\frac{1}{41} \approx 0,0244} $$