Combinatoriek-mix groep 2 Trainingsweekend, november 2011 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 • 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 Definities: • Voor een geheel getal n ≥ 1 defini¨eren we n! = n · (n − 1) · · · · · 2 · 1 (spreek uit: n-faculteit). • Nu is n! het aantal manieren om n verschillende objecten op een rij te zetten. 1
• We defini¨eren 0! = 1. (Je kunt 0 objecten op precies 1 manier op een rij zetten.) n! • Voor gehele getallen n en k met n ≥ 0 en 0 ≤ k ≤ n defini¨eren we nk = k!(n−k)! . • Voor gehele getallen n en k met n ≥ 0 en niet 0 ≤ k ≤ n (dus of k < 0 of k > n) n defini¨eren we k = 0. • Nu is nk is het aantal manieren om k objecten uit n te kiezen, waarbij de volgorde niet uitmaakt. Eigenschappen binomiaalco¨effici¨enten (deze eigenschappen kun je zelf bewijzen met behulp van de definities): • Voor gehele getallen n en k met n ≥ 0 en 0 ≤ k ≤ n geldt
n k
n n−k
=
• Voor gehele getallen n en k met n ≥ 1 en 0 ≤ k ≤ n − 1 geldt
n k
+
. n k+1
=
n+1 k+1
.
Het binomium van Newton: voor gehele n ≥ 0 geldt n X n n−2 2 n n n−i i n n−1 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.) Toepassing: vul x = y = 1 in, dan staat er n X n i=0
i
= 2n .
Nog een toepassing: 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. Ja, 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 paaseieren die ik wil verven in de kleuren blauw, rood, geel en paars. Op hoeveel manieren kan dat? 2
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 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 23 dat het aantal manieren om de eieren te verven gelijk is aan 3 .
Opgaven Opgave 1 Bewijs dat voor positieve gehele n geldt: 2n 2n 2n 1 . − = n+1 n n n−1 Opgave 2 Bewijs dat voor positieve gehele n geldt: n X 2n 1 2n 2n−1 =2 + . k 2 n k=0 Opgave 3 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 4 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 3
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 5 Zij S een deelverzameling van {1, 2, . . . , 2011} zodanig dat S geen twee getallen bevat die 3 of 5 verschillen. Hoeveel elementen bevat S ten hoogste? Opgave 6 Bereken 49 X
99 (−1) · . 2k k=0 k
Opgave 7 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
min(`,n)
X k=max(0,`−m)
n m . k `−k
Opgave 8 Een groep van n man-vrouw-paren 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 9 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 10 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. 4
Opgave 11 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 12 Bewijs dat voor niet-negatieve gehele n geldt:
Pn
1 k=0 2k
·
n+k k
= 2n
Opgave 13 Bewijs dat voor positieve gehele n geldt: n X n−i X (−1)j i=0 j=0
i!j!
= 1.
Opgave 14 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 van zulk soort wedstrijdverlopen zijn. (Dit zijn de zogenaamde CaBewijs dat er n+1 n talangetallen.)
5
