6 Ringen, lichamen, velden

6 6.1

Ringen, lichamen, velden Polynomen over Fp : irreducibiliteit en factorisatie

Oefening 6.1. Bewijs dat x2 + 2x + 2 irreducibel is in Z3 [x]. Oplossing 6.1 Aangezien de veelterm van graad ≤ 3 is, is deze irreducibel als hij geen wortels heeft. x ∈ Z3 x2 + 2x + 2 0 2 2 1 1 2 Uit bovenstaande tabel volgt dat dit inderdaad het geval is, de veelterm x2 + 2x + 2 is dus irreducibel in Z3 [x]. Oefening 6.2. Ontbind x5 + x4 + x3 + x in irreducibele factoren over Z2 . Oplossing 6.2 We vinden dat x5 + x4 + x3 + x = x(x4 + x3 + x2 + 1). Beschouw f (x) = x4 + x3 + x2 + 1. Aangezien f (1) = 0 vinden we dat (x + 1) een factor is van f (x). We berekenen aan de hand van de Euclidische deling of het schema van Horner dat x4 + x3 + x2 + 1 = (x + 1)(x3 + x + 1). Als g(x) = x3 + x + 1 reducibel is, dan zou er minstens één lineaire factor zijn die deze veelterm deelt. Maar g(0) = 1 = g(1), waaruit volgt dat x3 + x + 1 irreducibel is. We besluiten dat x5 + x4 + x3 + x = x(x + 1)(x3 + x + 1), waarbij elke factor irreducibel is. Oefening 6.3. Ontbind x8 − 1 in irreducibele factoren in Z3 [x]. Oplossing 6.3 In Z3 [x] is volgende formule ook geldig: A2 − B 2 = (A + B)(A − B). We vinden dus dat x8 − 1 = (x4 + 1)(x2 + 1)(x + 1)(x − 1). Er zijn nu nog twee niet-lineaire factoren waarvoor we moeten onderzoeken of ze te ontbinden zijn in Z3 [x]. Als de factor f (x) = x2 + 1 ontbindbaar is, dan is het een product van twee eentermen, wat enkel mogelijk is als f (x) nulwaarden bezit in Z3 . Aangezien echter f (0) = 1 en f (1) = f (2) = 2, mogen we besluiten dat de veelterm x2 + 1 irreducibel is in Z3 [x]. De ontbinding van x4 + 1 is in de cursus reeds uitgewerkt. We vinden dat x4 + 1 = (x2 + x − 1)(x2 − x − 1), terwijl deze veeltermen niet verder ontbindbaar zijn in Z3 [x]. We vinden dus dat x8 − 1 = (x + 1)(x − 1)(x2 + 1)(x2 + x − 1)(x2 − x − 1). Oefening 6.4. Ontbind x3 + 5x2 + 5 in Z11 [x]. Oplossing 6.4 Deze veelterm is van de graad 3 en dus irreducibel over Z11 als en slechts als ze geen lineaire factor Opgeloste oefeningen Relaties en Structuren, hoofdstuk 6

20

bevat, dus als en slechts als ze geen wortels bevat in Z11 . Aangezien de som van de coëfficiënten gelijk is aan 11 ≡ 0 (mod 11) is de veelterm deelbaar door x − 1 en na uitvoering van de deling bekomen we (x2 + 6x + 6)(x − 1) = x3 + 5x2 + 5. Zoeken we van x2 + 6x + 6 ∈ Z11 [x] de wortels (Discriminant = 12 = 1), dan vinden we 2 en 3, dus de gezochte factorisatie is x3 + 5x2 + 5 = (x − 1)(x − 2)(x − 3). Oefening 6.5. Factoriseer volgende veeltermen in irreducibele veeltermen over F5 . a. x4 + 4 b. x4 + 3x3 + 2x + 4 Oplossing 6.5 a. (x + 1)(x + 2)(x + 3)(x + 4) b. (x + 4)3 (x + 1) Oefening 6.6. Wat is de multipliciteit van de wortel 1 van x8 + x7 + x6 + x3 + x2 + 1 in Z2 [x]? Oplossing 6.6 Met behulp van de Euclidische deling of de regel van Horner vinden we achtereenvolgens: x8 + x7 + x6 + x3 + x2 + 1 x7 + x5 + x4 + x3 + x + 1 x6 + x5 + x3 + 1 x5 + x2 + x + 1 x4 + x3 + x2 + 1

= = = = =

(x + 1)(x7 + x5 + x4 + x3 + x + 1) (x + 1)(x6 + x5 + x3 + 1) (x + 1)(x5 + x2 + x + 1) (x + 1)(x4 + x3 + x2 + 1) (x + 1)(x3 + x + 1)

Nu is 1 geen nulpunt van x3 + x + 1. We vinden dus dat x8 + x7 + x6 + x3 + x2 + 1 = (x + 1)5 (x3 + x + 1). Toepassing van de regel van Horner maakt precies dezelfde berekening, maar noteert veel korter. Beredeneer zelf dat deze regel geldig is in Z2 [x]. Een andere manier om dit te vinden is de volgende berekening, waarbij herhaaldelijk gebruik gemaakt wordt van (a + b)2 = a2 + b2 : x8 + x7 + x6 + x3 + x2 + 1 = = = =

x8 + 1 + x3 (x4 + 1) + x2 (x4 + 1) (x4 + 1)(x4 + 1 + x3 + x2 ) (x + 1)4 (x3 (x + 1) + (x + 1)2 ) (x + 1)5 (x3 + x + 1)

De gezochte multipliciteit is dus 5.

6.2

Deling, Euclides en modulaire inversen

Oefening 6.7. Bepaal het quotiënt en de rest van de deling van a(x) door b(x) over het veld F. a. b. c. d. e.

F = F5 ; a(x) = 3x4 + 4x3 − x2 + 1; b(x) = 2x2 + x + 1. F = F8 met α3 + α + 1 = 0; a(x) = x4 + α2 x3 + α6 x2 + αx + α5 ; b(x) = α4 x2 + α3 x + 1. F = F2 ; a(x) = x3 + x2 + 1; b(x) = x2 + x + 1. F = F5 ; a(x) = x5 + x4 + 2x3 + x2 + 4x + 2, b(x) = x2 + 2x + 3. Zelfde als d. maar nu over F7 .

Opgeloste oefeningen Relaties en Structuren, hoofdstuk 6

21

f. Zelfde als d. maar nu over F73 . Oplossing 6.7 a. b. c. d. e. f.

Quotiënt 4x2 , rest 1. Quotiënt (α + 1)x2 + (α + 1)x + α2 + 1, rest (α2 + 1)x + α. Quotiënt x, rest x + 1. Quotiënt x3 + 4x2 + x + 2, rest 2x + 1. Quotiënt x3 + 6x2 + x + 2, rest 4x + 3. Quotiënt x3 − x2 + x + 2, rest −3x − 4.

Oefening 6.8. Vind de monische grootste gemene deler van de polynomen a(x) en b(x) in F[x] en schrijf het eindresultaat in de gedaante λ(x)a(x) + µ(x)b(x) over F[x]. a. b. c. d. e.

F = F3 ; a(x) = x3 + x2 + x + 1; b(x) = x2 + 2. F = F5 ; a(x) = x4 + 2x3 + x2 + 4x + 2; b(x) = x2 + 3x + 1. F = F2 ; a(x) = x4 + 1; b(x) = x2 + 1. F = F2 ; a(x) = x5 + 1; b(x) = x2 + 1. F = F2 ; a(x) = x9 + 1; b(x) = x6 + 1.

Oplossing 6.8 a. b. c. d. e.

Grootste gemene deler: Grootste gemene deler: Grootste gemene deler: Grootste gemene deler: Grootste gemene deler:

x + 1, λ(x) = 2, µ(x) = x + 1. x + 4, λ(x) = 1, µ(x) = 4x2 + x + 2. x2 + 1, λ(x) = 0, µ(x) = 1. x + 1, λ(x) = 1, µ(x) = x3 + x. x3 + 1, λ(x) = 1, µ(x) = x3 .

Oefening 6.9. Bepaal in de volgende gevallen de veeltermen λ(x) en µ(x) zodanig dat ggd(a(x), b(x)) = λ(x)a(x) + µ(x)b(x). a. a(x) = x4 + 2 en b(x) = 5x2 + 6x + 4 in Z7 [x]. b. a(x) = x3 + 2x2 + 2x + 1 en b(x) = 2x2 + 2 in Z3 [x]. c. a(x) = x5 + 1 en b(x) = x + 1 in Z2 [x]. Oplossing 6.9 a. Stel voor het gemak bij de berekeningen op voorhand volgende tabel op in Z7 : x 1 2 3 4 5 6 x−1 1 4 5 2 3 6 −x 6 5 4 3 2 1 Een eerste keer de Euclidische deling toepassen geeft x4 + 2 = (3x2 + 2x + 5)(5x2 + 6x + 4) + (4x + 3), wat we ook kunnen schrijven als (x4 + 2) − (3x2 + 2x + 5)(5x2 + 6x + 4) = 4x + 3. Opgeloste oefeningen Relaties en Structuren, hoofdstuk 6

22

De tweede Euclidische deling geeft als resultaat: 5x2 + 6x + 4 = (3x + 1)(4x + 3) + 1. We vinden dus achtereenvolgens 1 = 5x2 + 6x + 4 − (3x + 1)(4x + 3) = 5x2 + 6x + 4 − (3x + 1)[x4 + 2 − (3x2 + 2x + 5)(5x2 + 6x + 4)] = [(3x + 1)(3x2 + 2x + 5) + 1](5x2 + 6x + 4) − (3x + 1)(x4 + 2) = (2x3 + 2x2 + 3x + 6)(5x2 + 6x + 4) − (3x + 1)(x4 + 2), dus λ(x) = −3x − 1 = 4x + 6, µ(x) = 2x3 + 2x2 + 3x + 6. b. Grootste gemene deler: 1, λ(x) = x + 1, µ(x) = x2 . c. Grootste gemene deler: x + 1, λ(x) = 0, µ(x) = 1. Oefening 6.10. Bepaal in F3 [x] de inverse veelterm van 2x4 + 2 modulo x5 + 2. Oplossing 6.10 Aan de hand van het uitgebreid algoritme van Euclides vinden we (let op, we gebruiken -1 en 2 door elkaar, hoewel we hetzelfde element bedoelen): x5 + 2 = (2x4 + 2)(2x) + (−x + 2) 2x4 + 2 = (−x + 2)(x3 + 2x2 + x + 2) + 1 1 = (2x4 + 2) − (−x + 2)(x3 + 2x2 + x + 2) = −(x5 + 2)(x3 + 2x2 + x + 2) + (2x4 + x3 + 2x2 + x + 1)(2x4 + 2) Beschouw de laatste uitdrukking modulo x5 + 2 en je bekomt dat de inverse van 2x4 + 2 gelijk is aan 2x4 + x3 + 2x2 + x + 1, modulo x5 + 2. In Sage zou men dit kunnen berekenen met de volgende code: K.<x> = PolynomialRing(GF(3)) L.<x> = K.quotient(x^5+2) 1/(2*x^4+2) Na de tweede lijn weet x dat hij een element is van F3 [x]/(x5 + 2) zodat de laatste lijn het juiste antwoord geeft. Oefening 6.11. a. Waarom is x2 + 3 irreducibel over F5 ? b. Zoek de inverse veelterm van x + 1 modulo x2 + 3 in F5 . Oplossing 6.11

• Stel f (x) = x2 + 3, dan is f (1) = f (4) = 4 en f (2) = f (3) = 2, de veelterm f (x) heeft dus geen nulwaarden in F5 = Z5 , zodat de veelterm irreducibel is. • Aan de hand van het algoritme van Euclides vinden we x2 + 3 = (x + 1)(x + 4) + 4 x2 + 3 + 4(x + 1)(x + 4) = 4 4(x2 + 3) + (x + 1)(x + 4) = 1 Opgeloste oefeningen Relaties en Structuren, hoofdstuk 6

23

We vinden dus dat (x + 1)(x + 4) = 1 modulo x2 + 3. De inverse veelterm van x + 1 is dus gelijk aan x + 4 modulo x2 + 3 in F5 . Alternatief: werken modulo x2 + 3 betekent dat je x opvat als een object dat de informatie in zich draagt dat x2 + 3 = 0, ofte x2 = 2. Dus, met de methode van onbepaalde coëfficiënten: (x + 1)(ax + b) = 1 a · 2 + (a + b)x + b = 1 ( 2a + b = 1 a+b=0 a = 1, b = −1 = 4 Oefening 6.12. a. Bereken de som en het product in Z[x] van 3x + 4 en 5x − 2 modulo x2 − 7. −x2 2 b. Bereken de som en het product van 3x 2 en 2 modulo x + 2 in Q[x]. Oplossing 6.12 a. 8x + 2 en 14x + 97. b. Het tweede element is gewoon 1. Dus 23 x + 1 en 32 x.

6.3

Constructie van eindige velden

Oefening 6.13. a. b. c. d.

Toon aan dat f (t) = t2 + t − 1 over Z3 een irreducibel polynoom is. Bewijs dat f (t) = t2 + t − 1 een primitief polynoom is in Z3 [t]. Stel de Zech-log-tabel op voor F9 met de keuze van dit primitief polynoom. Bereken volgende elementen van F9 : (1 − t)(−1 + t) t4 + t7 t2 − 4t3 + 5t5 − 7t7

Oplossing 6.13 a. Aangezien een tweedegraadsveelterm enkel in lineaire termen ontbonden kan worden, is het voldoende om na te gaan of f (t) = t2 + 1 − 1 nulwaarden heeft in Z3 . t2

t 0 1 −1 + t − 1 −1 1 −1

We vinden dat f (t) = t2 + t − 1 irreducibel is over Z3 . b. Het polynoom f (t) = t2 + t − 1 is een primitief polynoom in Z3 [t] als t de cyclische groep F∗9 = C8 voortbrengt. Aangezien t2 = −t + 1 zal t4 = (−t + 1)2 = t2 + t + 1 = −t + 1 + t + 1 = 2 = −1 dus niet gelijk aan +1 waaruit we al mogen besluiten dat t voortbrengend element is van F∗9 . De veelterm f (t) = t2 + t − 1 is dus een primitief polynoom in Z3 [t]. c. We vinden dat F9 voorgesteld kan worden door F9 = {0, 1, −1, t, 1 + t, −1 + t, −t, −1 + t, −1 − t}, Opgeloste oefeningen Relaties en Structuren, hoofdstuk 6

24

waarbij onderverstaan is dat t2 + t − 1 = 0. Om de Zech-log-tabel op te stellen is het voldoende om de elementen ti met i = 2, . . . , 7 uit te rekenen, die wegens de definitie van primitief element allemaal verschillend zijn. We bekomen als totale oplijsting van het veld: t∞ = 0 t0 = 1 t1 = t t2 = −t + 1 t3 = t(t2 ) = t(−t + 1) = −t2 + t = t − 1 + t = −t − 1 t4 = −1 t5 = t(t4 ) = −t t6 = t2 (t4 ) = −t2 = t − 1 t7 = t2 − t = −t + 1 − t = t + 1 (t8 = 1) We vinden dus achtereenvolgens dat t + 1 = t7 ; t7 + 1 = t + 1 + 1 = t − 1 = t6 en dat t6 + 1 = t. Of nog θ(1) = 7; θ2 (1) = θ(7) = 6; θ3 (1) = θ(6) = 1. Anderzijds is t2 + 1 = −t + 1 + 1 = −t − 1 = t3 en is t3 + 1 = −t − 1 + 1 = −t = t5 dus θ(2) = 3; θ(3) = 5 waaruit zonder verdere berekeningen volgt dat θ(5) = 2. Verder is dus θ(∞) = 1, θ(1) = 4 en θ(4) = ∞. De Zech-log-tabel wordt dus gegeven door i ∞ 0 1 2 3 4 5 6 7 θ(i) 0 4 7 3 5 ∞ 2 1 6 d. (1 − t)(−1 + t) = t2 · t6 = t8 = 1 t4 + t7 = −1 + t + 1 = t t2 − 4t3 + 5t5 − 7t7 = t2 − t3 − t5 − t7 = (−t + 1) − (−t − 1) − (−t) − (t + 1) = 1 Oefening 6.14. a. Is x4 + x2 + 1 een primitieve, irreducibele veelterm in Z2 ? b. Is x4 + x + 1 een primitieve, irreducibele veelterm in Z2 ? Oplossing 6.14 a. We vinden onmiddellijk dat x4 + x2 + 1 = (x2 + x + 1)2 . Deze veelterm is dus reducibel, en komt zelfs niet in aanmerking om een primitief polynoom te zijn. b. Merk op dat x4 + x + 1 geen lineaire factoren heeft. Als de veelterm reducibel is, is hij het product van twee irreducibele tweedegraadsveeltermen over Z2 . Over Z2 zijn er twee lineaire veeltermen: x en x + 1. Er zijn bijgevolg juist drie reducibele kwadratische veeltermen: x2 , x2 + x en x2 + 1. Maar er zijn slechts vier kwadratische veeltermen over Z2 , waaruit volgt dat x2 + x + 1 de enige irreducibele kwadratische veelterm is over Z2 . Wetende dat x4 + x + 1 geen lineaire factoren heeft, kan hij enkel reducibel zijn als hij het product is van twee irreducibele kwadratische veeltermen zijn, dus de enige mogelijkheid is (x2 + x + 1)2 = x4 + x2 + 1. Dit is niet gelijk aan x4 + x + 1, waaruit volgt dat de beschouwde veelterm irreducibel is. Opgeloste oefeningen Relaties en Structuren, hoofdstuk 6

25

Is de veelterm nu ook primitief? Met andere woorden: is het element x (met x4 + x + 1 = 0) een voortbrengend element van F24 = F16 , waarbij F16 geconstrueerd wordt door x4 + x + 1? Om dit te controleren zullen we het veld stap voor stap opstellen. De resultaten zijn te vinden in volgende tabel. exponentieel additief 0 0 1 1 x x x2 x2 x3 x3 x4 x+1 x2 + x x5 3 2 x +x x6 x3 + x + 1 x7 x8 x2 + 1 3 x +x x9 x2 + x + 1 x10 x11 x3 + x2 + x 3 2 x +x +x+1 x12 x3 + x2 + 1 x13 x3 + 1 x14 Inderdaad, we zien dat de orde van x juist 15 is en niet minder. Omdat we weten dat x15 = 1, is het enige wat kon mislopen dat x3 = 1 of x5 = 1, dus eigenlijk volstond het om dit te controleren. Oefening 6.15. Onderzoek of de gegeven veelterm een irreducibele veelterm is over het gepaste veld en stel de Zech-logtabel op voor het gevraagde veld. Als het gegeven polynoom niet primitief is, zal je in plaats van de de variabele t dus een ander element α moeten kiezen dan als primitief element. a. b. c. d.

F4 , met f (t) = t2 + t + 1. F9 , met f (t) = t2 + 1. F16 , met f (t) = t4 + t + 1. F25 , met f (t) = t2 + 4t + 2.

Oplossing 6.15 a. De veelterm f (t) = t2 + t + 1 is een irreducibel polynoom in Z2 [t] en blijkt een primitieve veelterm voor F4 . Kies daarom α = t. We vinden de eerste twee kolommen hieronder, waaruit men snel de laatste twee kan halen, die de Zech-log-tabel zijn. exponentieel additief i θ(i) α∞ 0 ∞ 0 0 1 0 ∞ α α t 1 2 α2 t+1 2 1 b. De gegeven veelterm is irreducibel, maar is niet primitief. Het element α = 2t + 1 is echter wel een primitief element. We berekenen daarom de opeenvolgende machten αi voor i = 1, . . . 7 en kunnen dan de volgende tabel opstellen die het verband legt tussen de exponentiële notatie en de additieve Opgeloste oefeningen Relaties en Structuren, hoofdstuk 6

26

notatie, waaruit dan ook onmiddellijk de Zech-log-tabel volgt (zie de laatste twee kolommen). We stellen bovendien ook elk element a0 + a1 t nog eens voor als geordend tweetal (a0 , a1 ). exponentieel 0 = α∞ α0 α α2 α3 α4 α5 α6 α7

additief (a0 , a1 ) 0 (0, 0) 1 (1, 0) 2t + 1 (1, 2) t (0, 1) t+1 (1, 1) 2 (2, 0) t+2 (2, 1) 2t (0, 2) 2t + 2 (2, 2)

i θ(i) ∞ 0 0 4 1 7 2 3 3 5 4 ∞ 5 2 6 1 7 6

c. De veelterm f (t) = t4 +t+1 is een irreducibel polynoom in Z2 [t] en is een primitieve veelterm voor F16 . Kies daarom α = t en we bekomen de volgende tabel waarbij we in de eerste kolom de exponentiële notatie geven, in de tweede kolom de additieve notatie, in de derde kolom elk element dat dus additief van de vorm a0 + a1 t + a2 t2 + a3 t3 is, voorstellen als geordend 4-tal (a0 , a1 , a2 , a3 ). Uit de eerste twee kolommen kan men dan snel de laatste twee kolommen halen, die de Zech-log-tabel geeft. exponentieel 0 = α∞ α0 α α2 α3 α4 α5 α6 α7 α8 α9 α10 α11 α12 α13 α14

additief (a0 , a1 , a2 , a3 ) 0 (0, 0, 0, 0) 1 (1, 0, 0, 0) t (0, 1, 0, 0) 2 t (0, 0, 1, 0) 3 t (0, 0, 0, 1) 1+t (1, 1, 0, 0) 2 t +t (0, 1, 1, 0) 3 2 t +t (0, 0, 1, 1) t3 + t + 1 (1, 1, 0, 1) 2 t +1 (1, 0, 1, 0) 3 t +t (0, 1, 0, 1) t2 + t + 1 (1, 1, 1, 0) 3 2 t +t +t (0, 1, 1, 1) 3 2 t +t +t+1 (1, 1, 1, 1) t3 + t2 + 1 (1, 0, 1, 1) 3 t +1 (1, 0, 0, 1)

i θ(i) ∞ 0 0 ∞ 1 4 2 8 3 14 4 1 5 10 6 13 7 9 8 2 9 7 10 5 11 12 12 11 13 6 14 3

d. De gegeven veelterm is inderdaad irreducibel over Z5 en is bovendien een primitieve veelterm voor F25 . Maak zelf de berekeningen en controleer ze met de volgende tabel.


27

exponentieel 0 = α∞ α0 α α2 α3 α4 α5 α6 α7 α8 α9 α10

additief (a0 , a1 ) 0 (0, 0) 1 (1, 0) t (0, 1) t+3 (3, 1) 4t + 3 (3, 4) 2t + 2 (2, 2) 4t + 1 (1, 4) 2 (2, 0) 2t (0, 2) 2t + 1 (1, 2) 3t + 1 (1, 3) 4t + 4 (4, 4)

i θ(i) ∞ 0 0 6 1 22 2 17 3 10 4 23 5 14 6 18 7 8 8 4 9 11 10 13

exp α11 α12 α13 α14 α15 α16 α17 α18 α19 α20 α21 α22 α23

additief (a0 , a1 ) 3t + 2 (2, 3) 4 (4, 0) 4t (0, 4) 4t + 2 (2, 4) t+2 (2, 1) 3t + 3 (3, 3) t+4 (4, 1) 3 (3, 0) 3t (0, 3) 3t + 4 (4, 3) 2t + 4 (4, 2) t+1 (1, 1) 2t + 3 (3, 2)

i θ(i) 11 16 12 ∞ 13 5 14 3 15 2 16 20 17 1 18 12 19 9 20 19 21 7 22 15 23 21

Oefening 6.16. Gebruik de Zech-log-tabellen uit oefening 6.15 om de volgende kwadratische vergelijkingen op te lossen: a. b. c. d.

αx2 + α2 = 0 over F4 . x2 + α7 x + α2 = 0 over F9 . x2 + α7 x + 1 = 0 over F16 . x2 + α13 x + α14 = 0 over F25 .

Oplossing 6.16 a. Over F4 . Deze vergelijking is equivalent met x2 + α = 0, dus door α4 = α ook equivalent met x2 + α4 = 0 en wegens de freshmen’s dream met (x + α2 )2 = 0. We vinden één oplossing, namelijk x = α2 . b. Over F9 . Kwadratische vergelijkingen over karakteristiek verschillend van 2 kunnen we oplossen met de discriminantmethode. Houd rekening met 2 = −1 = α4 en met α8 = 1. We vinden dan √ −b ± b2 − 4ac x1,2 = 2a √ 7 −α ± α14 − α2 = −1 p = α7 ∓ α14 + α6 √ = α7 ∓ 2α6 √ = α7 ∓ α4 α6 = α7 ∓ α5 = α7 + α5 , α7 − α5 = α7 + α5 , α7 + α = α5 (α2 + 1), α(α6 + 1) = α5 α3 , αα = 1, α2 . Inderdaad, men kan controleren dat 1 + α7 + α2 = 0 en (α2 )2 + α7 α2 + α2 = 0. c. Over F16 . Opgeloste oefeningen Relaties en Structuren, hoofdstuk 6

28

1. Gereduceerde vergelijking y = δ =

ax b ac b2

= αx7 = α114

15

= αα7x 15 = αα14

= α8 x =α

2. Tr(α) Tr(α) = α + α2 + α4 + α8 = α(1 + α) + α4 (1 + α4 ) = α5 + α5 = 0. We kunnen dus besluiten dat er twee oplossingen zijn. 3. We zoeken nu een element k ∈ F16 waarvoor Tr(k) = 1. We vinden Tr(α3 ) = α3 + α6 + α12 + α9 = α2 + α8 = α15 = 1. Een oplossing van de vergelijking wordt gegeven door s = kδ 2 + (k + k 2 )δ 4 + (k + k 2 + k 4 )δ 8 . Wanneer we k = α3 en δ = α invullen, bekomen we s = α3 α2 + (α3 + α6 )α4 + (α3 + α6 + α12 )α8 = α5 + α6 + α7 α8 = α9 + 1 = α7 . De twee oplossingen van de gereduceerde vergelijking worden gegeven door α7 en α9 . 4. De oplossingen van de oorspronkelijke vergelijking worden gegeven door α14 en α. d. Over F25 . We gebruiken de discriminantmethode. Houd rekening met 4 = −1 = α12 en met α24 = 1. We vinden dan √ −b ± b2 − 4ac x1,2 = (5) 2a√ −α13 ± α26 + α14 = (6) 2 p −α13 ± α14 (α12 + 1) = (7) α6 √ α12 α13 ± 0 = (8) α6 = α19 (9) met dubbele multipliciteit. Inderdaad, want x2 + α13 x + α14 = x2 + α18 α19 x + α38 = x2 − 2α19 x + α38 = (x − α19 )2 . Oefening 6.17. Los de volgende kwadratische vergelijkingen op over F8 waarbij t3 + t + 1 = 0. a. tx2 + (t2 + t + 1)x + t2 + t = 0. Opgeloste oefeningen Relaties en Structuren, hoofdstuk 6

29

b. (1 + t + t2 )x2 + t2 x + t + 1 = 0. Oplossing 6.17 Werk in de exponentiële notatie en ga pas op het einde weer over naar de additieve notatie. a. {t, t2 }. b. {1, 1 + t + t2 }

6.4

Primitieve elementen

Oefening 6.18. Hoeveel primitieve elementen heeft een eindig veld van orde 64? Oplossing 6.18 Aangezien de multiplicatieve groep F∗64 de cyclische groep C63 is, zijn er Φ(63) = Φ(32 · 7) = 2 · 3 · 6 = 36 niet-nul-elementen die deze multiplicatieve groep voortbrengen, dus primitieve elementen. Oefening 6.19. Zoek de primitieve elementen van Z41 . Oplossing 6.19 Aangezien 41 een priemgetal is, is Z41 een veld. We weten ook dat Z∗41 de cyclische groep C40 is. Een primitief element van Z41 is dus een element van orde 40 dat de volledige groep Z∗41 voortbrengt. Er zijn in totaal juist Φ(40) = Φ(5)Φ(8) = 4 · 4 = 16 primitieve elementen van Z41 . We zoeken nu een element van orde 40. We starten met het kleinst mogelijk element, met name 2 en nemen de opeenvolgende machten van 2 (ermee rekening houdend dat we modulo 41 werken). We vinden dan 2, 4, 8, 16, 32, 23, 5, 10, 20, 40 = −1. Omdat 210 = −1 in Z41 , zal de orde van 2 precies 20 zijn. Helaas, geen primitief element. We proberen eens met 3. Om de orde van 3 te vinden, noteren we de opeenvolgende machten van 3: 3, 9, 27, 81 = −1. Hieruit kunnen we besluiten dat de orde van 3 inderdaad 8 moet zijn. Weer geen primitief element, maar kgv(8, 20) = 40. We maken nu gebruik van de volgende eigenschap (zie oefeningen 5.7 en 5.11): als u de orde s heeft en v de orde r, dan heeft uv de orde kgv(r, s) = rs/ ggd(r, s). We vinden dus dat de orde van 6 gelijk is aan kgv(20, 8) = 40. Hoera, 6 is een primitief element. Nu we een primitief element α gevonden hebben, gebruiken we dat ook αi met ggd(i, 40) = 1, een primitief element is van Z41 . Om nu alle primitieve elementen te vinden in Z41 moeten we dus 6k berekenen modulo 41 met ggd(k, 40) = 1, dus de primitieve elementen zijn 6, 63 , 67 , 69 , 611 , 613 , 617 , 619 , 621 , 623 , 627 , 629 , 631 , 633 , 637 en 639 . Sage rekent na dat dit de elementen 6, 11, 29, 19, 28, 24, 26, 34, 35, 30, 12, 22, 13, 17, 15 en 7 zijn. Oefening 6.20. Vergelijk de ringen Z16 en F16 . Beantwoord daarvoor voor beide: a. Hoe ziet de additieve groep van beide eruit? b. Hoeveel elementen heeft de multiplicatieve groep (of meer correct, de multiplicatieve groep van inverteerbare elementen)? c. Hoeveel primitieve elementen zijn er? d. Lijst alle inverteerbare elementen met hun ordes op. Oplossing 6.20


30

a. Z16 is net opgebouwd als de optelling modulo 16, dus de additieve groep van Z16 is cyclisch en wordt voortgebracht door 1, m.a.w Z16 , + ∼ = C16 . De additieve groep van F16 is meer ingewikkeld. Omdat 1 + 1 = 0, brengt element 1 hier een deelgroep C2 voort en niet de hele groep. De additieve groep is abels en element heeft orde 2. We vinden dat F16 , + ∼ = C2 × C2 × C2 × C2 . b. F16 is een veld dus elk element behalve 0 is inverteerbaar. We weten bovendien dat de multiplicatieve groep cyclisch is, namelijk F16 , · ∼ = C15 . Een element zal inverteerbaar zijn modulo 16 als het er onderling ondeelbaar mee is. Bijgevolg zijn er Φ(16) = 8 inverteerbare elementen in Z16 . Deze zullen een groep vormen, maar dit is niet noodzakelijk een cyclische groep. c. In F16 zijn er Φ(15) = 8 primitieve elementen. Dezelfde redenering als oefening 6.18. Een element van Z16 wordt primitief genoemd als het maximale orde, nl. 8 heeft. Als de groep niet cyclisch is (en er dus geen element van orde 8 bestaat), zijn er geen primitieve elementen. Als de groep wel cyclisch is, zullen er Φ(8) = 4 primitieve elementen zijn. Uit de uitwerking hieronder blijkt dat er geen primitieve elementen zijn. d. Voor F16 is de oefening eenvoudig, als we de elementen multiplicatief voorstellen, als machten van een primitief element α: x 0 = α∞ 1 α2 α3 α4 α5 α6 α7 α8 α9 α10 α11 α12 α13 α14 orde − 1 15 5 15 3 5 15 15 5 3 15 5 15 15 Voor Z16 zijn we aangewezen op proberen. We weten alvast dat we de ordes moeten bepalen van de Φ(16) = 8 inverteerbare elementen {1, 3, 5, 7, 9, 11, 13, 15}, die de multiplicatieve groep uitmaken. Deze orde is het kleinste natuurlijk getal t waarvoor geldt dat at ≡ 1 (mod 16). Om niet voor alle elementen een groot aantal berekeningen te moeten maken, zullen we theoretische observaties gebruiken. (a) Aangezien aΦ(m) ≡ 1 (mod m) vinden we al dat elke t | 8. We hebben dus enkel 1, 2, 4 en 8 als mogelijke ordes van deze elementen. (b) Als de orde van een element a gelijk is aan t, dan heeft ak eveneens orde t als en slechts als ggd(k, t) = 1. (Hieruit kunnen we al besluiten dat als we een primitief element a vinden, er minstens Φ(8) = 4 primitieve elementen zijn, namelijk a, a3 , a5 en a7 , die wegens primitiviteit van a allemaal verschillend zijn.) Beschouw a = 3. We vinden 32 ≡ 9 (mod 16) 33 ≡ 27 ≡ 11 34 ≡ 3 · 11 ≡ 33

(mod 16) ≡ 1

(mod 16)

De orde van 3 is dus gelijk aan 4, maar ook de orde van 33 ≡ 11 (mod 16) is gelijk aan 3. We vinden ook dat de orde van 32 ≡ 9 (mod 16) gelijk is aan 2. Beschouw nu a = 5. We vinden 52 ≡ 25 ≡ 9

(mod 16).

Aangezien we de orde van 9 al kennen, vinden we dat de orde van 5 gelijk is aan 4. Ook de orde van 53 ≡ 5 · 9 ≡ 13 (mod 16) is gelijk aan 4. Hieruit kunnen we ook meteen besluiten dat er geen primitieve elementen zijn, aangezien er geen 4 elementen meer over zijn. We moeten nu nog de orde van 7 en 15 bepalen. We vinden dat 73 ≡ 49 ≡ 1 (mod 16), de orde van 7 is dus gelijk aan 2. Uit (−1)2 ≡ 1 (mod 16), volgt dat ook de orde van −1 ≡ 15 gelijk is aan 2. We vatten dit samen in volgende tabel: x 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 orde − 1 − 4 − 4 − 2 − 2 − 4 − 4 − 2 Opgeloste oefeningen Relaties en Structuren, hoofdstuk 6

31

6.5

Doordenkers in eindige velden

Oefening 6.21. Bewijs dat alle elementen van F211 derdemachten zijn. Oplossing 6.21 211 = 2048. In F211 is elk element een kwadraat en hebben we dat x = x2048 . Vermenigvuldigen we deze vergelijking met x, dan bekomen we voor elk element x2 = x2049 = (x

2049 3

)3 .

Een willekeurig element van F211 is te schrijven als het linkerlid, en dus ook als het rechterlid, is m.a.w. een derdemacht. Oefening 6.22 (Examen 2012). Bewijs: als ggd(k, q − 1) = 1, dan is elk element in Fq een k-de macht. Oplossing 6.22 De multiplicatieve groep van dit veld is een cyclische groep Cq−1 , voortgebracht door een element a. We moeten bewijzen dat elk element van Cq−1 te schrijven is als k-de macht. Maar als ggd(k, q − 1) = 1, dan is ook ak een voortbrenger. Daarom is elk element te schrijven als (ak )m = (am )k , duidelijk een k-de macht. De observatie dat ook 0 een k-de macht is, voltooit het bewijs. Een andere methode is de volgende. Om te bewijzen dat de afbeelding θk : Fq → Fq : x 7→ xk surjectief is, volstaat het om aan te tonen dat ze injectief is (door de eindigheid van Fq ). Stel dat xk = y k . Dan is (xy −1 )k = 1. Maar in de multiplicatieve, cyclische groep heeft elk element als orde een deler van q − 1, maar k is onderling ondeelbaar met q−1. Dit kan enkel als xy −1 = 1. (Meer formeel, met c(q−1)+dk = 1, c d xy −1 = (xy −1 )c(q−1)+dk = (xy −1 )q−1 · (xy −1 )k = 1. Oefening 6.23. a. Welk irreducibel polynoom met coëfficiënten in F2 heeft precies alle elementen van orde drie van F16 als nulpunten? b. Welk irreducibel polynoom met coëfficiënten in F2 heeft precies alle elementen van orde vijf van F16 als nulpunten? c. Welk irreducibel polynoom met coëfficiënten in Fp heeft precies alle elementen van orde d van Fph als nulpunten, waarbij d een deler is van ph − 1? Oplossing 6.23 a. De elementen van orde drie van F16 voldoen aan x3 = 1. Maar ook 1 voldoet hieraan, en dit is geen element van orde 3. We vinden over F2 dat x3 + 1 = (x + 1)(x2 + x + 1). De veelterm x2 + x + 1 is irreducibel over F2 en heeft de twee elementen van F16 van orde 3 als wortels. Een andere manier om dit te vinden is de volgende: in de exponentiële notatie van F16∗ zijn α5 en α10 de elementen van orde drie. Deze vormen immers de cyclische deelgroep C3 van hαi = C15 . We vinden dat het gezochte polynoom (x + α5 )(x + α10 ) = x2 + (α5 + α10 )x + α15 is, hoewel dit nog geen polynoom is met coëfficiënten in F2 . Voor elk element van F16 geldt echter dat zijn 15-de macht 1 is, dus α15 = 1. Om te bepalen wat het mysterieuze element α5 + α10 is, kunnen we observeren dat zijn kwadraat (α5 + α10 )2 = α10 + α20 = α10 + α5 terug zichzelf is. Er zijn echter maar twee elementen die voldoen aan η 2 = η, namelijk 1 en 0. Maar mocht α5 + α10 = 0, dan zouden α5 en α10 gelijk zijn, quod non. Dus de middelste coëfficiënt is 1 en het gezochte polynoom is x2 + x + 1. Opgeloste oefeningen Relaties en Structuren, hoofdstuk 6

32

b. Analoog, x4 + x3 + x2 + x + 1. c. Analoog. Deze elementen voldoen aan xd + 1 = 0, maar het gezochte polynoom is (xd + 1)/(x + 1) = xd−1 + xd−2 + · · · + x + 1. Oefening 6.24. Welke polynoom is een deler van x15 − 1 en heeft precies alle primitieve elementen van F16 als nulpunt? Oplossing 6.24 Het polynoom x15 − 1 heeft alle elementen van F16 als wortels. De elementen van orde 3 zijn wortels van x3 − 1. Meer precies (omdat 1 hier ook een wortel van is maar niet orde 3 heeft), zijn de orde3 −1 = x2 + x + 1. Analoog zijn de orde-5-elementen precies de wortels van 3-elementen wortels van xx−1 x5 −1 x−1

= x4 + x3 + x2 + x + 1. Het orde-1-element, namelijk 1, is wortel van x − 1. De overblijvende elementen zijn de primitieve elementen, dus om het gevraagde polynoom te bekomen, moeten we uit x15 − 1 de gevonden polynomen wegdelen. Brute-force-rekenwerk leert ons dat (x + 1)(x2 + x + 1)(x4 + x3 + x2 + x + 1) = x7 + x6 + x5 + x2 + x + 1 en met behulp van de Euclidische deling vinden we tot slot dat x15 + 1 = (x7 + x6 + x5 + x2 + x + 1)(x8 + x7 + x5 + x4 + x3 + x + 1). Iets zuiniger in rekenwerk is de berekening (x − 1)

(x15 − 1)(x − 1) x15 − 1 = = x8 + x7 + x5 + x4 + x3 + x + 1 5 3 3 5 (x − 1)(x − 1) x −1 x −1 x−1 x−1

We besluiten dat x8 + x7 + x5 + x4 + x3 + x + 1 juist de 8 primitieve elementen van F16 als nulpunt heeft. Oefening 6.25. a. Hoeveel koppels (a, b) ∈ F8 × F8 zijn er met a2 − b2 = 1? b. Hoeveel koppels (a, b) ∈ F9 × F9 zijn er met a2 − b2 = 1? c. Hoeveel koppels (a, b) ∈ F16 × F16 zijn er met a2 + b3 = 1? Oplossing 6.25 a. We werken over een veld met even karakteristiek, dus elk element is een kwadraat. Analoog heeft elk element een vierkantswortel. Beschouw a2 = 1 + b2 . We vinden dat er voor elke b ∈ F8 een uniek getal 1 + b2 bestaat. We vinden dat er dus een unieke a bestaat zodat a2 = 1 + b2 . Er zijn dus juist acht koppels in F8 × F8 . b. Over F9 hebben we dat −1 = α4 . We kunnen dus volgende tabel opstellen. b 0 1 α α2 α3 α4 α5 α6 α7 2 2 4 6 b 0 1 α α α 1 α2 α4 α6 b2 + 1 1 α4 α2 + 1 0 α6 + 1 We hebben nu al 8 oplossingen (welke? (1, 0), (α4 , 0), (0, α2 ), (0, α6 ), (α2 , 1), (α2 , α4 ), (α6 , 1), (α6 , α4 )). Er kunnen er telkens nog 4 bijkomen, als zou blijken dat α2 + 1 of α6 + 1 een kwadraat zijn. Nu zouden we het veld F9 expliciet kunnen opstellen om dit te onderzoeken, maar aangezien het aantal oplossingen onafhankelijk is van de voorstelling van het veld, kunnen we dit ook los van de additieve notatie of de Zech log tabel oplossen. We vinden dat a2 + 1 = a2 (1 + a6 ) en a6 + 1 = a6 (1 + a2 ). Hieruit volgt dat ofwel α2 + 1 en α6 + 1 beide een kwadraat zijn, ofwel geen van beiden. Opgeloste oefeningen Relaties en Structuren, hoofdstuk 6

33

Veronderstel dat ze beiden een kwadraat zijn. Dan vinden we α2 + 1 = α6 en α6 + 1 = α2 . Deze twee beweringen kunnen slechts samengaan in een veld van karakteristiek 2, waaruit een strijdigheid volgt. We concluderen dat α2 + 1 en α6 + 1 beide geen kwadraat zijn, waaruit volgt dat er juist 8 koppels voldoen aan de gegeven vergelijking. Een veel kortere methode is de volgende: a2 − b2 = 1 ⇔ (a + b)(a − b) = 1. We vinden dus dat a + b = x en a − b = x−1 . Het stelsel gevormd door deze twee vergelijkingen heeft determinant 1 en is dus voor elke waarde van x oplosbaar: de oplossing wordt gegeven door (−x − x−1 , −x + x−1 ). Voor elke x ∈ F∗9 vinden we precies 1 mogelijkheid voor a en b. Dus 8 oplossingen. c. Voor elke b vinden we precies één a, omdat elk element een vierkantwortel heeft. Er zijn dus zoveel oplossingen als de grootte van het veld, nl. 16. Oefening 6.26. Bewijs dat x16 + x4 + x + 1 precies 16 verschillende wortels heeft over F64 . Hint: beschouw de afbeelding f : F64 → F64 , x 7→ x16 + x4 + x + 1 en vooral diens beeld. Oplossing 6.26 Beschouw, voor een vaste x ∈ F64 het beeld f (x) = x16 + x4 + x + 1 = γ. We vinden dat γ 4 = γ. Hieruit volgt dat elk mogelijk beeld γ van de functie f (x) een element is van F4 (als deelveld van F64 ). De elementen van F64 worden door f dus afgebeeld op vier elementen, namelijk 0, 1, t = α21 , t2 = t + 1 = α42 . De vier vergelijkingen x16 + x4 + x + 1 = 0 x16 + x4 + x + 1 = 1 x16 + x4 + x + 1 = α21 x16 + x4 + x + 1 = α42 hebben samen juist 64 oplossingen, namelijk alle elementen van F64 . Maar elke vergelijking heeft hoogstens 16 oplossingen, waaruit volgt dat elke bovenstaande vergelijking juist 16 oplossingen heeft. Oefening 6.27. Noem α een primitief element van F9 , en noem f (x) een irreducibele veelterm van Z3 [x] zodanig dat f (α2 ) = 0. Bepaal f (x). Oplossing 6.27 We hebben dat α8 = 1, met αn 6= 1 voor elke 0 < n < 8. Stel b = α2 . Bovenstaande opmerkingen hebben tot gevolg dat de orde van b gelijk is aan 4. We hebben dus b4 = 1. Stel nu g(x) = x4 − 1. Dan is b een nulpunt van deze veelterm over Z3 . Maar deze veelterm is niet irreducibel over Z3 . Aangezien x4 − 1 = (x2 + 1)(x + 1)(x − 1) over Z3 , vinden we dat f (x) = x2 + 1. Controle: we vinden dat b2 + 1 = α4 + 1 = −1 + 1 = 0 in F9 .


34

7 7.1

Telprincipes Dubbele telling

Oefening 7.1. Veronderstel dat we een aantal verschillende deelverzamelingen van N[1, 8] beschouwen zodanig dat elke deelverzameling 4 elementen bevat en dat elk element van N[1, 8] tot 3 dergelijke deelverzamelingen behoort. Hoeveel dergelijke deelverzamelingen zijn er dan? Oplossing 7.1 Beschouw de verzameling M van alle deelverzamelingen van N[1, 8] met drie elementen die voldoen aan bovenstaande eigenschappen. De deelverzameling S = {(n, D) ∈ N[1, 8] × M k n ∈ D} van N[1, 8] × M , dan is rn (S) = 3 voor alle n ∈ N[1, 8] en kD (S) = 4 voor alle D ∈ M . Wegens het principe van de dubbele telling bekomen we X X rn (S) = kD (S), |S| = n∈N[1,8]

D∈M

waaruit 3 · |N[1, 8]| = 4 · |M | en dus |M | = 6. Oefening 7.2. Is het mogelijk om een verzameling van deelverzamelingen van N[1, 8] te vinden zodanig dat elke deelverzameling 3 elementen bevat, en zodanig dat elk element van N[1, 8] tot 5 deelverzamelingen behoort? Oplossing 7.2 Dezelfde redenering als in oefening 7.2 zou impliceren dat |M | · 3 = 8 · 5 waaruit zou volgen 3 | 8 · 5, een strijdigheid. Dus een dergelijke verzameling M bestaat niet. Oefening 7.3. Indien X1 , X2 , X3 , . . . , Xn verzamelingen zijn (eventueel gelijk), dan wordt X1 × X2 × · · · × Xn = {(x1 , x2 , . . . , xn ) k xi ∈ Xi } de productverzameling van X1 , X2 , . . . , Xn genoemd. Bewijs door middel van het inductieprincipe dat |X1 × X2 × · · · × Xn | = |X1 | · |X2 | · . . . · |Xn |. Oplossing 7.3 Voor inductiebasis n = 1 is er niets te bewijzen: |X1 | = |X1 |. We bewijzen expliciet voor n = 2 dat |X1 × X2 | = |X1 | · |X2 |. Een willekeurig element van X1 × X2 is van de vorm (x1 , x2 ), waarbij x1 ∈ X1 P en x2 ∈ X2 . We vinden dat |X1 × X2 | = x1 ∈X1 rx1 (S), waarbij rx1 (S) juist gelijk is aan het aantal koppels (x1 , x2 ) waartoe die bepaalde x1 behoort. Dit aantal is gelijk aan |X2 |. We vinden dus dat P |X1 × X2 | = x1 ∈X1 |X2 | = |X1 | · |X2 |, wat men wilde bewijzen. Zij nu k ≥ 2. We bewijzen dat als de uitspraak geldt voor n = k, dan ook voor n = k + 1. |X1 × X2 × · · · × Xk+1 | = |(X1 × X2 × · · · × Xk ) × Xk+1 )| n=2

= |X1 × X2 × · · · × Xk | · |Xk+1 |

IH

= |X1 | · |X2 | · · · · · |Xk+1 |.


35

Oefening 7.4. Beschouw volgende definitie: de hoekpunten van een ruimtefiguur zijn de geordende drietallen (a1 , a2 , a3 ) waarbij a1 , a2 , a3 ∈ {0, 1}. Twee hoekpunten worden verbonden door een ribbe als ze slechts in één positie een verschillend element hebben. Bijvoorbeeld (0, 0, 0) wordt verbonden met (0, 0, 1) maar niet met (1, 1, 0). a. b. c. d. e. f. g.

Hoeveel hoekpunten heeft deze figuur? Heeft deze figuur driehoeken? Heeft deze figuur vierhoeken? Tot hoeveel ribben behoort elk hoekpunt? Bepaal hoeveel ribben deze figuur heeft aan de hand van een dubbele telling. Bepaal hoeveel vierhoeken deze figuur heeft aan de hand van een dubbele telling. Welk ruimtelichaam stelt deze figuur voor?

Oplossing 7.4 Er zijn 23 = 8 drietallen. Neen. Ja. 3. Tel de koppels (hoekpunt, ribbe) op twee manieren, waarbij het beschouwde hoekpunt tot de ribbe behoort. Stel r gelijk aan het aantal ribben. We vinden 8 · 3 = r · 2, waaruit volgt dat de figuur 12 ribben heeft. f. 6. g. Een kubus (eigenlijk parallellepipedum) a. b. c. d. e.

Oefening 7.5. Op een grootouderfeest op een lagere school komen voor elk kind gemiddeld 2 grootouders kijken. Elke grootouder heeft gemiddeld drie kleinkinderen op deze school. Hoeveel kinderen zitten op deze school als er 66 grootouders naar het feest komen? Oplossing 7.5 99: dubbele telling koppels (grootouder, kleinkind) geeft 66 · 3 = 2 · x. Oefening 7.6. In de minor wiskunde zijn er zeven vakken waarvan elke student er exact vier moet volgen. (Ga uit van een ideale wereld zonder GIT.) • De administratie laat weten dat er in deze lessen respectievelijk 10, 5, 6, 8, 13, 17 en 8 studenten ingeschreven zijn. Bewijs dat de administratie fout is. • Na hervragen blijkt dat er in de vakken 10, 5, 6, 8, 13, 17 en 5 studenten ingeschreven zijn. Bewijs dat de administratie nog steeds fout is. Oplossing 7.6 • Het aantal student-vak-inschrijvingen is de som van deze getallen, 67. Dit moet echter deelbaar zijn door 4, quod non. • Het aantal student-vak-paren is nu 64. Dit betekent dat er 16 studenten de minor wiskunde volgen. Dit is echter in strijd met het feit dat een vak gevolgd wordt door 17 lijfelijk verschillende studenten. Oefening 7.7. Gent wil een autodeelsysteem opstarten. Elk deelnemend gezin moet kunnen kiezen uit 3 verschillende auto’s. Er zijn 48 gezinnen ge¨nteresseerd en er zijn 18 wagens beschikbaar. Wat kan je nu bepalen? Opgeloste oefeningen Relaties en Structuren, hoofdstuk 7

36

Oplossing 7.7 Elke auto wordt door (gemiddeld) 8 gezinnen gebruikt. Oefening 7.8. Hoeveel diagonalen heeft een n-hoek? Oplossing 7.8 Dubbele telling van de koppels (diagonaal, hoekpunt) waarbij het hoekpunt op de diagonaal ligt, levert diagonalen. n(n − 3) = 2|D|, aldus zijn er n(n−3) 2 Oefening 7.9. Een tuinaanlegger wil 10 bomen op een originele manier planten. Hij wil 5 rijen van vier bomen bekomen. Hoe kan hij dat doen? Oplossing 7.9 Elke boom moet in twee rijen staan. Hij moet ze in een stervorm plaatsen: 1 op de 5 toppen en 1 op de snijpunten van de lijnstukken die de toppen verbindt. Oefening 7.10. Een school besluit een voetbalcompetitie op te starten. Elke ploeg moet tegen elke andere ploeg spelen. Leerlingen moeten een vast duo vormen en samen moeten ze in drie ploegen meespelen (waarbij er telkens één van de twee meespeelt). Er zijn 36 wedstrijden gepland. Hoeveel leerlingen nemen deel aan deze competitie? Oplossing 7.10 Als er n ploegen zijn, en er worden W = 36 wedstrijden gespeeld, tel dan de koppels (p, w), waarbij p een ploeg is en w een wedstrijd, zodat p de wedstrijd w speelt. We vinden dat n(n − 1) = W · 2 = 72. Oplossen van deze vergelijking levert ons n = 9 (of n = −8, wat hier nu niet mogelijk is). Er zijn dus negen ploegen. We tellen nu de koppels (d, p), waarbij d een duo leerlingen is en p een ploeg waarin een vertegenwoordiger van d speelt. Stel nu D gelijk aan de verzameling van alle leerlingenduo’s. Een dubbele telling geeft dat |D| · 3 = n · 11 = 99. We vinden hieruit dat er 33 duo’s leerlingen zijn die deelnemen aan het tornooi. Dit betekent dat er 66 leerlingen voetballen. Merk op dat dit een eenvoudige dubbele telling van leerlingen en duo’s is, met 2 leerlingen per duo en 1 duo per leerling. Oefening 7.11. Een geheime sekte heeft een zeer speciaal gebouw gemaakt. Elke kamer is toegankelijk door juist drie deuren, waarbij er ook juist drie deuren naar buiten toe gebruikt worden. Er zijn juist 15 kamers. De sekte heeft speciale sleutels laten maken zodat voor elke twee deuren er precies één sleutel is die op beide deuren past maar op geen enkele andere. Elke sleutel hangt buiten in een kastje dat op zijn beurt ook op slot is. Van elk kastje zijn er drie sleuteltjes gemaakt. Elk sektelid heft een sleutelbos met 12 sleuteltjes van een kastje. Hoeveel sekteleden telt deze sekte? Oplossing 7.11 Opnieuw zullen we de elementen van een verzameling door kleine letters aanduiden, waarbij de verzameling zelf door een grote letter genoteerd wordt. Tel de koppels (k, d) op twee manieren, waarbij k een kamer is en d een deur die toegang geeft tot deze kamer. Merk op dat we ook buiten als een kamer moeten beschouwen, aangezien ook tot deze ruimte drie deuren behoren. We bekomen dat |K| · 3 = |D| · 2, waaruit volgt dat |D| = 16·3 2 = 24. Er zijn dus 24 deuren. Opgeloste oefeningen Relaties en Structuren, hoofdstuk 7

37

Tel nu het aantal sleutels. We zullen de koppels (s, d) tellen, waarbij de sleutel s op de deur d past. Op deur d passen 23 sleutels, namelijk voor elke andere deur de sleutel die op d en die andere deur past. Dubbele = 12 · 23. telling van deze koppels geeft dus dat |S| · 2 = |D| · 23 = 24 · 23, waaruit volgt dat |S| = 24·23 2 Men kan ook inzien dat het aantal sleutels het aantal paren is uit 24 elementen, dus 24 = 12 · 23. 2 Er zijn evenveel kastjes als sleutels. Er zijn dus 12·23 kastjes k. Tel nu de koppels (k, s) op twee manieren, waarbij het sektelid s een sleuteltje heeft van het kastje k. We vinden dat |K| · 3 = |S| · 12. Aangezien |K| = 12 · 23, vinden we dat |S| = 23 · 3 = 69. Er zijn 69 sekteleden.

7.2

Binomium van Newton

Oefening 7.12. Bewijs het binomium van Newton door gebruik te maken van inductie. Oplossing 7.12 Neem als inductiebasis n = 1, dan volgt duidelijk dat het binomium geldig is voor n = 1. Stel nu dat het binomium voldaan is voor k ∈ N. Dan (a + b)k+1

= (a + b)k (a + b) k X k i k−i IH ab = (a + b) i i=0 k−1 k k k+1 X k i+1 k−i X k i k−i+1 k k+1 = a + a b + ab + b k i i 0 i=0 i=1 k X k k k+1 k+1 = a +b + + aj b(k+1)−j j−1 j j=1

k+1 X k + 1 i (k+1)−i = ab i i=0

waaruit, wegens het inductieprincipe, volgt dat het binomium van Newton geldig is voor alle n ∈ N0 . Oefening 7.13. Bewijs de volgende formules: n X n = 2n k k=0 n X k n (−1) = 0 k k=0

Oplossing 7.13 Beide gelijkheden kunnen bewezen worden door een goede keuze te maken voor a en b in (a + b)n uit het binomium van Newton, door inductie te gebruiken, of door verzamelingtheoretisch te redeneren, hetgeen een elegante oplossing oplevert. Tel het aantal deelverzamelingen van N[1, n] op twee manieren om de eerste formule te bewijzen: we weten al dit aantal gelijk is aan 2n . We tellen nu dit aantal op een andere wijze n X |{M kM ⊆ N[1, n]}| = |{M ⊆ N[1, n]| |M | = k}| k=0

=

n X n k=0

k


38

waaruit de eerste formule. n−1 + k−1 , Om de tweede formule te bewijzen gebruiken we de identiteit van Stifel-Pascal, zijnde nk = n−1 k 1 1 gecombineerd met inductie op n. Kies als inductiebasis n = 1. Wegens 0 − 1 = 0 is het gestelde alvast waar voor n = 1. Zij nu l willekeurig zodat het gestelde geldt voor n = l. Dan is l+1 X l+1 = (−1)k k

l+1 X

k=0

k=0

(−1)k

l l + k k−1

l X

X l+1 l k l k = + (−1) (−1) k k−1 k=0 k=1 X l l X k l i l = − (−1) (−1) k i k=0

i=0

IH

= 0 + 0 = 0.

l l In de tweede gelijkheid hebben we gebruikt dat de verdwenen binomiaalcoëfficiënten l+1 en l+1 gelijk zijn aan 0. In de derde gelijkheid hebben we de rechtse som aangepast door over te gaan op sommatievariabele i = k − 1. Als k loopt van 1 tot l + 1, dan loopt i van 0 tot l. De exponent van −1 wordt dan i + 1, maar we hebben één factor als minteken voorop gezet. Oefening 7.14. Bewijs de volgende formule 2 2 2 2 2 n n n n n 2n + + + ... + + = . 0 1 2 n−1 n n Oplossing 7.14 Het gebruik van inductie leidt tot niet triviale gelijkheden die aangetoond moeten worden. We gebruiken dus een alternatieve methode. We zien dat 2n n het aantal deelverzamelingen met n elementen is van een verzameling met 2n elementen. We zullen nu dit aantal op een andere manier proberen tellen. Daartoe zoeken we een interpretatie voor het linkerlid in termen van deelverzamelingen. De formule n worden als: kies i elementen uit een verzameling met n elementen. Aangezien i kan ge¨nterpreteerd n n 2 n n n = = vinden we dat i . n−i i n−i i Deze gegevens moeten we nu combineren om een uitdrukking te vinden die alle deelverzamelingen met n elementen van een verzameling met 2n elementen telt. Beschouw M = N[1, 2n], dan is M = M1 ∪ M2 , met M1 = N[1, n], M2 = N[n + 1, 2n]. Deze unie is disjunct, en |M1 | = |M2 | = n. Elke deelverzameling van M met kardinaliteit n kan verkregen worden door eerst in M1 precies i getallen te kiezen (i ≤ n) en daarna nog (n − i) getallen in M2 , en elke dergelijke verkregen verzameling is maar één keer geteld op die manier. Omgekeerd heeft elke deelverzameling B van M , waarvoor |B| = n, een vast aantal i elementen gemeen met M1 en n − i elementen met M2 .


39

Deze redenering levert ons: |{D ⊆ M k |D| = n}| = |{(D1 , D2 ) ∈ 2M1 × 2M2 k |D1 ∪ D2 | = n}| X = |{D2 ⊆ M2 k |D1 ∪ D2 | = n}| =

=

D1 ⊆M1 n X

X

|{D2 ⊆ M2 k |D2 | = n − i}|

i=0 D1 ⊆M1 :|D1 |=i n X X i=0 D1 ⊆M1 :|D1 |=i n X

n n−i

n n i n−i i=0 n 2 X n = i =

i=0

Oefening 7.15. Bewijs dat het binomiaalgetal kp met p een priemgetal, deelbaar is door p voor alle waarden van k, 1 ≤ k ≤ p − 1. Leid hieruit af dat (a + b)p − ap − bp steeds deelbaar is door p voor elke 2 gehele getallen a en b. Oplossing 7.15 p! Aangezien kp = k!(p−k)! volgt dat p! = kp k!(p − k)!. Omdat nu p het linkerlid deelt, moet het ook het rechterlid delen. Aangezien k, p − k < p is k!(p − k)! niet deelbaar door p want p is priem. Dus p | kp voor alle k met 1 ≤ k ≤ p − 1. P p i p−i Nu is (a + b)p − ap − bp = p−1 waaruit onmiddellijk volgt dat p | (a + b)p − ap − bp . i=1 i a b

7.3

Variaties en combinaties

Oefening 7.16. Op hoeveel manieren kan je 12 mensen aan 2 ronde tafels voor 6 personen zetten? We beschouwen twee schikkingen als dezelfde als je de ene kan bekomen uit de andere door de tafels rond te draaien. Merk op dat we de tafels niet nummeren, dus een tafelschikking bekomen uit een andere door de twee tafels om te wisselen als geheel, beschouwen we ook als equivalent. Oplossing 7.16 Eerst moeten we de mensen in 2 groepen van 6 personen verdelen. Dit kan door 6 personen uit de groep te halen en de overige zes vormen dan de tweede goep. We bekomen elke opsplitsing nu 2 keer, aangezien de volgorde van de groepen niet belangrijk is. We vinden dus dat we dit kunnen doen op 21 12 6 manieren. Daarna moeten we alle mensen aan de tafel plaatsen. We kunnen dit aan elke tafel op 6! manieren, maar er zijn telkens 6 manieren dezelfde, aangezien we de tafel kunnen draaien. Er zijn dus 6!6 = 5! mogelijkheden voor elke tafel. 2 Samen genomen vinden we dat er 21 12 6 · (5!) = 6 652 800 mogelijkheden zijn. Een andere methode is de volgende: nummer de stoelen van 1 tot 12. De mensen kunnen op 12! manieren op de stoelen gaan zitten. Nu geeft het ronddraaien van elke tafel telkens 6 dezelfde tafelschikkingen op, terwijl het verwisselen van de twee tafels opnieuw dezelfde tafelschikkingen oplevert. We bekomen dus 12! 6·6·2 . Opgeloste oefeningen Relaties en Structuren, hoofdstuk 7

40

We kunnen de symmetrie ook van meet af aan inbouwen in de redenering. Aangezien het verwisselen van de twee tafels als geheel dezelfde tafelschikking oplevert, net zoals het roteren van tafels, is het duidelijk dat we voor een gegeven tafelschikking, na omwisselen en roteren, ieder van de 12 personen op de eerste stoel kunnen krijgen. Dus voor stoel nummer 1 mogen we een willekeurige persoon kiezen, zonder dat er daarbij tafelschikkingen verloren gaan. Er blijven dus 11 · 10 · 9 · 8 · 7 mogelijkheden om de eerste tafel op te vullen. Voor de tweede tafel blijven er nog juist 6 personen over. Opnieuw mogen we, omwille van de rotatie van tafels, 1 van de overblijvende personen op de eerste stoel van de tweede tafel kiezen. Er blijven dus nog 5! mogelijkheden over om de tweede tafel op te vullen. In totaal zijn er dus 11! 6 mogelijke tafelschikkingen. Oefening 7.17. Constantijn heeft tien ballen. Hij splitst deze in twee hopen. Dan neemt hij een hoop die uit minstens twee elementen bestaat en splitst deze op in twee hopen, zo verdergaand tot alle ballen afzonderlijk liggen. Op hoeveel manieren kan hij dit doen? Oplossing 7.17 In hoeveel stappen is de procedure afgelopen? Om de oplossing te vinden, kan je de procedure achterwaarts doorlopen. In negen stappen is de procedure afgelopen. De procedure achterwaarts doorlopen komt erop neer dat je in stap n twee hoopjes kiest, hiervoor zijn dus n2 manieren. In het totaal kan dit dus op 10 9 8 2 · · · ... · 2 2 2 2 manieren. Oefening 7.18. a. Op hoeveel manieren kan je drie verschillende personen aan een tafel met twintig stoelen zetten, waarbij er geen twee naast elkaar zitten? b. Als er al twintig personen rond diezelfde tafel zitten, op hoeveel manieren kan je dan drie mensen kiezen waarvan er geen twee naast elkaar zitten? Oplossing 7.18 De tweede vraag vraagt het aantal configuraties, waarbij de volgorde van de plaatsen niet van belang is. Bij de eerste vraag zijn twee zettingen wel degelijk verschillend als de personen samen dezelfde plaatsen bezetten, maar er in een andere volgorde op zitten. Het antwoord op de eerste vraag zal dus een factor 3! = 6 groter zijn dan het antwoord op de tweede. a. De eerste persoon kan je op 20 manieren kiezen. Zijn 2 buren vallen dan meteen weg. Voor de 17 plaatsen die mogelijk zijn om de tweede persoon te kiezen, zullen we een onderscheid maken in twee gevallen. De tweede persoon kan ofwel twee plaatsen van de eerste persoon zitten, ofwel verder. In het ene geval hebben we twee manieren om de tweede persoon te kiezen (namelijk twee links of twee rechts), en daarna 15 manieren om de derde persoon te kiezen, want nu blokkeren beiden slechts vijf zetels. In het andere geval kunnen we de tweede persoon op 15 manieren kiezen en de derde persoon op 14, want nu blokkeren beiden samen zes zetels, namelijk deze waarop ze zitten en hun buren. We vinden dat 20 · (2 · 15 + 15 · 14) = 4800. b. We volgen een alternatieve piste voor de tweede vraag. Het aantal mogelijkheden om willekeurig drie plaatsen uit te kiezen, is 20 3 . Het aantal mogelijkheden om drie plaatsen zodanig te kiezen dat er twee naast elkaar zitten en de de andere ergens apart, is 20 · 16: er zijn 20 mogelijkheden om twee Opgeloste oefeningen Relaties en Structuren, hoofdstuk 7

41

aaneensluitende posities te kiezen aan de ronde tafel en dan zijn er nog 16 mogelijkheden om de andere te kiezen. Het aantal mogelijkheden om drie aaneensluitende plaatsen te kiezen, is 20. Er zijn dus 20 3 − 20 · 16 − 20 = 800 manieren om drie mensen te kiezen waarvan er geen twee naast elkaar zitten. Oefening 7.19. Beschouw een verzameling A met n elementen. a. b. c. d. e. f. g.

Hoeveel relaties zijn er over A? Hoeveel reflexieve relaties zijn er over A? Hoeveel antireflexieve relaties zijn er over A? Hoeveel relaties over A zijn reflexief en symmetrisch? Hoeveel symmetrische relaties zijn er over A? Hoeveel antisymmetrische relaties zijn er over A? Hoeveel relaties over A zijn noch symmetrisch, noch antisymmetrisch?

Oplossing 7.19 a. We herhalen dat een relatie over A een deelverzameling R ⊆ A × A is. Het aantal relaties over A is 2 dus het aantal deelverzamelingen van de verzameling A × A, dit is dus 2|A×A| = 2n . b. Een relatie R over de verzameling A is reflexief als en slechts als (x, x) ∈ R, ∀x ∈ A. Een reflexieve relatie R bevat dus zeker de diagonaal D = {(x, x)kx ∈ R}. In A × A \ D blijven er nog juist n2 − n koppels van de vorm (x, y), x 6= y over waarvan we willekeurig kunnen kiezen of ze tot de reflexieve relatie behoren of niet. Om een reflexieve relatie op te bouwen, moeten we dus starten van D en hebben we nog n2 − n keer de keuze om een koppel al dan niet toe te voegen. Het aantal reflexieve 2 relaties over A is dus 2n −n . c. Een relatie R is antireflexief als en slechts als (x, x) 6∈ R, ∀x ∈ A. Ook hier hebben we voor elk identiek koppel (a, a) geen keuze: het mag niet in R zitten. Dus er blijven ook nu nog n2 − n koppels over 2 waarvan we de keuze hebben om ze toe te voegen aan R, en aldus zijn er 2n −2 antireflexieve relaties over A. Het aantal antireflexieve relaties is bijgevolg gelijk aan het aantal reflexieve relaties. d. Als we een reflexieve en symmetrische relatie willen opbouwen, hebben we geen keuze op de diagonaal: de identieke koppels moéten erin. De symmetrie van de relatie R eist dat als (a, b) ∈ R, dan ook (b, a) ∈ R. Voor elk paar {a, b}, met a 6= b, zitten dus ofwel (a, b) en (b, a) er beiden in, ofwel zit geen 2 enkel van beide in R. Voor elk van de n2 = n 2−n paren moeten we dus de keuze maken. Er zijn n2 −n

bijgevolg 2 2 symmetrische en reflexieve relaties. 2 e. Zoals bij de vorige opgave mogen we voor de n 2−n niet-identieke paren telkens de binaire keuze maken (beide erin of beide er niet in), maar nu hebben we ook op de diagonaal vrij spel: we mogen voor de n identieke koppels (a, a) telkens de binaire keuze maken of we het koppel erin nemen of niet. Er zijn 2

2

n2 +n

dus n 2−n + n = n 2+n keuzes te maken en bijgevolg bestaan er 2 2 symmetrische relaties. f. Voor de antisymmetrische relaties is het iets moeilijker. Antisymmetrie betekent dat als (a, b) ∈ R én (b, a) ∈ R, dan a = b moet zijn. Voor verschillende elementen a 6= b mogen (a, b) en (b, a) dus niet beiden in R zitten. De drie alternatieven, nl. dat enkel (a, b) tot de relatie behoort, of enkel 2 (b, a), of geen enkele van de twee, zijn wel mogelijk. Omdat we voor elk van de n 2−n niet-identieke paren juist 3 opties hebben, en we verder opnieuw naar willekeur een aantal van de n identieke koppels kunnen toevoegen, is het aantal mogelijkheden om een antisymmetrische relatie op te bouwen, gelijk n(n−1) aan 3 2 · 2n . g. We bewijzen eerst dat de relaties die zowel symmetrisch als antisymmetrisch zijn, precies deze zijn die enkel identieke koppels bevatten (maar mogelijks niet allemaal). Inderdaad, stel dat (a, b), met a 6= b, in R zou zitten. Wegens symmetrie moet dan ook (b, a) erin zitten en wegens antisymmetrie moet dan a = b, een strijdigheid. Er zijn bijgevolg 2n relaties die zowel symmetrisch als antisymmetrisch zijn: voor elk van de n identieke koppels moeten we kiezen of we het koppel erin nemen of niet. Opgeloste oefeningen Relaties en Structuren, hoofdstuk 7

42

Het aantal gevraagde relaties is dus het totaal aantal relaties, verminderd met het aantal symmetrische en verminderd met het aantal antisymmetrische, maar vermeerderd met 2n , omdat we dat aantal dubbel n(n−1) n(n+1) 2 afgetrokken hadden. We vinden dat er 2n − 2 2 − 3 2 · 2n + 2n relaties noch symmetrisch, noch antisymmetrisch zijn. Oefening 7.20. a. Als A 64 deelverzamelingen heeft, wat is dan |A|? b. Als B 64 deelverzamelingen van oneven kardinaliteit heeft, wat is dan |B|? Oplossing 7.20 a. |A| = 6. Een verzameling heeft immers 2n deelverzamelingen. b. |B| = 7. Beschouw een verzameling met n elementen. Om de deelverzamelingen met oneven kardinaliteit te bepalen, moeten we elk element labelen met een 0 of een 1, waarmee we aanduiden of het element al dan niet tot de deelverzameling behoort. Maar bij het laatste element hebben we geen keuze meer, omdat we een oneven aantal elementen moeten hebben. Er zijn dus 2n−1 deelverzamelingen van even kardinaliteit. Oefening 7.21. Beschouw drie verzamelingen A, B en C waarvoor |B| = 3. Bepaal |A| als er 4096 relaties zijn van A naar B. Bepaal |C| als er 2187 afbeeldingen zijn van C naar B. Oplossing 7.21 |A| = 4. Een relatie is een deelverzameling van het cartesisch product A × B. Er zijn dus 2|A×B| = 2|A|·|B| = 23|A| = 212 relaties, dus |A| = 4. Om een afbeelding van C naar B te maken, moeten we voor elk van de |C| elementen van C kiezen op welk van de |B| = 3 elementen van B we het afbeelden. We hebben dus |B||C| = 3|C| = 37 afbeeldingen, waaruit |C| = 7. Oefening 7.22. Beschouw A ⊂ N[1, 14], met |A| = 6. Toon aan dat de mogelijke sommen van elementen uit deelverzamelingen van A niet allemaal verschillend kunnen zijn. Oplossing 7.22 A heeft 26 = 64 deelverzamelingen, inclusief de ledige, die som 0 heeft. Als we nu de mogelijke sommen bekijken van elementen uit A, dan weten we dat deze som ten minste 0 zal moeten zijn en ten hoogste 14 + 13 + 12 + 11 + 10 + 9 = 69, maar dit zijn 70 mogelijkheden. Hoewel die laatste som enkel kan voor één specifieke A, zijn er dus minder deelverzamelingen dan mogelijke sommen, waardoor we het gestelde niet kunnen concluderen door het duivenhokprincipe in het algemeen geval. Beschouw daarom enkel de deelverzamelingen met maximum 5 elementen. Voor elke dergelijke deelverzameling weten we dat de som van een aantal elementen eruit tussen 0 en 14 + 13 + 12 + 11 + 10 = 60 ligt. Er zijn dus hoogstens 61 mogelijke sommen. Maar er zijn juist 63 deelverzamelingen van A met maximum 5 elementen: enkel de verzameling A zelf moeten we buiten beschouwing laten. Wegens het ladenprincipe van Dirichlet bestaan er minstens twee deelverzamelingen van A (met ten hoogste 5 elementen) die dezelfde som hebben. Oefening 7.23. Op hoeveel manieren kan je 24 mensen aan 4 ronde tafels van 6 personen plaatsen?


43

Oplossing 7.23 18 12 6 24 Er zijn 6,6,6,6 = 24 6 6 6 6 mogelijkheden om vier groepen te maken van 6 personen, waarbij we de keuzes ordenen. Aangezien we het over een ongeordende keuze hebben, moeten we nog delen door 4!. We kunnen nu elke groep op 5! manieren aan hun tafel zetten. Het aantal manieren is dus 24 6,6,6,6

4!

· (5!)4 .

Een alternatieve redenering gaat als volgt. Er zijn 24! manieren om iedereen op één stoel te zetten. Nu is elke draaiing van een tafel eenzelfde tafelschikking. We moeten dus delen door 64 , aangezien er 4 tafels zijn. We kunnen nu nog de tafels onderling wisselen en delen dus door 4!. Ga na dat dit hetzelfde aantal oplevert. Oefening 7.24. Op de busticketjes in Servië staan de cijfers van 1 tot en met 9, zoals ze op een telefoon zijn afgebeeld (zie het eerste ticket op de figuur). Bij het opstappen moet je de ticketjes in een ontwaarder steken. Deze perforeert mechanisch enkele gaatjes op de plaatsen van de cijfers. Je bekomt dus een getal met hoogstens 9 cijfers waarvan de cijfers van klein naar groot gerangschikt zijn. Het tweede ticket bijvoorbeeld kan je voorstellen door 125 (of zo je wil duaal door 346789).

Figuur 1: Bustickets uit Belgrado, Servië.


44

a. Hoeveel verschillende manieren zijn er om drie gaatjes in deze kaartjes te knippen, waarbij er geen drie opeenvolgende cijfers uitgeknipt worden? b. Hoeveel verschillende manieren zijn er om drie gaatjes in deze kaartjes te knippen, zodat er twee gaatjes naast elkaar liggen, maar de drie gaatjes niet op één rij liggen? (Merk op dat naast elkaar liggen betekent dat de desbetreffende vierkantjes een zijde gemeenschappelijk moeten hebben. Zo liggen 1 en 4 naast elkaar en 3 en 5 niet.) Op de figuur voldoet het tweede, vierde, vijfde en zesde ticket aan deze voorwaarde. Oplossing 7.24 a. We kunnen drie gaatjes uitpikken op 93 manieren. Er zijn 7 manieren waarbij er drie opeenvolgende cijfers uitgeknipt worden: beginnend met een 1, tot en met 7. Het gezochte aantal manieren is dus 9 − 7 = 77. 3 b. We beschouwen eerst de twee gaatjes die naast elkaar liggen. Merk op dat het aantal keuzemogelijkheden van het tweede gaatje afhangt van de plaats waar we het eerste gaatje gekozen hebben: in een hoek, het midden van een zijde of de middelste positie. Maar we kiezen twee posities, en we merken op dat juist één van deze posities noodzakelijk in het midden van een zijde liggen, dus de cijfer 2, 4, 6 of 8 moeten zijn. Gevolg is dat we dus voor dat gaatje 4 keuzes hebben, en voor het tweede gaatje nog eens drie keuzes. We hebben bij deze manier al rekening gehouden met de volgorde en vinden dus 12 mogelijke keuzes voor de eerste twee manieren. Voor de keuze van het derde gaatje moeten we opnieuw opletten: als het derde gaatje niet naast één van de eerste twee gaatjes ligt, bekomen we een unieke configuratie. Als het derde gaatje daarentegen naast één van de twee andere gaatjes ligt, wordt die betreffende configuratie dubbel geteld. Het derde gaatje kunnen we op 6 manieren kiezen, want het derde gaatje in het verlengde van de eerste twee gaatjes mogen we niet kiezen. Er zijn echter 16 manieren om de drie gaatjes in een hoekformatie te plaatsen. Deze zijn dubbel geteld, en moeten dus van het totaal aantal afgetrokken worden. We vinden dus in het totaal 12 · 6 − 16 = 56 manieren. Een alternatieve manier om dit te tellen is de volgende. Er zijn in totaal 93 = 84 manieren om drie gaatjes te kiezen uit deze 9 posities. Hiervan zijn er 6 manieren waarbij deze op één rij of kolom liggen. Nu moeten we nog het aantal manieren tellen waarbij er geen twee naast elkaar liggen. Ofwel behoort de 5 tot de drie gaatjes, ofwel niet. In het eerste geval moeten we voor de twee volgende kiezen uit de hoekposities, en dit kan op 42 = 6 manieren. In het tweede geval kunnen we het eerste vakje kiezen uit 8 mogelijkheden. Merk op dat deze allemaal gelijkwaardig zijn, aangezien elke positie juist twee buren heeft. Om de gedachten te vestigen kiezen we het getal 1. Voor het tweede gaatje moeten we opsplitsen. We mogen niet voor 2 of 4 kiezen, aangezien deze naast 1 liggen. Als we voor 3 of 7 kiezen, hebben we bij de volgende keuze nog 3 mogelijkheden. Als we voor 6, 8 of 9 kiezen, hebben we bij de volgende keuze nog slechts 2 keuzemogelijkheden. We hebben nog geen rekening gehouden met de volgorde, waaruit volgt dat er in dit tweede geval 8·(2·3+3·2) = 16 3! mogelijkheden zijn. We hebben dus nog 84 − 6 − 6 − 16 = 56 mogelijkheden over. Oefening 7.25 (Ingangsexamen geneeskunde-tandheelkunde). Op hoeveel manieren kunnen we 5 rode ballen en 3 witte ballen verdelen over 3 personen als de eerste persoon niet meer dan 5 ballen krijgt maar wel zeker 2 rode en 1 witte bal krijgt, de tweede persoon zeker 1 rode en 1 witte bal en de derde persoon zeker 1 rode bal. Oplossing 7.25 Zes ballen hebben hun plaats al gevonden. Slechts een rode bal en een witte moeten nog toegewezen worden aan één van de drie personen en dit kan onafhankelijk van elkaar. Bijgevolg zijn er 32 = 9 manieren om dit te doen. Opgeloste oefeningen Relaties en Structuren, hoofdstuk 7

45

7.4

De Stirlinggetallen

Oefening 7.26. Bewijs de volgende identiteiten voor de Stirlinggetallen. a. S(n, 2) = 2n−1 − 1 b. S(n, n − 1) = n2 Oplossing 7.26 a. Deze gelijkheid is via inductie zeer eenvoudig te bewijzen als je gebruik maakt van de recursieve definitie van de Stirlinggetallen. Een andere manier om deze gelijkheid aan te tonen, is door een dubbele telling. Er zijn exact S(n, 2) mogelijke niet-triviale partities van N[1, n]. Beschouw nu de koppels (D, P ), waarbij P een partitie is van N[1, n] in twee niet-ledige klassen, zodat D één van deze twee klassen is. Elke D behoort tot juist één partitie, namelijk de partitie bestaande uit D en N[1, n] \ D. Er zijn juist 2n − 2 keuzes voor D, aangezien zowel ∅ als N[1, n] zelf ongeldige partities opleveren. Anderzijds vinden we dat elke partitie juist twee deelverzamelingen van N[1, n] bevat, terwijl er S(n, 2) dergelijke partities zijn. We vinden dus dat 2n −2 = 2·S(n, 2), waaruit het gestelde volgt. b. Een partitie van N[1, n] met (n − 1) niet-ledige klassen is noodzakelijk een partitie met (n − 1) singletons en precies 1 paar. Omgekeerd, met elk paar correspondeert een unieke partitie in n − 1 deelverzamelingen. Dus S(n, n − 1) is gelijk aan het aantal paren in N[1, n], wat n2 is. Oefening 7.27. Beschouw A = N[1, 6]. Hoeveel relaties in A zijn equivalentierelaties? Oplossing 7.27 Een equivalentierelatie in A is hetzelfde als een partitie van A. Er zijn juist S(6, i) partities van A in i P klassen. We vinden dus dat er 6i=1 S(6, i) = 1 + 31 + 90 + 65 + 15 + 1 = 203 equivalentierelaties zijn. Oefening 7.28. Beschouw 2 verzamelingen A en B met respectievelijk m en n elementen, waarbij m ≥ n. Hoeveel surjecties zijn er van A op B? Oplossing 7.28 Om een surjectie f van A op B te bekomen, moeten we een partitie maken van A in n klassen, en elke klasse dan op een ander element b van B afbeelden. (Deze klasse wordt de vezel van het element b genoemd en wordt genoteerd als f −1 (b).) Er zijn exact S(m, n) partities van A in n klasses, en van elke partitie kunnen we op n! manieren een surjectieve afbeelding maken, door aan elk van de vezels een beeld van B toe te wijzen. Er zijn dus n!S(m, n) surjecties van A op B.

7.5

De multinomiaalgetallen

Oefening 7.29. Hoeveel strings van 11 letters kunnen we maken met de letters uit het woord MISSISSIPPI? Oplossing 7.29 Stel X = N[1, 11] and Y = {m, i, s, p}, dan correspondeert met elk woord x1 x2 . . . x11 , bestaande uit de −1 11 letters van MISSISSIPPI, precies 1 afbeelding σ : X → Y , gegeven door iσ = xi waarbij |mσ | = 1,


46

−1

−1

−1

|iσ | = |sσ | = 4 en |pσ | = 2, en omgekeerd. Dus het aantal woorden is gelijk aan het aantal dergelijke functies, wat net de definitie is van het multinomiaalgetal 11 11! = 34650. = 1, 4, 4, 2 4!4!2! Oefening 7.30. Indien a + b + c = n, bewijs dan dat n n−1 n−1 n−1 = + + . a, b, c a − 1, b, c a, b − 1, c a, b, c − 1 Van welke identiteit van binomiaalgetallen is dit een veralgemening? Oplossing 7.30

n a, b, c

=

n! a!b!c!

(n − 1)! a!b!c! (n − 1)! (n − 1)! (n − 1)! = + + (a − 1)!b!c! a!(b − 1)!c! a!b!(c − 1)! n−1 n−1 n−1 = + + a − 1, b, c a, b − 1, c a, b, c − 1 = (a + b + c)

wat het gestelde bewijst. Men kan dit ook door een synthetische redenering bewijzen. Als we n elementen moeten verdelen over n als volgt opdelen. drie verzamelingen van groottes a, b en c, dan kunnen we het aantal manieren a,b,c Fixeer een element x. Als we zeker zijn dat het in de verzameling met grootte a terechtkomt, zijn er nog n−1 n−1 om de overige n − 1 te verdelen. Analoog als x elders terecht komt: dan zijn er a,b−1,c a−1,b,c manieren n−1 of a,b,c−1 manieren. Omdat we juist in één van die gevallen zullen zitten, is het totaal aantal manieren de som van deze drie, wat de identiteit bewijst. n−1 + Dit is een veralgemening van de de identiteit van Stifel-Pascal: nk = n−1 k−1 . k Oefening 7.31. Veronderstel dat p een priemgetal is. Bewijs dat het multinomiaalgetal p n1 , n2 , . . . , nk deelbaar is door p, tenzij één van de getallen ni gelijk is aan p. Oplossing 7.31 p! = n1 ! · n2 ! · · · · · nk ! ·

p n1 ,n2 ,...,nk

. Aangezien p priem is, zal de factor p maar één keer in p! zitten. Dus

p | p! en deelt p! niet. Deze vaststellingen impliceren dat p | n1 !n2p!!...nk ! als en slechts als n1 !n2 ! . . . nk ! niet deelbaar is door p, of dus als en slechts als ni < p, voor alle i ∈ N[1, k]. p2

Oefening 7.32. Bewijs dat 1 X n S(n, k) = k! n1 , n2 , . . . , nk waarbij de som genomen wordt over alle mogelijke k-tallen (n1 , n2 , . . . , nk ) van positieve natuurlijke getallen zodanig dat hun som n is. Opgeloste oefeningen Relaties en Structuren, hoofdstuk 7

47

Oplossing 7.32 De bewijsbare formule is gelijkwaardig met X n k! · S(n, k) = n1 , n2 , . . . , nk Het linkerlid is juist gelijk aan het aantal surjecties van N[1, n] op N[1, k]. We proberen nu de surjecties van N[1, n] op N[1, k] op een andere manier te tellen. Beschouw een willekeurige surjectie γ van N[1, n] op N[1, k]. Stel nu ni gelijk aan het aantal elementen van N[1, n] dat afgebeeld wordt op het element i uit N[1, k]. Dit levert een genummerde partitie op van N[1, n]. Beschouw volgende redeneringen om dit in te zien. • Aangezien we een functie beschouwen, wordt elk element van N[1, n] afgebeeld op juist één element van van N[1, k]. Elk element van N[1, n] behoort tot juist één component van de partitie van N[1, n]. P Hieruit volgt dat ki=1 ni = n. • Aangezien we een surjectie beschouwen, kunnen we voor elk element i van N[1, k] een element vinden uit N[1, n] dat afgebeeld wordt op i. De bijhorende component van de partitie van N[1, n] is dus niet ledig en dus is elke ni verschillend van nul. • Merk nog eens op dat elk element van eenzelfde component afgebeeld wordt op hetzelfde element i van N[1, k]. Deze component bevat juist ni elementen, we kunnen deze component dan ook de i-de component van de partitie noemen. Omwille van deze nummering van de componenten bepaalt de genummerde partitie op een unieke manier de surjectie γ. We willen nu het aantal surjecties van N[1, n] op N[1, k] bepalen. Merk op dat voor elke gekozen P (n1 , n2 , n3 , . . . , nk ) met ki=1 ni = n, er exact n1 ,n2n,...,nk mogelijkheden zijn om de elementen van N[1, n] in deze genummerde partitie in te delen. Elke partitie bepaalt op een unieke manier een surjectie. Anders geformuleerd: er zijn exact n1 ,n2n,...,nk surjecties van N[1, n] op N[1, k] waarbij er ni elementen afgebeeld worden op het element i van N[1, k]. Om nu alle mogelijke surjecties te vinden, moeten we nog P sommeren over alle mogelijke (n1 , n2 , n3 , . . . , nk ) waarvoor geldt ki=1 ni = n. Oefening 7.33. Op hoeveel manieren kan men mn voorwerpen verdelen over m dozen zodanig dat elke doos juist n elementen bevat? Oplossing 7.33 Het is duidelijk dat dit net het aantal surjectieve afbeeldingen γ van N[1, nm] naar N[1, m] is, waarbij −1 met alle ni gelijk voor alle i ∈ N[1, m] : |iγ | = n. Per definitie is dit het multinomiaalgetal n1 ,nnm ,...,n m 2 aan n, dit is

(nm)! (n!)m .

Oefening 7.34. Bewijs door gebruik te maken van de multinomiaalgetallen, dat a. 2n een deler is van (2n)! en dat het quotient even is als n ≥ 2. b. (n!)2n+1 een deler is van (n2 !)!. Oplossing 7.34 a. Aangezien het multinomiaalgetal n1 ,n2n waarbij alle ni gelijk zijn aan 2, goed gedefinieerd is 2 ,...,nn en dus per definitie een natuurlijk getal is, zal 2n = (2!)n | (2n)!. Men kan (a) ook eenvoudig inzien door op te merken dat (2n)! zeker n even factoren bevat, waardoor 2n | (2n)!. Als n ≥ 2 dan zit ook 4 = 22 onder deze factoren, zodat 2n+1 | (2n)!. Dit betekent dat (2n)! 2n even is. Opgeloste oefeningen Relaties en Structuren, hoofdstuk 7

48

n2 ! met alle ni gelijk aan n en c = n2 ! − (2n + 1)n. Dit b. Beschouw het multinomiaalgetal n1 ,n2 ,...,n ,c 2n+1 multinomiaalgetal is gedefinieerd zodra n2 ! ≥ n(2n + 1), en in dat geval is b. bewezen. Inderdaad: als n ≥ 2, dan is n2 ! ≥ n2 (n2 − 1) ≥ n · n · (n + 1) ≥ n · 2 · (n + 1) ≥ n · (2n + 1). Voor n ∈ {0, 1} vinden we 1 | 1, wat ook waar is.


49

6 Ringen, lichamen, velden

Recommend Documents