Combinatoriek groep 2 Mix: inductie, ladenprincipe, binomiaalco¨effci¨enten, paaseierenprincipe
Trainingsweekend november 2015
Theorie De opgaven in deze handout hebben allemaal wat te maken met ´e´en of meer van onderstaande onderwerpen. Belangrijk bij het maken van opgaven is om niet alleen de theorie die je kent goed gebruiken, maar om ook zelf de geschikte theorie te selecteren.
Inductie Bij een bewijs met volledige inductie bewijs je eerst de bewering voor een zekere beginwaarde n = n0 ; dit heet de inductiebasis. Vervolgens laat je zien dat uit de bewering voor een zekere n = k (de inductiehypothese) volgt dat hij ook geldt voor n = k + 1; dit heet de inductiestap. Dit moet je laten zien voor elke k ≥ n0 . Uit deze twee onderdelen volgt nu dat de bewering waar is voor alle n ≥ n0 . Soms hebben we een sterkere inductiehypothese nodig om de bewering te kunnen bewijzen voor n = k + 1, zoals de aanname dat de bewering al geldt voor n = k ´en n = k − 1 (tweestapsinductie) of de aanname bestaat uit geldigheid van de bewering voor ´alle n ≤ k (sterke inductiehypothese). Houd er bij tweestapsinductie rekening mee dat je in de inductiebasis ook de eerste twee gevallen bewijst.
Ladenprincipe Het ladenprincipe kent verschillende gedaantes: • Als je n + 1 balletjes verdeelt over n laden, dan is er minstens ´e´en lade met meer dan ´e´en balletje. • Als je kn + 1 balletjes verdeelt over n laden, dan is er minstens ´e´en lade met meer dan k balletjes. • Als je oneindig veel balletjes verdeelt over n laden, dan is er minstens ´e´en lade met oneindig veel balletjes.
Binomiaalco¨ effici¨ enten Definitie. Laat n ≥ 0 geheel zijn.
Dit materiaal behoort tot het trainingsprogramma van de Nederlandse Wiskunde Olympiade ter voorbereiding op de internationale wedstrijden.
• We defini¨eren n! als het aantal manieren om n verschillende objecten op een rij te zetten (spreek uit: n-faculteit). • Nu is n! = n · (n − 1) · · · · · 2 · 1 voor n ≥ 1. • Merk op dat 0! = 1. (Je kunt 0 objecten op precies 1 manier op een rij zetten.) • Voor gehele k met 0 ≤ k ≤ n defini¨eren we nk als het aantal manieren om k objecten uit n te kiezen, waarbij de volgorde niet uitmaakt. n! • Nu is nk = k!(n−k)! voor 0 ≤ k ≤ n. • Als niet geldt dat 0 ≤ k ≤ n (dus of k < 0 of k > n) zeggen we dat nk = 0. Lemma 1 (Eigenschappen binomiaalco¨effici¨enten). Laat n en k geheel zijn. n • Als n ≥ 0 en 0 ≤ k ≤ n, dan geldt nk = n−k . n = n+1 . • Als n ≥ 1 en 0 ≤ k ≤ n − 1, dan geldt nk + k+1 k+1 Lemma 2 (Het binomium van Newton). Voor gehele n ≥ 0 geldt n X n n−i i n n−1 n n−2 2 n n (x + y) = x y =x + x y+ x y + ··· + xy n−1 + y n . i 1 2 n − 1 i=0 n
(Herinnering: voor alle re¨ele getallen x geldt x0 = 1.) Voorbeeld. Vul x = y = 1 in in het binomium, dan staat er n X n i=0
i
= 2n .
Of vul x = 1, y = −1 in, dan staat er, voor n > 0, n X i n (−1) = (1 − 1)n = 0n = 0. i i=0 Merk op dat er voor n = 0 aan beide kanten 1 was uitgekomen, want ook voor x = 0 geldt x0 = 1.
Paaseierenprincipe Het paaseierenprincipe is een methode om slim te tellen die zich bijzonder goed laat illustreren aan de hand van een opgave over het verven van paaseieren: Voorbeeld. Ik heb 20 (identieke) paaseieren die ik wil verven in de kleuren blauw, rood, geel en paars. Op hoeveel manieren kan dat? Oplossing. Leg de eieren op een rij en verdeel ze in vier groepjes, die eventueel ook leeg mogen zijn. Het eerste groepje verven we blauw, het tweede groepje rood, het derde groepje geel en het vierde groepje paars. Het aantal manieren om de paaseieren te verven komt 2
dus overeen met het aantal manieren om de eieren in vier groepjes te verdelen, waarbij de volgorde van de groepjes uitmaakt (de verdeling (6, 4, 3, 7) is niet hetzelfde als (7, 3, 4, 6)). Stel je nu als afscheiding tussen de groepjes eieren hekjes voor; je hebt dus drie hekjes nodig. De verdeling (6, 4, 3, 7) ziet er nu uit als 0 0 0 0 0 0 + 0 0 0 0 + 0 0 0 + 0 0 0 0 0 0 0. In feite staat hier een rij van 23 symbolen, waarvan er 20 het symbool 0 zijn en 3 het symbool +. Elk zo’n rij correspondeert met precies ´e´en manier om de eieren in vier groepjes te verdelen. Het aantal manieren om zo’n rij te maken is simpelweg het aantal manieren om 3 plekken te kiezen uit 23, namelijk de 3 plekken waar de plusjes komen. We concluderen dat het aantal manieren om de eieren te verven gelijk is aan 23 . 3
Opgaven Opgave 1. Een banketbakker heeft zes soorten bonbons waaronder ook de tot “bonbon van het jaar” verkozen bonbon. Wat is het aantal mogelijkheden om (a) een doosje met 12 bonbons te vullen, (b) een doosje met 12 bonbons te vullen zodat er minimaal 2 bonbons van het jaar in zitten, (c) een groot doosje met 24 bonbons te vullen zodat er van elk type minstens 2 in zitten, (d) een doosje met 12 bonbons te vullen waarin maximaal ´e´en bonbon van het jaar zit, (e) een doosje waar maximaal 24 bonbons in kunnen te vullen (hoewel suf, het doosje zou dus leeg kunnen zijn), (f ) een grote bak met 36 bonbons vullen zodat er van elk type een oneven aantal in de bak zitten. Opgave 2. Bewijs dat voor positieve gehele n geldt: 2n 2n 1 2n − = . n+1 n n n−1 Opgave 3. Op hoeveel manieren kan je een natuurlijk getal n schrijven als som van natuurlijke getallen waarbij de volgorde uitmaakt. Voor n = 3 zijn bijvoorbeeld vier mogelijkheden; 3, 2 + 1, 1 + 2 en 1 + 1 + 1. Opgave 4. Chocoladeletters zijn er in de soorten puur, melk en wit. Jan heeft vier chocoladeletters J, van ´e´en of meer van deze soorten. Hij telt het aantal manieren waarop hij deze letters op een rij kan leggen. Vervolgens koopt hij nog een melk-letter J en nog een pure letter J en telt weer op hoeveel manieren hij zijn zes letters op een rij kan leggen. Dit aantal is precies 5 keer zo groot als het vorige aantal. Hoeveel witte chocoladeletters heeft Jan?
3
Opgave 5. Bewijs dat voor positieve gehele n geldt: n X 2n 1 2n 2n−1 =2 + . k 2 n k=0 Opgave 6. In een vierkant met zijden van lengte 1 zijn negen punten gegeven. Bewijs dat we drie van deze punten kunnen kiezen zodat de oppervlakte van de driehoek gevormd door deze punten maximaal 18 is. (Je mag zonder bewijs gebruiken dat de oppervlakte van een driehoek die geheel binnen een a × b-rechthoek ligt ten hoogste 21 ab is.) Opgave 7. In de Eerste Kamer zijn er 75 zetels te verdelen. Hoeveel manieren zijn er om deze zetels onder drie partijen te verdelen zodat elk tweetal partijen een meerderheid heeft in de kamer? Opgave 8. Het zogenaamde hockeysticklemma luidt: voor niet-negatieve gehele n en p geldt: p p X X n+k n+p+1 n+k n+p+1 = of = k p n n+1 k=0 k=0 (a) Bewijs dit lemma met inductie naar p. (b) Geef een combinatorisch bewijs van dit lemma door het aantal rijtjes met een bepaald vast aantal nullen en een bepaald vast aantal enen (hoeveel nullen en hoeveel enen?) op twee manieren te tellen. (c) Geef nog een tweede combinatorisch bewijs van dit lemma door het aantal oplossingen (x1 , x2 , . . . , xn+1 ) (met alle xi niet-negatief geheel) van de ongelijkheid x1 + x2 + · · · + xn+1 ≤ p op twee manieren te tellen. (d) Waarom heet dit eigenlijk het hockeysticklemma? (Het heet ook wel de sok van Pascal.) Opgave 9. Zij S een deelverzameling van {1, 2, . . . , 2013} zodanig dat S geen twee getallen bevat die 3 of 5 verschillen. Hoeveel elementen bevat S hooguit? Opgave 10. Bereken 49 X
99 (−1) · . 2k k=0 k
Opgave 11. Laat n, m, ` gegeven positieve gehele getallen zijn. Bewijs de volgende gelijkheid op een combinatorische manier: X n n+m n m = = ` k `−k k=0 4
min(`,n)
X k=max(0,`−m)
n m . k `−k
Opgave 12. Een groep van n man-vrouw-paren met n ≥ 2 gaat dineren aan een ronde tafel met 2n stoelen. Als je naar alle mogelijke manieren kijkt waarop men kan gaan zitten, hoeveel vrouwen zitten er dan gemiddeld naast hun eigen man? Opgave 13. Dwergen hebben vier soorten munten: gouden, zilveren, bronzen en koperen munten. Bronzen munten zijn 10 koperen munten waard, zilveren munten 100 en gouden munten 1000. Stel dat een dwerg iets wil kopen dat 2011 koperen munten kost. Op hoeveel manieren kan hij dit betalen, zonder teveel te betalen? Opgave 14. Voor alle niet-negatieve gehele n geldt 1 12 + 22 + 32 + · · · + n2 = n(n + 1)(2n + 1) 6 (a) Bewijs deze bewering met inductie. (b) Geef een combinatorisch bewijs van deze bewering door de verzameling {(x, y, z) | x, y, z ∈ {0, 1, 2, . . . , n}; x < z en y < z } op twee manieren te tellen. Opgave 15. Laat S = {1, 2, . . . , 2012}. Vind het aantal deelverzamelingen van S met precies 21 getallen, zodat de som van deze getallen deelbaar is door 4. Opgave 16. Bewijs dat voor niet-negatieve gehele n geldt:
Pn
1 k=0 2k
·
n+k k
= 2n
Opgave 17. Bewijs dat voor positieve gehele n geldt: n X n−i X (−1)j i=0 j=0
i!j!
= 1.
Opgave 18. Een voetbalwedstrijd eindigt in gelijkspel, zeg n–n. We tellen het aantal mogelijke wedstrijdverlopen waarbij de eerste club nooit achter heeft gestaan ten op zichte van de tweede club? (Een mogelijkheid is AAABBABAABBBAB.) 2n 1 Bewijs dat er n+1 van zulk soort wedstrijdverlopen zijn. (Dit zijn de zogenaamde Can talangetallen.)
5
