Diszkr´ et matematika 1. k¨ oz´ epszint
Diszkr´et matematika 1. k¨oz´epszint 8. el˝ oad´as
Nagy G´abor
[email protected] [email protected] compalg.inf.elte.hu/∼ nagy M´erai L´aszl´ o di´ai alapj´an Komputeralgebra Tansz´ ek
2017. ˝ osz
2017. ˝ osz
1.
Kombinatorika
Diszkr´ et matematika 1. k¨ oz´ epszint
2017. ˝ osz
Polinomi´alis t´etel P´elda Mennyi lesz? (x + y + z)2 = x 2 + y 2 + z 2 + 2xy + 2xz + 2yz.
(x + y + z)3 = . . .
T´etel r , n ∈ N eset´en (x1 + x2 + . . . + xr )n =
X i1 +i2 +...+ir =n
n! x i1 · x i2 · . . . · xrir . i1 ! · i2 ! · . . . · ir ! 1 2
Bizony´ıt´as (x1 + x2 + . . . + xr )n = (x1 + x2 + . . . + xr )(x1 + x2 + . . . + xr ) · · · (x1 + x2 + . . . + xr ). Az ! x1i1 x2i2 . . . ! utthat´ oja: xrir egy¨ ! !
n − i1 − i 2 n − i1 − i2 − . . . − ir −1 ··· = i3 ir (n − i1 )! (n − i1 − i2 − . . . − ir −1 )! n! n! ··· = i1 !(n − i1 )! i2 !(n − i1 − i2 )! ir !(n − i1 − . . . − ir −1 − ir )! i1 ! · i2 ! · · · ir ! n i1
n − i1 i2
2.
Kombinatorika
Diszkr´ et matematika 1. k¨ oz´ epszint
Polinomi´alis t´etel (x1 + x2 + . . . + xr )n =
X i1 +i2 +...+ir =n
n! x i1 x i2 · · · xrir i1 !i2 ! · · · ir ! 1 2
(x + y + z)3 = . . . i1
i2
i3
3
0
0
2
1
0
2
0
1
1
2
0
1
1
1
1
0
2
0
3
0
0
2
1
0
1
2
0
0
3
3! i1 !i2 !i3 ! 3! 3!0!0! = 3! 2!1!0! = 3! 2!0!1! = 3! 1!2!0! = 3! 1!1!1! = 3! 1!0!2! = 3! 0!3!0! = 3! 0!2!1! = 3! 0!1!2! = 3! 0!0!3! =
(x + y + z)3 = 1
x3
3
+3x 2 y
3
+3x 2 z
3
+3xy 2
6
+6xyz
3
+3xz 2
1
+y 3
3
+3y 2 z
3
+3yz 2
1
+z 3
2017. ˝ osz
3.
Kombinatorika
Diszkr´ et matematika 1. k¨ oz´ epszint
2017. ˝ osz
Skatulya-elv Skatulya-elv Ha n darab gyuf´asdobozunk ´es n + 1 gyufasz´alunk van, akkor ak´arhogyan rakjuk bele az ¨osszes gyuf´at a skatuly´akba, valamelyikben legal´abb kett˝o gyufa lesz.
P´elda Nyolc ember k¨oz¨ ul van legal´abb kett˝ o, aki a h´et ugyanazon napj´an sz¨ uletett. Az A = {1, 2, 3, 4, 5, 6, 7, 8} halmazb´ ol b´arhogyan v´alasztunk ki ¨ot¨ot, akkor lesz k¨oz¨ ul¨ uk kett˝o, melyek ¨ osszege 9. Tekints¨ uk az {1, 8}, {2, 7}, {3, 6}, {4, 5} halmazokat. Ekkor a kiv´alasztott ¨ot elem k¨oz¨ ul lesz kett˝ o, melyek azonos halmazban lesznek, ´ıgy ¨osszeg¨ uk 9.
4.
Kombinatorika
Diszkr´ et matematika 1. k¨ oz´ epszint
2017. ˝ osz
Szita m´odszer H´any olyan 1000-n´el kisebb pozit´ıv eg´esz sz´am van, amely nem oszthat´o sem 2-vel, sem 3-mal, sem 5-tel? Az 1000-n´el kisebb sz´amok ¨osszes 999 999 999 2-vel oszthat´o − 499 2 = 499 999 3-mal oszthat´o − 333 3 = 333 999 5-tel oszthat´o − 199 5 = 199 999 2 · 3-mal oszthat´o = 166 + 166 2·3 999 2 · 5-tel oszthat´o = 99 + 99 2·5 999 3 · 5-tel oszthat´o = 66 + 66 3·5 999 2 · 3 · 5-tel oszthat´o = 33 − 33 2·3·5 = 266
5.
Kombinatorika
Diszkr´ et matematika 1. k¨ oz´ epszint
2017. ˝ osz
Szita m´odszer T´etel Legyenek A1 , A2 , . . . , An v´eges halmazok. Ekkor Sn Pn P P i=1 Ai = i=1 |Ai | − i<j |Ai ∩ Aj | + i<j
P´elda H´any olyan 1000-n´el kisebb sz´am van, amely nem oszthat´o sem 2-vel, sem 3-mal, sem 5-tel? El˝osz¨or: H´any olyan 1000-n´el kisebb sz´am van, amely oszthat´o 2-vel vagy 3-mal vagy 5-tel?
A1 = {1 ≤ n ≤ 999 : 2|n} → A2 = {1 ≤ n ≤ 999 : 3|n} → A3 = {1 ≤ n ≤ 999 : 5|n}→
|A1 | = 999 ; 2 |A2 | = 999 ; 3 999 |A 3| = 5 .
999 999 Hasonl´oan |A1 ∩ A2 | = 999 2·3 , |A1 ∩ A3 | = 2·5 , |A2 ∩ A3 | = 3·5 , 999 |A1 ∩ A2 ∩ A3 | = 2·3·5 . 2-vel vagy 3-mal vagy 5-tel oszthat´ o sz´amok sz´ama: 999 999 999 999 999 999 999 + 3 + 5 − 2·3 − 2·5 − 3·5 + 2·3·5 . 2
6.
Kombinatorika
Diszkr´ et matematika 1. k¨ oz´ epszint
´ anos szita formula Altal´ T´etel Legyenek A1 , . . . , An az A v´eges halmaz r´eszhalmazai, f : A → R tetsz˝ oleges f¨ uggv´eny. Legyenek X S= f (x); x∈A
X
Sr =
X
f (x);
0
X
S0 =
x∈A\
f (x).
Sn
i=1 Ai
Ekkor S0 = S − S1 + S2 − S3 ± . . . + (−1)n Sn .
P´elda A = {1, 2, . . . , 999}, A1 = {n : 1 ≤ n < 1000, 2 | n}, A2 = {n : 1 ≤ n < 1000, 3 | n}, A3 = {n : 1 ≤ n < 1000, 5 | n}, f (x) = 1. S0 : 2-vel, 3-mal, 5-tel nem oszthat´ o 1000-n´el kisebb sz´amok sz´ama.
2017. ˝ osz
7.
Kombinatorika
Diszkr´ et matematika 1. k¨ oz´ epszint
2017. ˝ osz
´ anos szita formula bizony´ıt´asa Altal´ n S0 = S −X S1 + S2 − S3 ± . . . + X(−1) Sn : S0 = f (x), S = f (x) x∈A\
Sr =
Sn
Ai
i=1 X
x∈A
X
f (x)
0
Bizony´ıt´as Sn Ha x ∈ A Sn\ i=1 Ai , akkor f (x) mindk´et oldalon egyszer szerepel. Ha x ∈ i=1 Ai , legyenek Aj1 , . . . , Ajt azon r´eszhalmazok, melyeknek x eleme.X Ekkor f (x) a X bal oldalon nem szerepel. Jobb oldalon a f (x) 0
¨osszegben szerepel, ha {i1 , . . . , ir } ⊆ {j1 , . . . , jt }. Ilyen r elem˝ u indexhalmaz rt darab van. ´Igy f (x) egy¨ utthat´ oja t X t (−1)r = 0 (Biz.: gyakorlaton). r r =0
8.
Kombinatorika
Diszkr´ et matematika 1. k¨ oz´ epszint
2017. ˝ osz
V´eges halmazok Defin´ıci´o Az X ´es Y halmazokat ekvivalensnek nevezz¨ uk, ha l´etezik f : X → Y bijekci´o. Jel¨ol´ese: X ∼ Y .
´ ıt´as All´ Ha n term´eszetes sz´am, akkor {1, 2, . . . n} nem ekvivalens egyetlen val´odi r´eszhalmaz´aval sem.
Defin´ıci´o Egy X halmazt v´egesnek nevez¨ unk, ha valamely n ∈ N eset´en ekvivalens az {1, 2, . . . n} halmazzal, egy´ebk´ent v´egtelennek nevezz¨ uk. Azt az egy´ertelm˝ uen meghat´arozott term´eszetes sz´amot, amire egy adott X halmaz ekvivalens az {1, 2, . . . , n} halmazzal, az X sz´amoss´ag´anak nevezz¨ uk, jel¨ol´ese: |X | (esetleg card(X ), \(X ), #(X ).
9.
Kombinatorika
Diszkr´ et matematika 1. k¨ oz´ epszint
2017. ˝ osz
V´eges halmazok T´etel Legyenek X ´es Y halmazok. Ekkor 1
ha X v´ eges, ´ es Y ⊆ X , akkor Y is v´ eges, ´ es |Y | ≤ |X |;
2
ha X v´ eges, ´ es Y ( X , akkor |Y | < |X |;
3
ha X ´ es Y v´ egesek ´ es diszjunktak, akkor X ∪ Y is v´ eges, ´ es |X ∪ Y | = |X | + |Y |;
4
ha X ´ es Y v´ egesek, akkor |X ∪ Y | + |X ∩ Y | = |X | + |Y |;
5
ha X ´ es Y v´ egesek, akkor X × Y is v´ eges, ´ es |X × Y | = |X | · |Y |;
6
ha X v´ eges, akkor 2X is v´ eges, ´ es |2X | = 2|X | .
´ ıt´as (Skatulyaelv) All´ Ha X ´es Y v´eges halmazok, ´es |X | > |Y |, akkor egy f : X → Y f¨ uggv´eny nem lehet injekt´ıv.
10.
Elemi sz´ amelm´ elet
Diszkr´ et matematika 1. k¨ oz´ epszint
2017. ˝ osz
Oszthat´os´ag Ha a ´es b racion´alis sz´amok (b 6= 0), akkor az a/b oszt´as mindig elv´egezhet˝o (´es az eredm´eny szint´en racion´alis). Ha a ´es b eg´esz sz´amok, az a/b oszt´as nem mindig v´egezhet˝o el (a h´anyados nem felt´etlen¨ ul lesz eg´esz).
Defin´ıci´o Az a eg´esz osztja a b eg´eszet (b oszthat´ o a-val): a | b, ha l´etezik olyan c eg´esz, mellyel a · c = b (azaz a 6= 0 eset´en b/a szint´en eg´esz). P´eld´ak 1 | 13, mert 1 · 13 = 13; 1 | n, mert 1 · n = n; 6 | 12, mert 6 · 2 = 12; −6 | 12, mert (−6) · (−2) = 12. A defin´ıci´o kiterjeszthet˝o p´eld´aul a Gauss-eg´eszekre: {a + bi : a, b ∈ Z}. P´eld´ak i | 13, mert i · (−13i) = 13; 1 + i | 2, mert (1 + i) · (1 − i) = 2.
11.
Elemi sz´ amelm´ elet
Diszkr´ et matematika 1. k¨ oz´ epszint
2017. ˝ osz
Oszthat´os´ag tulajdons´agai ´ ıt´as (HF) All´ Minden a, b, c, . . . ∈ Z eset´en 1 a | a; 2 a | b ´es b | c ⇒ a | c; 3 a | b ´es b | a ⇒ a = ±b; 4 a | b ´es a0 | b 0 ⇒ aa0 | bb0 ; 5 a | b ⇒ ac | bc; 6 ac | bc ´es c 6= 0 ⇒ a | b; 7 a | b1 , . . . , bk ⇒ ⇒a | c1 b1 + . . . + ck bk ; 8 a | 0, ui. a · 0 = 0; 9 0 | a ⇔ a = 0; 10 1 | a ´ es −1 | a;
P´eld´ak 1 2 3 4 5 6 7
6 | 6; 2 | 6 ´es 6 | 12 ⇒ 2 | 12; a | 3 ´es 3 | a ⇒ a = ±3; 2 | 4 ´es 3 | 9 ⇒ 2 · 3 | 4 · 9; 3 | 6 ⇒ 5 · 3 | 5 · 6; 3 · 5 | 6 · 5 ´es 5 6= 0 ⇒ 3 | 6; 3 | 6, 9 ⇒ 3 | 6c1 + 9c2
12.
Elemi sz´ amelm´ elet
Diszkr´ et matematika 1. k¨ oz´ epszint
2017. ˝ osz
Egys´egek Defin´ıci´o Ha egy ε sz´am b´armely m´asiknak oszt´ oja, akkor ε-t egys´egnek nevezz¨ uk.
´ ıt´as All´ Az eg´esz sz´amok k¨or´eben k´et egys´eg van: 1, −1.
Bizony´ıt´as A ±1 nyilv´an egys´eg. Megford´ıtva: ha ε egys´eg, akkor 1 = ε · q valamely q eg´esz sz´amra. Mivel |ε| ≥ 1, |q| ≥ 1 ⇒ |ε| = 1, azaz ε = ±1.
P´elda A Gauss-eg´eszek k¨or´eben az i is egys´eg: a + bi = i(b − ai). Megjegyz´es Pontosan 1 oszt´oi az egys´egek.
13.
Elemi sz´ amelm´ elet
Diszkr´ et matematika 1. k¨ oz´ epszint
2017. ˝ osz
Asszoci´altak Oszthat´os´ag szempontj´ab´ ol nincs k¨ ul¨ onbs´eg a 12 ill. −12 k¨oz¨ott.
Defin´ıci´o K´et sz´am asszoci´alt, ha egym´as egys´egszeresei.
Megjegyz´es a ´es b pontosan akkor asszoci´alt, ha a | b ´es b | a.
Bizony´ıt´as =⇒: Ha b = εa ´es a = ε0 b, ahol ε, ε0 egys´egek, akkor a|b ´es b|a nyilv´anval´o. ⇐=: Legyen b = ab1 ´es a = ba1 . Ekkor b = ab1 = ba1 b1 , ´ıgy a1 b1 = 1, vagyis a1 ´es b1 is egys´egek.
Defin´ıci´o Egy sz´amnak az asszoci´altjai ´es az egys´egek a trivi´alis oszt´oi.
14.
Elemi sz´ amelm´ elet
Diszkr´ et matematika 1. k¨ oz´ epszint
2017. ˝ osz
Pr´ımek, felbonthatatlanok Defin´ıci´o Ha egy nem-nulla, nem egys´eg sz´amnak a trivi´alis oszt´ oin k´ıv¨ ul nincs m´as oszt´oja, akkor felbonthatatlannak (irreducibilisnek) nevezz¨ uk.
P´elda 2, −2, 3, −3, 5, −5 felbonthatatlanok. P´elda 6 nem felbonthatatlan, mert 6 = 2 · 3. Defin´ıci´o Egy nem-nulla, nem egys´eg p sz´amot pr´ımsz´amnak nevez¨ unk, ha p | ab ⇒ p | a vagy p | b.
P´elda 2, −2, 3, −3, 5, −5. P´elda 6 nem pr´ımsz´am, mert 6 | 2 · 3 de 6 - 2 ´es 6 - 3.
15.
Elemi sz´ amelm´ elet
Diszkr´ et matematika 1. k¨ oz´ epszint
2017. ˝ osz
Pr´ımek, felbonthatatlanok ´ ıt´as All´ Minden pr´ımsz´am felbonthatatlan.
Bizony´ıt´as Legyen p pr´ımsz´am ´es legyen p = ab egy felbont´as. Igazolnunk kell, hogy a vagy b egys´eg. Mivel p = ab, ´ıgy p | ab, ahonnan p´eld´aul p | a. Ekkor a = pk = a(bk), azaz bk = 1, ahonnan k¨ ovetkezik, hogy b ´es k is egys´eg. A ford´ıtott ir´any nem felt´etlen¨ ul igaz: Z-ben igaz, (l´asd k´es˝ obb); √ {a + bi 5 : a, b ∈ Z}-ben nem igaz.
16.
Elemi sz´ amelm´ elet
Diszkr´ et matematika 1. k¨ oz´ epszint
2017. ˝ osz
Marad´ekos oszt´as A sz´amelm´eletben a f˝o eszk¨ oz¨ unk a marad´ekos oszt´as lesz:
T´etel Tetsz˝oleges a eg´esz sz´amhoz ´es b 6= 0 eg´esz sz´amhoz egy´ertelm˝ uen l´eteznek q, r eg´eszek, hogy a = bq + r
´es
0 ≤ r < |b|.
Bizony´ıt´as A t´etelt csak nemnegat´ıv sz´amok eset´eben bizony´ıtjuk. 1 L´etez´es: a szerinti indukci´ oval. a = 0 eset´en q = r = 0 j´o v´alaszt´as. Tegy¨ uk fel, hogy a-n´al kisebb sz´amok m´ar fel´ırhat´ok ilyen alakban. Ha a < b, akkor a = b · 0 + a (q = 0, r = a). Ha a ≥ b, akkor legyen az indukci´ os feltev´es ´ertelm´eben a − b = bq ∗ + r ∗ . Ekkor a = b(q ∗ + 1) + r ∗ (q = q ∗ + 1, r = r ∗ ). 2
Egy´ertelm˝ us´eg: legyen a = bq + r = bq ∗ + r ∗ . Ekkor ∗ b(q − q ) = r ∗ − r . Ez csak akkor lehet, ha q = q ∗ ´es r = r ∗ .
17.
