Oefeningen op hoofdstuk 3
Combinatoriek 3.1
Het duivenhokprincipe
Oefening 3.1. Geraldine heeft twaalf roze kousen, zes appelblauwzeegroene en tien gele allemaal door elkaar in haar lade. Het is pikdonker in de kamer. Hoeveel enkele kousen moet Geraldine meenemen om er zeker van te zijn dat ze ´e´en paar bij elkaar horende kousen heeft? En hoeveel moet ze er nemen als er ´e´en oranje kous tussenzit? Oefening 3.2. Bewijs dat een willekeurige verzameling van 12 gehele getallen ten minste 2 elementen bezit waarvan het verschil deelbaar is door 11. Oefening 3.3. Hoeveel elementen moet een deelverzameling M van {1, . . . , 999} minstens hebben om alleszins twee verschillende elementen met som 1000 te bevatten? Oefening 3.4. Zij gegeven een rij van m gehele getallen a1 , a2 , a3 , · · · , am . Toon aan dat er een aantal ai ’s kunnen gevonden worden zodanig dat ze elkaar opvolgen in de rij en dat hun som deelbaar is door m. Oefening 3.5. Veronderstel dat X een deelverzameling is van {1, . . . , 2n} van kardinaliteit n + 1. Bewijs dat steeds minstens ´e´en van de elementen van X een deler is van een ander element van X zodanig dat het quoti¨ent even is. Oefening 3.6. In het eenheidsvierkant liggen 51 punten. Bewijs dat er een cirkelschijf met straal 1/7 bestaat die minstens 3 van de 51 punten bedekt. Oefening 3.7. Bewijs dat in een groep van 6 personen er steeds drie mensen gevonden kunnen worden die ofwel elkaar ooit eens ontmoet hebben, ofwel elkaar nooit ontmoet hebben.
3.2
Dubbele telling
Probeer alle oefeningen op te lossen door het principe van dubbele telling toe te passen.
Oefeningen Relaties en Structuren, Combinatoriek
38
Geef eerst een beschrijving van de koppels (x, y) die je telt: een beschrijving van x, beschrijving van y en de relatie tussen x en y. Tel dan het aantal koppels op twee manieren om de gezochte informatie te vinden. Oefening 3.8. Veronderstel dat we een aantal verschillende deelverzamelingen van N<8 beschouwen zodanig dat elke deelverzameling 4 elementen bevat en dat elk element van N<8 tot 3 dergelijke deelverzamelingen behoort. Hoeveel dergelijke deelverzamelingen zijn er dan? Oefening 3.9. Is het mogelijk om een verzameling van deelverzamelingen van N<8 te vinden zodanig dat elke deelverzameling 3 elementen bevat, en zodanig dat elk element van N<8 tot 5 deelverzamelingen behoort? Oefening 3.10. 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 |. Oefening 3.11. 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 ´e´en positie een verschillend element hebben. Bijvoorbeeld (0, 0, 0) wordt verbonden met (0, 0, 1) maar niet met (1, 1, 0). a. Hoeveel hoekpunten heeft deze figuur? b. Heeft deze figuur driehoeken? c. Heeft deze figuur vierhoeken? d. Tot hoeveel ribben behoort elk hoekpunt? e. Bepaal hoeveel ribben deze figuur heeft aan de hand van een dubbele telling. f. Bepaal hoeveel vierhoeken deze figuur heeft aan de hand van een dubbele telling. g. Welk ruimtelichaam stelt deze figuur voor? Oefening 3.12. De vier-dimensionale kubus kan als volgt geconstrueerd worden: de hoekpunten zijn de geordende viertallen (a1 , a2 , a3 , a4 ) waarbij a1 , a2 , a3 , a4 ∈ {0, 1}. Twee hoekpunten worden verbonden door een ribbe als ze slechts in ´e´en positie een verschillend element hebben. a. Tel het aantal hoekpunten van de vierdimensionale kubus. b. Bepaal door een dubbele telling het aantal ribben en vierhoeken van de vierdimensionale kubus. c. Tot hoeveel kubussen behoort elke vierhoek van de vierdimensionale kubus?
Oefeningen Relaties en Structuren, Dubbele telling
39
d. Maak gebruik van dubbele telling om te bepalen hoeveel kubussen er in de vierdimensionale kubus zitten. e. Maak gebruik van dubbele telling om te bepalen tot hoeveel kubussen van de vierdimensionale kubus elke ribbe behoort.
Figuur 3.1: Twee voorstellingen van een vierdimensionale kubus.
Oefening 3.13. 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? Oefening 3.14. 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. Oefening 3.15. 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? Oefening 3.16. Hoeveel diagonalen heeft een n-hoek? Oefening 3.17. Een tuinaanlegger wil 10 bomen op een originele manier planten. Hij wil 5 rijen van vier bomen bekomen. Hoe kan hij dat doen? Oefening 3.18. 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 ´e´en van de twee meespeelt). Er zijn 36 wedstrijden gepland. Hoeveel leerlingen nemen deel aan deze competitie? Oefening 3.19. 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 ´e´en sleutel is die op beide deuren past maar op geen enkele andere. Elke sleutel hangt buiten in een kastje dat op zijn Oefeningen Relaties en Structuren, Dubbele telling
40
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?
3.4
Combinatieleer
Variaties, combinaties, Stirlinggetallen, multinomiaalgetallen Oefening 3.20. 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? Oefening 3.21 (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. Oefening 3.22. Hoeveel strings van 11 letters kunnen we maken met de letters uit het woord MISSISSIPPI? Oefening 3.23. 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. Oefening 3.24. Op hoeveel manieren kan je 24 mensen aan 4 ronde tafels van 6 personen plaatsen? Oefening 3.25. 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? Oefening 3.26. Op hoeveel manieren kan men mn voorwerpen verdelen over m dozen zodanig dat elke doos juist n elementen bevat? Oefening 3.27. Op de busticketjes in Belgrado, Servi¨e staan de cijfers van 1 tot en met 9, zoals ze op een telefoon zijn afgebeeld. 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 complementair door 346789). a. Hoeveel verschillende manieren zijn er om drie gaatjes in deze kaartjes te knippen?
Oefeningen Relaties en Structuren, Combinatieleer
41
b. Hoeveel verschillende manieren zijn er om drie gaatjes in deze kaartjes te knippen, waarbij er geen drie opeenvolgende cijfers uitgeknipt worden? c. 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 ´e´en 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. Oefening 3.28 (Herexamen 2013). • Hoeveel anagrammen bestaan er van het woord aardappelpuree? Hoeveel daarvan beginnen ook met (minstens) twee a’s? Hoeveel beginnen met precies twee a’s? • Hoeveel permutaties van de 26 letters van het alfabet bevatten geen enkele van de aaneensluitende lettersequenties: kat en muis? Oefening 3.29 (Herexamen 2012). • Hoeveel getallen in N[0, 9999] bestaan er, zodat hun cijfers van links naar rechts telkens strikt stijgen? • Hoeveel getallen in N[0, 9999] bestaan er, zodat hun cijfers van links naar rechts stijgen (i.e. stijgen of gelijk blijven)? Oefening 3.30 (Examen 2013). Een kolom bestaat uit 4 punten onder elkaar. Een punt kan wit, zwart of oranje zijn. We noemen een kolom overheersend zwart als hij minstens 2 zwarte punten bevat, en analoog voor de andere kleuren. a.
• Op hoeveel manieren kan een kolom gekleurd zijn? • Hoeveel kolommen zijn overheersend wit? • Hoeveel kolommen zijn tegelijk overheersend wit en overheersend oranje? • Hoeveel kolommen bevatten alledrie de kleurtjes?
b. We zetten 19 kolommen in een cirkel, zodat we een cilinder van vier punten hoog krijgen. Toon aan dat er altijd een rechthoek met gelijkgekleurde hoekpunten kan gevonden worden. Oefeningen Relaties en Structuren, Combinatieleer
42
(F) [Bonus] Hoeveel zo’n cilinders kan men maken? (+ bewijs)
Oefeningen Relaties en Structuren, Combinatieleer
43
Tellen in de verzamelingenleer Oefening 3.31. Beschouw A = {1, . . . , 6}. Hoeveel relaties in A zijn equivalentierelaties? Oefening 3.33. Beschouw een verzameling A met n elementen. a. Hoeveel relaties zijn er over A? b. Hoeveel reflexieve relaties zijn er over A? c. Hoeveel antireflexieve relaties zijn er over A? d. Hoeveel relaties over A zijn reflexief en symmetrisch? e. Hoeveel symmetrische relaties zijn er over A? f. Hoeveel antisymmetrische relaties zijn er over A? g. Hoeveel relaties over A zijn noch symmetrisch, noch antisymmetrisch? Oefening 3.34. Beschouw 2 verzamelingen A en B met respectievelijk m en n elementen, waarbij m ≥ n. Hoeveel surjecties zijn er van A op B? Oefening 3.37 (Examen 2012). Hoeveel relaties op een verzameling met n elementen zijn tegelijk reflexief, niet-transitief en symmetrisch?
Combinatorische bewijzen Oefening 3.42. De volgende formules kunnen eenvoudig bewezen worden, door gepaste keuzes van a en b in het binomium van Newton. Bewijs ze alternatief, door een verzamelingstheoretisch argument of een rechtstreekse inductie. n X n = 2n k k=0 n X n (−1)k =0 k k=0
Oefening 3.45. Bewijs de volgende identiteiten voor de Stirlinggetallen. a. S(n, 2) = 2n−1 − 1 b. S(n, n − 1) = n2 Oefening 3.48 (Herexamen 2013). Bewijs dat
Pd
n k=0 k
=
n+1 d
.
Oefening 3.49 (Examen 2013). Toon aan dat als m ≥ n, n X n k! S(m, k) = nm k k=1
Oefeningen Relaties en Structuren, Combinatieleer
44
