Diszkrét matematika I. feladatok

Diszkr´et matematika I. feladatok

1. 1.1.

Komplex sz´ amok Fogalmak

´ jel: i, amire igaz: i2 = −1. Uj Minden z komplex sz´ am a k¨ ovetkez˝ o alakba ´ırhat´o: z = a + i · b, ezt nevezz¨ uk z algebrai alakj´anak. a-t a komplex sz´ am val´ os r´esz´enek, b-t pedig a k´epzetes r´esz´enek nevezz¨ uk. A z konjug´altja a z¯ = a − i · b komplex sz´am. Egy z komplex sz´ am abszol´ ut ´ert´eke a |z| = (a2 + b2 )1/2 sz´ am. Komplex sz´ amok trigonometrikus alakja: z = |z| · (cosα + i · sinα). Ha 0 6= z ∈ C, akkor a −π < α ≤ π sz¨ oget z argumentum´ anak nevezz¨ uk. Komplex sz´ amok szorz´ asa. Legyen z = |z| · (cosα + i · sinα) ´es w = |w| · (cosβ + i · sinβ). Ekkor k¨onnyen bel´athat´ o, hogy z · w = |z · w| · (cos(α + β) + i · sin(α + β)). Ebb˝ ol k¨ovetkezik, hogy minden nem nulla z komplex ´es minden n term´eszetes sz´ amra z n = |z|n · (cos(nα) + i · sin(nα)). 1. Fejezd ki algebrai alakban a k¨ ovetkez˝ o sz´ amokat: a) (3 + i)(2 + 3i); b) (1 − 2i)(5 + i) ; c) (2 − 5i)2 ;

d) (1 − i)3 .

2. ´Ird a lehet˝ o legegyszer˝ ubb alakba a k¨ ovetkez˝ o kifejez´eseket: 1 1 1 3 5 8 a) i ; b) i ; c)i ; d) 2 ; e) ; f ) 3 . i i i 3. A k¨ ovetkez˝ o sz´ amokat fejezd ki algebrai alakban: √ 3 + 4i 1 1 3−i ; b) √ ; a) ; c) ; d) 1 − 2i (1 + i)2 (2 − i)(1 + 2i) 3+i

e)

1 1 + ; 2 + 3i 2 − 3i

f)

1 1 + . 3 + i 1 + 7i

4. Add meg az a ´es b val´ os sz´ amok ´ert´ek´et, ha: a) (a + bi)(2 − i) = a + 3i; b) (a + i)(1 + bi) = 3b + ai. 5. Legyen

5 2 + = 1, ahol x ´es y val´ os sz´amok. Add meg x ´es y ´ert´ek´et! x + yi 1 + 3i

6. Add meg a k¨ ovetkez˝ o sz´ amokat trigonometrikus alakban: √ 10 2 + 3i a) 3 + i; b) 1 − i; c) 4i; d) −3; e) √ ; f) ; 5+i 3−i

g) 3 − 4i;

h) −2 + i.

(1 + i)9 7. Sz´ am´ıtsd ki a k¨ ovetkez˝ o kifejez´eseket a trigonometrikus alak felhaszn´al´as´aval: a) ; (1 − i)7

√ b)

1−

3−i 2

!24 .

8. Add meg a −7 − 24i komplex sz´ am n´egyzetgy¨ okeit algebrai alakban. 9. Vonjunk n´egyzetgy¨ ok¨ ot a k¨ ovetkez˝ o sz´ amokb´ ol: a) 3 − 4i;

b) 2i;

c) 8 + 6i.

10. Oldd meg a k¨ ovetkez˝ o m´ asodfok´ u egyenletet: (2 + i)x2 − (5 − i)x + (2 − 2i) = 0. √ 11. Sz´ amold ki a z = −16 · 3 + 16i sz´ am ¨ ot¨ odik gy¨okeit! 12. Vonj harmadik gy¨ ok¨ ot a) 1- b˝ ol;

b) 2 + 2i-b˝ ol.

13. Vonj negyedik gy¨ ok¨ ot a k¨ ovetkez˝ o sz´ amb´ ol:

−4 . (2 + i)3

14. Bizony´ıtsd be a komplex sz´ amok seg´ıts´eg´evel, hogy egy paralelogramma ´atl´oinak n´egyzet¨osszege egyenl˝o az oldalak n´egyzet¨ osszeg´evel. ´ azoljuk a z = 2 + i komplex sz´ 15. Abr´ amot a Gauss-sz´ams´ıkon vektorral. Adjuk meg algebrai alakban ´es ´ abr´ azoljuk ugyanezen az ´ abr´ an a k¨ ovetkez˝ oket: −z; z; −z; iz; −iz.

1

16. Mi a geometriai jelent´ese a k¨ ovetkez˝ oknek: √ 1 3 a) |z1 − z2 |; b) i-vel val´ o szorz´ as ; c) + i-vel val´o szorz´as; 2 2

d) cos

2π 2π + sin -nel val´o szorz´as. n n

17. Hol helyezkednek el a s´ıkon azok a pontok, amelyeknek megfelel˝o komplex sz´amokra z − 3i ≥ 1 ; c) z = 1 ; d) z = − 1 ; e) |z| = iz; e) |z − i| < 1; a) |z| = 2<(z); b) z+i z z g) |z − 1| < 1 ´es <(z) > 0; h) |z − 1| = 2|z − 2 + 1|.

f ) 2 < |z| ≤ 3;

z − 2i komplex sz´ am z+4 val´ os r´esze z´erus. Bizony´ıtsuk√be, hogy Z m´ertani helye egy k¨or¨on van rajta. Keress¨ uk meg a k¨or k¨oz´eppontj´ at, ´es mutassuk meg, hogy a sugara 5.

18. A z = x + yi komplex sz´ amnak a Gauss sz´ ams´ıkon feleltess¨ uk meg a Z pontot. Tudjuk, hogy a

19. Bizony´ıtsd be, hogy egy p kvaterni´ ora |<(p)| ≤ |p|, |=(p)| ≤ |p| ´es kp| ≤ |<(p)| + |=(p)|. 20. Ha p = 1 + i + j + k ´es q = k kvaterni´ ok, hat´ arozd meg a p, p2 , 1/p, q(1/p) ´es (1/p)q kvaterni´okat. 21. Mutasd meg, hogy ha q tetsz˝ oleges kvaterni´ o, akkor q − iqi − jqj − kqk = 4<(q).

2.

Logikai alapok

1. Egy fikt´ıv univerzum le´ır´ as´ ahoz a k¨ ovetkez˝ o predik´atumokat haszn´aljuk: J(x) : x Jedi, S(x) : x Sith, F (x) : x f´erfi, N (x) : x n˝ o, M (x) : x mester, T (x, y) : x tan´ıtv´anya y-nak, L(x, y) : x legy˝ozi y-t. ´Igy p´eld´aul T (Luke, Cs´ asz´ ar) azt jelenti, hogy Luke legy˝ ozi a Cs´ asz´ art. ´Irjuk fel logikai formul´akkal a k¨ovetkez˝o magyar nyelv˝ u mondatokat: a) Minden Jedi f´erfi; b) minden Jedi n˝ o, de nem minden n˝o Jedi; c) Sith-ek mindig ketten vannak, egy mester ´es a tan´ıtv´ anya; d) a Sith-eket mindig a tan´ıtv´anyaik gy˝ozik le; e) Yoda mesternek 800 tan´ıtv´ anya van, de nem mind Jedi; f ) egy Jedi csak akkor v´alhat mesterr´e, ha legy˝ ozi onmag´ ¨ at; g) n˝ oi Sith mesternek sosincs n˝oi tan´ıtv´anya; h) Jedi mester gy˝oz¨ott m´ar le m´asik Jedi mestert, aki azonban egy Sith tan´ıtv´ anya is volt ; i) a Cs´asz´ar tan´ıtv´anya k´et mester´et is legy˝ozte. 2. Pozit´ıv eg´eszeket tekintve, jel¨ olje P (x), E(x), O(x), illetve D(x, y) rendre azt, hogy x pr´ım, p´aros, p´aratlan, illetve hogy x oszt´ oja y-nak. Ford´ıtsuk le magyar nyelvre az al´abbi formul´akat. Tagadjuk a formul´akat form´alisan, illetve k¨ oznyelvileg. Melyik r¨ ovid´ıthet˝ o ∃! haszn´ alat´ aval? a) P (7); b) (E(2) ∧ P (2)); c) (∀x(D(2, x) ⇒ E(x))); d) (∃x(E(x) ∧ D(x, 6))); e) (∀x(¬E(x) ⇒ ¬D(2, x))); f ) (∀x(E(x) ⇒ (∀y(D(x, y) ⇒ E(y))))); g) (∀x(P (x) ⇒ (∃y(E(y) ∧ D(x, y))))); h) (∀x(O(x) ⇒ (∀y(P (y) ⇒ ¬D(x, y))))); i) ((∃x(E(x) ∧ P (x))) ∧ (¬(∃x(E(x) ∧ P (x) ∧ (∃y(¬x = y ∧ E(y) ∧ P (y))))))). 3. Jel¨ olje N (), E(), H(), illetve B() azt, hogy ma s¨ ut a nap, ma esik az es˝o, ma havazik, illetve hogy tegnap borult volt az ´eg. Ford´ıtsuk le magyar nyelvre (az u ¨res z´ ar´ ojelek nincsenek ki´ırva): a) (N ⇒ ¬(E ∧ H)); b) (B ⇔ N ); c) (B ∧ (N ∨ E)); e) (N ⇔ ((E ∧ ¬H) ∨ B)); f ) ((N ⇔ E) ∧ (¬H ∨ B)).

d) ((B ⇒ E) ∨ N );

4. Jel¨ olje N (x), F (x), illetve G(x, y) rendre azt, hogy x n˝o, f´erfi, illetve x gyermeke y-nak. Ezek seg´ıts´eg´evel defini´ ald formul´ aval a k¨ ovetkez˝ o kapcsolatokat: x az y-nak fia, l´anya, sz¨ ul˝oje, apja, anyja, unok´aja, nagysz¨ ul˝oje, nagyapja, nagyanyja, apai nagyapja, anyai nagyapja, apai nagyanyja, anyai nagyanyja, testv´ere, fiv´ere, n˝ov´ere, f´eltestv´ere, unokatestv´ere, nagyb´ atyja, unoka¨ occse, unokah´ uga. 5. Jel¨ olje H(x, y) azt, hogy x ´es y h´ azast´ arsak. Ennek, valamint az el˝oz˝o feladat predik´atumai seg´ıts´eg´evel defini´ ald a k¨ ovetkez˝ o kapcsolatokat: x y-nak f´erje, feles´ege, s´og´ora, s´og´orn˝oje, ap´osa, any´osa, veje, menye. 6. Egy t´ ancmulats´ agon fi´ uk ´es l´ anyok t´ ancolnak. Jel¨olje T (L, F ) azt, hogy az L l´any t´ancolt az F fi´ uval. Formaliz´ aljuk pontosan az al´ abbi ”gyors´ır´ assal” fel´ırt formul´ akat. D¨onts¨ uk el, hogy melyik k¨ovetkezik a m´asikb´ol. (Egy formul´ ab´ ol k¨ ovetkezik egy m´ asik formula, ha valah´ anyszor az egyik igaz, akkor a m´asik is.) ∃L∀F T (L, F ), ∃L∃F T (L, F ),

∀F ∃L T (L, F ), ¬∃L∃F T (L, F ),

∃F ∀L T (L, F ), ∀F ∃L ¬T (L, F ),

2

∀L∃F T (L, F ), ∀L∃F ¬T (L, F ),

∀L∀F T (L, F ), ∀L∀F ¬T (L, F ).

3.

Halmazok

1. Legyen A = {p(x) polinom gy¨ okei}, B = {q(x) polinom gy¨okei} ´es r(x) = p(x)q(x). Hogyan fejezhetj¨ uk ki az r(x) polinom gy¨ okeit A-val ´es B-vel? 2. Melyik az az s(x) polinom, melynek gy¨ okei D halmaz´ara D = A∩B, ahol A ´es B az el˝oz˝o feladatban szerepl˝o halmazok? 3. Keress¨ unk olyan A, B, C halmazokat, melyekre egyszerre teljes¨ ulnek a k¨ovetkez˝ok: A ∩ B 6= ∅,

A ∩ C = ∅,

(A ∩ B) \ C = ∅.

4. Bizony´ıtsd be, hogy A ∩ B ⊆ C ⇔ A ⊆ B ∪ C. 5. Adj meg olyan halmazrendszert, mely diszjunkt de nem p´aronk´ent diszjunkt. Van-e olyan halmazrendszer, mely p´ aronk´ent diszjunkt de nem diszjunkt? 6. Legyen A= {{a, b, c}, {a, d, e}, {a, f }}. Mi lesz ∪A ´es ∩A? 7. Hat´ arozd meg a {{x ∈ R : |x| < y} : y ∈ R, y > 0} halmazrendszer uni´oj´at ´es metszet´et. Mi a helyzet, ha y ∈ N, illetve y ∈ Z? 8. Igazoljuk, hogy A 4 ∅ = A,

A 4 A = ∅,

A 4 (B 4 C) = (A 4 B) 4 C,

9. Fejezz¨ uk ki a 4 ´es ∩ seg´ıts´eg´evel a k¨ ovetkez˝ oket: A \ B

´es

A 4 (A 4 B) = B.

A ∪ B.

10. Hozzuk egyszer˝ ubb alakra a k¨ ovetkez˝ o kifejez´est: (A ∪ (A ∩ B) ∪ (A ∩ B ∩ C)) ∩ (A ∪ B ∪ C). 11. Bizony´ıtsuk be, hogy a) A ∩ B = A∪B;

b) A\B = A∩B;

c) A\(B ∩C) = (A\B)∪(A\C);

d) A\(B ∪C) = (A\B)\C.

´ 12. Allap´ ıtsd meg, hogy az al´ abbi ´ all´ıt´ asok k¨ oz¨ ul melyek igazak tetsz˝oleges A, B, C halmazokra: (A ∪ B) \ A = B;

(A ∪ B) \ C = A ∪ (B \ C);

(A \ B) ∩ C = (A ∩ C) \ B = (A ∩ C) \ (B ∩ C).

13. Bizony´ıtsd be a k¨ ovetkez˝ o¨ osszef¨ ugg´est: (A ∩ B ∪ C) ∩ A ∪ B ∪ C = A ∪ B ∪ C. 14. Egyszer˝ us´ıtsd amennyire lehet a k¨ ovetkez˝ oket: A ∪ (B ∩ (C ∪ D)), 15. ´Ird fel a hatv´ anyhalmazt egy-egy 0,1,2, illetve 3-elem˝ u halmazra.

3

(A ∪ B) ∩ (A ∪ B).

4. 4.1.

Rel´ aci´ ok, f¨ uggv´ enyek Fogalmak

Rendezett p´ ar Az (x, y) rendezett p´ ar fogalm´ at u ´gy szeretn´enk defini´alni, hogy (x, y) = (u, v) akkor ´es csak akkor teljes¨ ulj¨ on, ha x = u ´es y = v. (ezt form´ alisan ´ıgy jel¨ olj¨ uk: (x, y) = {{x}, {x, y}}). Az (x, y) rendezett p´ar els˝o koordin´ at´ aja x, a m´ asodik y. Descartes-szorzat Az X, Y halmazok Descartes-szorzat´an az al´abbi halmazt ´ertj¨ uk: X × Y := {(x, y) : x ∈ X, y ∈ Y }. Bin´ er rel´ aci´ ok Egy halmazt bin´er rel´ aci´ o nak nevez¨ unk (vagy k´etv´altoz´os rel´aci´onak), ha minden eleme rendezett p´ ar. Ha R egy bin´er rel´ aci´ o, akkor (x, y) ∈ R helyett gyakran ezt ´ırjuk: xRy, szavakkal x ´es y k¨oz¨ott fenn´all az R rel´aci´o. Legyen most X = Y , valamint R egy bin´er rel´ aci´ o X × X-en. Azt mondjuk, hogy R -tranzit´ıv, ha minden x, y, z-re xRy ´es yRz eset´en xRz teljes¨ ul (pl. <, ≤); -szimmetrikus, ha minden x, y-ra xRy eset´en yRx teljes¨ ul (pl. =); -antiszimmetrikus, ha minden x, y-ra xRy ´es yRx eset´en x = y (pl. ≤); -reflex´ıv, ha minden x-re xRx teljes¨ ul (pl. =); -trichotom, ha minden x, y eset´en x = y, xRy ´es yRx k¨oz¨ ul pontosan egy teljes¨ ul (pl. <). R r´eszben rendez´es, ha tranzit´ıv, antiszimmetrikus ´es reflex´ıv. 1. Az R = {(x, y) ∈ R × R : y 2 = 2 − x − x2 } rel´aci´ora har´arozd meg a {0} halmaz k´ep´et ´es teljes inverz k´ep´et. Mely A ⊂ R halmazokra lesz R(A), illetve R−1 (A) egyelem˝ u? 2. ´Ird fel intervallumokkal az x 7→ |x| lek´epez´esn´el az al´abbi halmazok teljes inverz k´ep´et: [−1, 2], ]1, 4[, [−1, 2[. 3. Legyen az R ⊆ N × N rel´ aci´ o olyan, hogy nRm(n, m ∈ N) igaz, ha n ´es m k¨oz¨os pr´ımoszt´oinak a sz´ ama p´ aros. Vizsg´ aljuk meg R tulajdons´ agait (ti. fenn´ alnak-e a k¨ovetkez˝ok: reflex´ıv, tranzit´ıv, szimmetrikus, antiszimmetrikus, trichot´ om). 4. Keress¨ unk olyan rel´ aci´ ot, amely a) reflex´ıv, de nem tranzit´ıv; b) antiszimmetrikus ´es reflex´ıv; c) antiszimmetrikus ´es nem tranzit´ıv; d) nem reflex´ıv, nem tranzit´ıv; e) nem tranzit´ıv, de trichot´om; f ) semmi (nem reflex´ıv, nem tranzit´ıv, nem szimmetrikus, nem antiszimmetrikus, nem trichot´om). 5. Adj p´eld´ at olyan rel´ aci´ ora, amely a) reflex´ıv ´es szimmetrikus, de nem tranzit´ıv; c) tranzit´ıv ´es szimmetrikus, de nem reflex´ıv.

b) reflex´ıv ´es tranzit´ıv, de nem szimmetrikus;

6. Az emberek halmaz´ an tekintve milyen tulajdons´agokkal rendelkeznek az apja, sz¨ ul˝oje, anyja, testv´ere, f´eltestv´ere, gyermeke, nagysz¨ ul˝ oje, unok´ aja, nagyapja, nagyanyja, anyai nagysz¨ ul˝oje, egyenes´agi lesz´armazottja, egyenes´ agi rokona rel´ aci´ ok? 7. Defini´ aljunk Z-n k´et rel´ aci´ ot az al´ abbi m´ odon, ´es vizsg´aljuk R1 ´es R2 tulajdons´agait (ti. fenn´alnak-e a k¨ ovetkez˝ ok: reflex´ıv, tranzit´ıv, szimmetrikus, antiszimmetrikus, trichot´om). a) xR1 y, ha x2 + y 2 oszthat´ o 2-vel; b) xR2 y, ha x2 − y 2 oszthat´o 2-vel. 8. Mutasd meg, hogy ha % ´es σ szimmetrikus rel´ aci´ok S-en akkor a k¨ovetkez˝ok ekvivalensek: a) % ◦ σ szimmetrikus b) % ◦ σ = σ ◦ % 9. Hat´ arozd meg az S ◦ R ´es R ◦ S szorzatot, ha a) R = {(x, y) ∈ R × R : y 2 = x} ´es S = {(x, y) ∈ R × R : y = 2x}; b) R = {(x, y) ∈ R+ × R : y 3 = x} ´es S = {(x, y) ∈ R × R : y = tan x}; c) R = {(x, y) ∈ [−π, π] × R : y = sin x} ´es S = {(x, y) ∈ R × R : y + 1/y = x}; d) R = S = {(x, y) ∈ R × R : x < y} ; e) R = S = {(x, y) ∈ Z × Z : x < y}; f ) R = S = {(x, y) ∈ N+ × N+ : x osztja y − t, de x 6= y}; g) K ´es L k´et k¨ orlap a P s´ıkban ´es R = {(x, y) ∈ P × P : x = y vagy x, y ∈ K} ´es S = {(x, y) ∈ P × P : x = y vagy x, y ∈ L}. 10. N × N-en defini´ aljunk egy R rel´ aci´ ot a k¨ ovetkez˝ok´eppen: (m1 , n1 )R(m2 , n2 ), ha m1 ≤ m2 ´es n1 ≤ n2 . Mutassuk meg, hogy R r´eszbenrendez´es. 11. Mutassuk meg, hogy az el˝ oz˝ o feladatban az R rel´aci´oval az N×N r´eszben rendezett halmaz minden nem¨ ures r´eszhalmaz´ anak van minim´ alis eleme. Hogyan kereshetj¨ uk meg? 12. Mutasd meg, hogy ha egy r´eszbenrendezett halmazban x < y ´es y ≤ z, akkor x < z. 4

13. Bizony´ıtsd be, hogy egy r´eszbenrendezett halmaz b´armely nem u ¨res r´eszhalmaz´anak b´armely als´o korl´atja kisebb vagy egyenl˝ o b´ armely fels˝ o korl´ atj´ an´ al. 14. Tekints¨ uk az {1, 2, 3, 4, 5, 6, 7, 8} halmazon az ”oszt´oja” r´eszbenrendez´est. A megfelel˝o szigor´ u rel´aci´ot ´ırjuk fel p´ arok halmazak´ent. Keress¨ unk intervallumokat, r´eszhalmazokra als´o ´es fels˝o korl´atokat, infimumot, szupr´emumot. 15. Legyen H ⊂ R. A H halmaz milyen tulajdons´ ag´at fejezik ki a k¨ovetkez˝o formul´ak: a) ∀x ∈ R ∃y ∈ H (x < y); b) ∃x ∈ R ∀y ∈ H (x < y); c) ∀x ∈ H ∃y ∈ R (x < y);

d) ∀x ∈ H ∃y ∈ H (x < y)

F¨ uggv´ eny A f¨ uggv´eny (vagy lek´epez´es) egy olyan f rel´aci´o, melyre, ha (x, y) ∈ f ´es (x, y 0 ) ∈ f , akkor y = y 0 . Magyarul minden x-hez legfeljebb egy olyan y l´etezik, melyre (x, y) ∈ f . Az y elemet az f f¨ uggv´eny x helyen felvett ´ert´ek´enek nevezz¨ uk ´es a szok´ asos m´ odon jel¨ olj¨ uk: f (x) = y (esetleg f : x 7→ y). Az f f¨ uggv´enyt injekt´ıvnek (magyarul k¨ olcs¨ on¨ osen egy´ertelm˝ unek) nevezz¨ uk, ha f (x) = y ´es f (x0 ) = y eset´en x = x0 . Ezt u ´gy is fogalmazhatjuk, hogy k¨ ul¨ onb¨ oz˝ o elemek k´epe k¨ ul¨onb¨oz˝o. Egy f : X 7→ Y f¨ uggv´enyt sz¨ urjekt´ıvnek nevez¨ unk, ha minden y ∈ Y elemhez l´etezik egy x ∈ X, hogy f (x) = y, magyarul az eg´esz Y el˝ o´ all az f k´epek´ent. Ha f injekt´ıv ´es sz¨ urjekt´ıv is, akkor bijekt´ıvnek mondjuk. 16. Adj p´eld´ at olyan f¨ uggv´enyre, amely a) N-et N val´ odi r´esz´ere k´epezi le, de nem injekt´ıv; b) N-et N val´odi r´esz´ere k´epezi le ´es injekt´ıv; c) Z-t Z val´ odi r´esz´ere k´epezi le, de nem injekt´ıv; d) Z-t Z val´odi r´esz´ere k´epezi le ´es injekt´ıv; e) R-et N-be k´epezi le; f ) R-et N-be k´epezi le, de egyik elem k´epe sem saj´ at maga. 17. Legyen A = {a nem negat´ıv eg´eszek}, B = {p´ aros sz´amok}. Konstru´alj bijekt´ıv lek´epez´est az A ´es B halmazok k¨ oz¨ ott. 18. Konstru´ aljunk bijekt´ıv lek´epez´est k´et tetsz˝ oleges s´ıkbeli szakasz k¨oz¨ott. 19. F¨ uggv´eny-e a k¨ ovetkez˝ o rel´ aci´ o? R ⊆ A × A, ahol A = { a s´ıkbeli egyenesek}; aRb, ha a ´es b egyenesek ´ altal bez´ art (a kisebb) sz¨ og 60◦ : Vizsg´ aljuk a fenti rel´aci´o tulajdons´agait (ti. fenn´alnak-e a k¨ovetkez˝ok: reflex´ıv, tranzit´ıv, szimmetrikus). 20. Legyen A = {olyan egyenl˝ osz´ ar´ u h´ aromsz¨ ogek, amelyeknek az alaphoz tartoz´o magass´aguk egyenl˝o egy r¨ogz´ıtett m > 0 sz´ ammal}, B = {y : y > 0, y val´ os}. Defini´ aljuk az R ⊆ A × B rel´aci´ot a k¨ovetkez˝ok´eppen: aRb, a ∈ A, b ∈ B, ha az a h´ aromsz¨ og ter¨ ulete b. Mutassuk meg, hogy R f¨ uggv´eny, ´es vizsg´aljuk ennek a f¨ uggv´enynek a tulajdons´ agait (ti. fenn´ alnak-e a k¨ ovetkez˝ ok: sz¨ urjekt´ıv, injekt´ıv, bijekt´ıv). 21. Legyenek f : X → Y, g : Y → Z lek´epez´esek. Mutasd meg, hogy a) ha f, g injekt´ıv, akkor f ◦ g injekt´ıv; b) ha f, g sz¨ urjekt´ıv, akkor f ◦ g sz¨ urjekt´ıv; bijekt´ıv.

c) ha f, g bijekt´ıv, akkor f ◦ g

22. Hat´ arozd meg az al´ abbi rel´ aci´ ok ´ertelmez´esi tartom´any´at, ´ert´ekk´eszlet´et, d¨ontsd el, hogy f¨ uggv´eny-e ´es hogy az inverze f¨ uggv´eny-e: a) {(x, y) ∈ R2 : a < x < b, x < y < 2x}, ahol a, b ∈ R adott sz´amok; b) {(x, y) ∈ R2 : y(1 − x2 ) = x − 1}; c) {(x, y) ∈ R2 : y = (x − 1)/(1 − x2 )}; 2 d) {(x, y) ∈ R : |x| + |y| ≤ 1}; e) {(x, y) ∈ R2 : x2 = 1 + y 2 , y > 0}; 2 2 2 f ) {(x, y) ∈ R : x + y − 2y < 0}; g) {(x, y) ∈ R2 : |x| = |y|}; h) {(x, y) ∈ R2 : y(bxc − 2) = 1}; 2 2 2 i) {(x, y) ∈ R : y = x − bxc}; j) {(x, y) ∈ R : y = bx c}; k) {(x, y) ∈ R2 : y = x2 }; 2 4 l) {(x, y) ∈ R : y = x , 0 < x < 2}. 23. Mutasd meg, hogy Y X = ∅ pontosan akkor teljes¨ ul, ha Y = ∅ ´es X 6= ∅. 24. Hat´ arozd meg X Y ¨ osszes elem´et, ha X-nek, illetve Y -nak nulla, egy, kett˝o illetve h´arom eleme van. Melyek lesznek invert´ alhat´ oak?

5.

Elemi kombinatorika

´ 1. Az ¨ osszes lehets´eges m´ odon kit¨ olt¨ unk TOTO-szelv´ enyeket. H´any szelv´enyt t¨olt¨ott¨ unk ki? 2. Egy dobozban 10 piros, 20 feh´er ´es 40 z¨ old goly´o van, ezekb˝ol h´ uzunk. H´anyat kell h´ uznunk ahhoz, hogy a) feh´er; b) 3 k¨ ul¨ onb¨ oz˝ o sz´ın˝ u; c) 3 azonos sz´ın˝ u; d) 5 azonos sz´ın˝ u; e) 15 azonos sz´ın˝ u; f ) k´et egym´ as ut´ ani z¨ old h´ uz´ as legyen? 3. Egy fut´ oversenyen 25-en indulnak. H´ anyf´ele sorrendben ´erhetnek c´elba (ha mondjuk nincs holtverseny ´es mindenki c´elba´er)? 5

4. Mekkora az a minim´ alis oszt´ alyl´etsz´ am, ahol biztosan teljes¨ ul, hogy a) van n´egy di´ ak, aki ugyanabban a h´ onapban sz¨ uletett; b) minden h´onapban van 3-3 sz¨ ulet´esnap? 5. Legfeljebb h´ any term´eszetes sz´ am adhat´ o meg u ´gy, hogy semelyik kett˝o k¨ ul¨onbs´ege ne legyen oszthat´o nyolccal? 6. Mutasd meg, hogy a π, 2π, 3π, . . . , 100π sz´ amok k¨oz¨ott van olyan, amelyik nincs messzebb a legk¨ozelebbi eg´eszt˝ ol, mint ´ 1/101. Altal´ anos´ıtsd az ´ all´ıt´ ast. 7. Bizony´ıtsd be, hogy b´ armely m ∈ N+ -hoz van olyan n ∈ N+ , hogy t´ızes sz´amrendszerben mn minden sz´ amjegye 0 vagy 1. ´ kell kit¨ 8. H´ any TOTO-t olten¨ unk ahhoz, hogy legyen olyan szelv´eny¨ unk, amin legal´abb 5 tal´alatunk van? 9. H´ any r´eszhalmaza van az {1, 2, .., 20} halmaznak? H´any r´eszhalmaz´ara teljes¨ ul, hogy a) az 1 benne van; b) 1 ´es 2 is benne van; c) 1, vagy 2 benne van? 10. H´ any hatjegy˝ u sz´ amra igaz, hogy a) a szomsz´edos sz´ amjegyei k¨ ul¨ onb¨ oznek; k¨ oz¨ ott?

b) minden jegye k¨ ul¨onb¨oz˝o;

c) pontosan egy jegye 0, d) van 0 a jegyei

11. H´ any olyan sorrendje van az 1, 2, . . . , n sz´ amoknak, melyben az 1 ´es a 2 nem lehetnek szomsz´edosak? 12. H´ anyf´elek´eppen lehet a MISSISSIPPI sz´ o bet˝ uit le´ırni u ´gy, hogy a n´egy S bet˝ u ne ker¨ ulj¨on egym´as mell´e? 13. Az (a + b)22 kifejt´es´eben mi az egy¨ utthat´ oja az a14 b8 -nak, valamint az a17 b5 -nek? 14. H´ any u ´t vezet a 3 × 10-es sakkt´ abla bal als´ o sark´ab´ol a jobb fels˝obe, ha csak fel, jobbra, vagy jobbra-fel ´ atl´ osan l´ephet¨ unk? 15. Adott a s´ıkon k´et p´ arhuzamos egyenes, az egyiken p darab, a m´asikon q darab pont. H´any olyan h´aromsz¨ og van, melynek cs´ ucsai az adott pontok k¨ oz¨ ul val´ ok? 16. Jel¨ olj¨ uk Ckn -val az xn−k y k egy¨ utthat´ oj´ at az (x+y)n kifejez´esben! Ezen sz´amokb´ol k´esz¨ ul a Pascal-h´ aromsz¨ og. Adjuk ossze a Pascal-h´ ¨ aromsz¨ og n-edik sor´ anak elemeit! Mit kapunk? Adjuk ¨ossze a Pascal-h´aromsz¨og n-edik sor´anak elemeit most v´ altakoz´ o el˝ ojellel! Most mit kapunk? 17. H´ any null´ ara v´egz˝ odik a 11100 − 1 sz´ am? 18. Mutasd meg, hogy megadhat´ o k´et k¨ ul¨ onb¨ oz˝ o term´eszetes sz´am, n ´es k u ´gy, hogy 2n − 2k oszthat´o legyen 711-gyel! 19. Egy bolha ugr´ al az egyenes eg´esz pontjain jobbra-balra, m´asodpercenk´ent egyet. Ha az orig´ob´ol indul ´es egy percig ugr´ al, h´ anyf´elek´eppen tud eljutni a +24 pontba? 20. H´ anyf´elek´eppen lehet felbontani, ha a sorrend sz´am´ıt a) a 100-at 7 pozit´ıv eg´esz sz´ am ¨ osszeg´ere; b) a 200-at 12 term´eszetes sz´am ¨osszeg´ere; melyben csak 1 ´es 2 szerepel?

c) a 12-t olyan ¨ osszegre,

21. H´ any olyan sz´ am van ¨ osszesen (ak´ arh´ anyjegy˝ u lehet), melyben a sz´amjegyek balr´ol jobbra olvasva a) szigor´ uan monoton n¨ ovekedve; b) szigor´ uan monoton cs¨ okkenve k¨ovetik egym´ast? 22. Egy oszt´ aly 30 tanul´ oja k¨ oz¨ ul a matekot 12, a matekot ´es a fizik´at 5, a fizik´at 14, a matekot ´es a k´emi´at 4, a k´emi´ at 13, a fizik´ at ´es a k´emi´ at 7, mindh´ armat 3 szereti. H´anyan vannak, akik semelyiket nem kedvelik?






n n 23. Bizony´ıtsd be, hogy a)) n+1 b) 44 + 54 + · · · + n4 = n+1 k+1 = k + k+1 ; 5 . 24. Egy 25 f˝ os oszt´ alyban k¨ uld¨ otts´eget v´ alasztanak, mely 6 f˝ob˝ol ´all, majd ezen hat emberb˝ol egy-egy igazgat´ot ´es titk´ art v´ alasztanak. H´ anyf´elek´eppen t¨ ort´enhet ez, ha egy ember csak egy tiszts´eget viselhet?


25. Hozd min´el egyszer˝ ubb alakra az al´ abbi kifejez´est: 1 n1 + 2 n2 + · · · + n nn . ´ ha mindenki kap biztosan 26. H´ anyf´elek´eppen lehet n darab egyforintos ´erm´et sz´etosztani k ember k¨oz¨ott sz´etosztani? Es legal´ abb egy forintot? 27. A cukr´ aszd´ aban ¨ otf´ele s¨ utem´enyt ´ arulnak: l´ udl´ abat, geszteny´es kock´at, dobostort´at, minyont ´es fat¨orzset. Mindegyikb˝ ol van m´eg legal´ abb 20. H´ anyf´elek´eppen ehet¨ unk meg h´armat, ha a) sz´am´ıt a sorrend, b) nem?

6

´ h´any olyan 1000-n´el kisebb, mely 28. H´ any 100-n´ al kisebb term´eszetes sz´ am van, mely 2,3 ´es 5 egyik´evel sem oszthat´o? Es 2,3,5 ´es 7 egyik´evel sem oszthat´ o? Szita formula: adott egy A halmaz P ´es annakP n r´eszhalmaza:PA1 , A2 , . . . , An . Ekkor A azon elemeinek sz´ama, melyek egyik Ai -ben sincsenek benne, |A| − |Ai | + |Ai ∩ Aj | − |Ai ∩ Aj ∩ Ak | + · · · + (−1)n |A1 ∩ · · · ∩ An |. 29. H´ anyf´elek´eppen lehet 100 rekeszben 30 goly´ ot elhelyezni u ´gy, hogy minden rekeszben, amelyikben van goly´ o, pontosan 6 darab van ´es a) a goly´ ok egyform´ ak; b) a goly´ok k¨ ul¨onb¨oz˝oek, ´es minden rekeszben figyelembe vessz¨ uk a goly´ ok sorrendj´et; c) a goly´ ok k¨ ul¨ onb¨ oz˝ oek, de a rekeszben nem vessz¨ uk figyelembe a goly´ok sorrendj´et? 30. Egy 2x12-es sakkt´ abla h´ anyf´elek´eppen fedhet˝ o le 2x1-es domin´okkal (melyeket v´ızszintesen ´es f¨ ugg˝olegesen tehet¨ unk le)? 31. Az 52 lapos francia k´ arty´ aban n´egy sz´ın mindegyik´eb˝ol 13-13 darab van, minden sz´ınb˝ol egy ´asz van. N´egy j´ at´ekosnak osztunk 13-13 lapot. H´ any k¨ ul¨ onb¨ oz˝ o leoszt´ as van? H´any olyan, amikor mindenkinek van ´asza? H´any olyan, amikor minden ´ asz egyvalakin´el van? 32. H´ anyf´elek´eppen lehet sorbarendezni n null´ at ´es k egyest u ´gy, hogy k´et egyes ne ker¨ ulj¨on egym´as mell´e? ¨ lovagot kell 33. Art´ ur kir´ aly Kerekasztal´ an´ al 12 lovag u ¨l. Mindegyik¨ uk haragban van a k¨ozvetlen¨ ul mellette u ¨l˝okkel. Ot kiv´ alasztani, akik kiszabad´ıtj´ ak a kir´ alyl´ anyt. H´anyf´elek´eppen tehetj¨ uk meg ezt u ´gy, hogy ne legyenek ellens´egek a ´ ha n lovagb´ lovagok k¨ oz¨ ott? Es ol kell k-t kiv´ alasztani?

6.

Sz´ amelm´ elet

´ 1. Allap´ ıtsd meg, milyen marad´ekot adnak a term´eszetes sz´amok n´egyzetei 3-mal ´es 5-tel osztva. 2. Igaz-e, hogy minden 3-n´ al nagyobb p pr´ımnek van 6-tal oszthat´o szomsz´edja? 3. Bizony´ıtsd be, hogy n5 − 5n3 + 4n oszthat´ o 120-szal. (n tetsz˝oleges eg´esz sz´am.) 4. Bizony´ıtsd be, hogy 665|36n − 26n . 5. Bizony´ıtsd be, hogy ¨ ot egym´ ast k¨ ovet˝ o eg´esz sz´am n´egyzet´enek az ¨osszege nem n´egyzetsz´am. 6. Bizony´ıtsuk be, hogy 30 oszt´ oja az mn(m4 − n4 ) sz´amnak, b´armilyen m, n eg´esz sz´am eset´en. 7. A szult´ an 100 cell´ aj´ aban sz´ az rab raboskodik. A szult´an lek¨ uldi egym´as ut´an 100 ember´et. A k-adik alkalommal lek¨ uld¨ ott ember minden k-adik cella z´ arj´ an ´ all´ıt egyet, ha nyitva volt, bez´arja, ha z´arva volt, akkor kinyitja. Kezdetben minden cella z´ arva volt. Mely sorsz´ am´ u cell´ ak lesznek a v´eg´en nyitva? 8. Mi a sz¨ uks´eges ´es el´egs´eges felt´etele annak, hogy egy n term´eszetes sz´amnak ugyanannyi p´aros oszt´oja legyen, mint ah´ any p´ aratlan? 9. Az euklideszi algoritmussal sz´ am´ıtsd ki az al´ abbi sz´amp´arok legnagyobb k¨oz¨os oszt´oj´at, ´es add meg a legkisebb k¨ oz¨ os t¨ obbsz¨ or¨ os¨ uket is. a) a = 86, b = 31; b) a = 139, b = 102; c) a = 255, b = 111; d) a = 332, b = 88. 10. Oldd meg az al´ abbi diofantikus egyenleteket: a) 172x + 62y = 38; b) 82x + 22y = 34; c) 450x + 86y = 100; 11. Oldd meg az al´ abbi kongruenci´ akat: a) 21x ≡ 14 (mod 35); b) 172x ≡ 6 (mod 62);

d) 125x + 45y = −20.

c) 3x ≡ 8 (mod 13);

d) 12x ≡ 9 (mod 18).

12. Keresd meg a k¨ ovetkez˝ o egyenletek eg´esz megold´asait kongruenci´ak felhaszn´al´as´aval: a) 84x+37y = 2; 3.

b) 41x+30y =

13. Bontsd fel 463-at k´et term´eszetes sz´ am ¨ osszeg´ere u ´gy, hogy az egyik sz´am oszthat´o legyen 14-gyel, a m´asik 23-mal. Oldjuk meg a feladatot kongruenci´ ak seg´ıts´eg´evel. 14. Oldd meg a k¨ ovetkez˝ o kongruencia-rendszert: 5x ≡ 3 (mod 7) 3x ≡ 7 (mod 8). 15. Oldd meg a x ≡ 2 (mod x ≡ 3 (mod x ≡ 1 (mod

k¨ ovetkez˝ o kongruencia-rendszert: 3) 4) 5). 7

16. Oldd meg a k¨ ovetkez˝ o kongruencia-rendszert: 4x ≡ 2 (mod 3) 3x ≡ 2 (mod 7) 9x ≡ 7 (mod 11).

8