Samenvatting Hoofdstuk 2: Eenvoudige Principes van de Discrete Wiskunde

Hoofdstuk 2: Eenvoudige principes van de
discrete wiskunde
1 De duiventil
Stelling (principe van de duiventil):
Als we n identieke objecten verdelen over k dozen met n > k, dan is er minstens 1 doos met
minstens 2 objecten.
Bewijs:
Uit het ongerijmde:
Veronderstel van niet. Dan is er in elke doos hoogstens 1 object. Zij m het aantal lege dozen.
Dan zijn er in totaal k – m dozen met juist 1 object. Vermits alle objecten verdeeld werden,
geldt:
𝑛 =𝑘−𝑚 ≤𝑘 <𝑛
En dat is een tegenspraak. ∎

1.1 Toepassing duiventil
Gevolg van de duiventil:
In de eerste 2013 elementen van de rij 7, 77, 777, … zit minstens 1 veelvoud van 2013.
Bewijs:
We noteren de eerste elementen van de rij 𝑎1 , 𝑎2 , … , 𝑎2013. Voor twee getallen a en b kunnen
we steeds quotiënt q en rest r bepalen zodat 𝑎 = 𝑞𝑏 + 𝑟 met 0 ≤ 𝑟 < 𝑏. Doe dit nu voor alle
getallen in de rij. Dus ∀ 𝑖 ∈ {1, … ,2013} bepalen we de 𝑞𝑖 en 𝑟𝑖 zo dat 𝑎𝑖 = 2013𝑞𝑖 + 𝑟𝑖 .
Als er een i bestaat met ri = 0, dan is ai deelbaar door 2013 en is er niets meer te bewijzen.
Veronderstel nu, uit het ongerijmde, dat geen enkele ri nul is. Dan is {𝑟1 , 𝑟2 , … , 𝑟2013 } een
deelverzameling van {1, 2, …, 2012}, de mogelijk niet-nulle resten bij deling door 2013. De
duiventil leert ons minstens 2 resten gelijk zijn. Dus ∃𝑖 ≠ 𝑗 ∈ {1,2, … ,2013} met 𝑟𝑖 = 𝑟𝑗 . We
mogen, zonder verlies van algemeenheid, aannemen dat 𝑎𝑖 > 𝑎𝑗 .

Bekijk nu het verschil 𝑎𝑖 − 𝑎𝑗 . Dit is enerzijds gelijk aan:




Of dus 𝑎𝑖 − 𝑎𝑗 = 77 … 77 × 10𝑗 .

Anderzijds is 𝑎𝑖 − 𝑎𝑗 = (2013𝑞𝑖 + 𝑟𝑖 ) − (2013𝑞𝑗 + 𝑟𝑗 ) = 2013(𝑞𝑖 − 𝑞𝑗 ) + 0, aangezien 𝑟𝑖 = 𝑟𝑗 .
Dus 𝑎𝑖 − 𝑎𝑗 = 𝑎𝑖−𝑗 × 10𝑗 is een veelvoud van 2013. Dit wil zeggen dat 𝑎𝑖−𝑗 × 10𝑗 deelbaar is
door 2013, maar vermits 10𝑗 geen enkele deler gemeenschappelijk heeft met 2013, moet
𝑎𝑖 − 𝑎𝑗 een veelvoud zijn van 2013. We bekomen een tegenspraak en dus is het
tegengestelde bewezen. ∎

1

, Notatie:
Zij 𝑥 ∈ ℝ. Dan noteren we:
⌈𝑥⌉ = 𝑘𝑙𝑒𝑖𝑛𝑠𝑡𝑒 𝑔𝑒ℎ𝑒𝑒𝑙 𝑔𝑒𝑡𝑎𝑙 ≥ 𝑥
⌊𝑥⌋ = 𝑔𝑟𝑜𝑜𝑡𝑠𝑡𝑒 𝑔𝑒ℎ𝑒𝑒𝑙 𝑔𝑒𝑡𝑎𝑙 ≤ 𝑥

Veralgemeende duiventil:
𝑛
Als je n identieke objecten verdeelt over k dozen, dan is er minstens 1 doos met minstens ⌈ ⌉
𝑘
objecten. Het bewijs is analoog met dat van de gewone duiventil.

1.2 Toepassing veralgemeende duiventil
In een groep van 6 mensen zijn elke 2 individu’s ofwel vrienden ofwel vijanden. Men kan met
zekerheid zeggen dat er in deze groep drie mensen zijn die ofwel 2 aan 2 vrienden zijn,
ofwel 2 aan 23 vijanden.
Bewijs:
Zij A een van die personen. De overblijvende 5 personen vallen uiteen in 2 groepen: de
vrienden van A en de vijanden van A. Door het veralgemeend principe van de duiventil bevat
5
1 van die 2 groepen minstens ⌈ ⌉ = 3 personen. Onderstel dat we dus minstens 3 vrienden
2
hebben (het geval dat er minstens 3 vijanden zijn verloopt analoog). We noemen B, C, D drie
van die vrienden. Als 2 van de 3 bevriend zijn is het bewijs gedaan. Als geen 2 van de drie
vriend zijn, hebben we 3 personen gevonden die 2 aan 2 vijanden zijn. ∎




2 Eenvoudige teltechnieken
Als we objecten tellen in dozen (zoals in het vorige deel) komt het er eigenlijk op neer dat we
elementen tellen in disjuncte verzamelingen.

2.1 Tellen
Stelling:
Twee eindige verzamelingen A en B bevatten evenveel elementen als en slechts als er een
bijectie A ←→ B bestaat.
Formeel definiëren wat we bedoelen met “aantal elementen in een eindige verzameling”.

• elementen van een verzameling A tellen
o komt eigenlijk overeen mat nummeren van de elementen van A.
▪ neem een eerste element weg uit de verzameling, dan een tweede
enz. tot er geen meer zijn
• Dit resulteert in een bijectie f tussen de verzameling {1, 2, . . . , n} en A met f(i) = i-de
element van A in onze selectie.

2