Nieuwe pagina 1

© h.hofstede (h.hofstede@hogeland.nl)

Zet een rij dozen met nummers 3,4,5,... naast elkaar.
Knip het veelvlak uit elkaar en leg elk vlak in een doos waarvan het nummer overeenkomt met het aantal zijden van het betreffende vlak. Stel dat alle vlakken in een verschillende doos kunnen en dat er n vlakken zijn.
Dan zijn er dus n dozen gevuld.
Omdat de dozen 1 en 2 leeg blijven zijn dus in ieder geval ook de dozen met de nummers n + 1 en n + 2 (of hoger) gevuld.
Maar als de doos met nummer n + 1 gevuld is, dan is er dus een vlak met n + 1 zijden.
Maar omdat al die n + 1 zijden aan nieuwe vlakken grenzen zijn er dus minstens n + 2 vlakken.
Dat is tegenstrijdig met het feit dat er slechts n vlakken waren.
Dus kunnen niet alle vlakken in een verschillende doos.

De totale som van de 10 getallen is hoogstens 945 (de 10 grootsten), dus de som van een deelverzameling varieert van 1 tot 945. (de duivengaten)
Het aantal verschillende deelverzamelingen (niet leeg) uit 10 getallen dat je kunt maken is 2¹⁰ - 1 = 1023 (elk getal hoort wel of niet bij de deelverzameling) Dit zijn de duiven.
Omdat er meer duiven dan gaten zijn moeten er dus minstens twee duiven in hetzelfde gat........

Sterker nog: je kunt ook altijd twee deelverzamelingen vinden die geen overlapping hebben.
Immers als twee deelverzamelingen met overlapping toegestaan mogelijk zijn, dan zijn die zonder overlapping óók mogelijk; laat gewoon de dubbelen weg, daarmee blijft de som van beiden gelijk!

Noem de N verschillende getallen a₁, a₂, ..., a_N
Construeer nu een nieuwe rij getallen:

b₁ = a₁ mod N
b₂ = (a₁ + a₂) mod N
b₃ = (a₁ + a₂ + a₃) mod N
...

Als er één van deze b's nul is hebben we een serie gevonden die bij delen door N rest nul geeft en zijn we dus klaar.

Neem dus aan dat de b-getallen geen van allen nul zijn.
Dan zijn er twee series:

1. de getallen 1,2,... N - 1 (de gaten; n-1 stuks)
2. de getallen b_i (de duiven: n stuks)
Dus moeten er volgens het pigeon-hole principe wel twee dezelfde b's zijn.
stel dat b_i = b_jDan is echter (a_i+1 + ... + a_j)mod N = 0 dus is deze serie deelbaar door N.

Noem de getallen A
Stel dat de rest bij delen door N-1 gelijk is aan R_A
Dan zijn er N getallen R_A (de duiven)
De resten R kunnen gelijk zijn aan 0 t.m. N-2 (de gaten)
Pigeon-Hole: Er moeten dus minstens 2 resten gelijk zijn.
Maar als twee verschillende getallen bij delen door N-1 dezelfde rest hebben, dan is hun verschil deelbaar door N-1.

Stel dat ons getal n is.
Bekijk dan alle getallen modulo n
Daar zijn er n van.
Bekijk ook de verzameling { 1 , 11 , 111 , 1111 , ......, 11111111.......} waarbij het laatste getal bestaat uit n + 1 enen.
Die verzameling heeft n + 1 elementen.
Dus als we deze verzameling modulo n opschrijven dan staat er zeker een dubbele bij.
Trek de getallen die bij deze dubbelen horen van elkaar af, dan heb je het gezochte veelvoud.

vb:
neem n = 12
{1 , 11 , 111, 1111, .....} modulo 12 wordt {1 , 11 , 3 , 7 , 11 , .... }
Daar is ie al: de 11 is de eerste dubbele, dus 11111 - 11 = 11100 is een veelvoud van 12.
(het is inderdaad 925 • 12)

Dat brengt je natuurlijk op het idee van een uitbreiding:

Elk getal, dat geen veelvoud van 2 of 5 is, heeft een veelvoud dat alleen uit enen bestaat.

Immers; bovenstaande procedure levert ons een getal van de vorm 1111......00000.....
Als we de nullen weglaten delen we eigenlijk door 10ⁿ dus door 2ⁿ • 5ⁿ .
Het resultaat is dan nog steeds een veelvoud van n (mits n geen veelvoud van 2 of 5 is)

Als één van de cijfers van het getal 0, 1, 4 of 9 is, is de stelling meteen bewezen, want dan is het ene cijfer al een kwadraat.
Laten we daarom aannemen dat het getal bestaat uit de cijfers 2,3,5,6,7,8
In de priemfactorontbinding daarvan komen alleen de priemgetallen 2, 3, 5 en 7 voor.

Elk product dat we gaan bekijken is van de vorm 2^a • 3^b • 5^c • 7^e

Bekijk het even of oneven zijn van de machten a, b, c en d.
Omdat elke macht even of oneven is zijn er in totaal 2⁴ = 16 mogelijke klassen daarvoor.

Noem de cijfers van het getal c₁c₂c₃...c₁₆
Dan zijn er 16 producten die beginnen met c₁, namelijk c₁, c₁c₂, c₁c₂c₃, ....
Als voor één van deze producten a, b, c en d allemaal even zijn dan is dat product een kwadraat, en is wederom onze stelling bewezen.

Neem daarom aan dat geen van deze 16 producten allemaal even machten heeft (klasse {even, even, even, even})
Dan vallen dus deze 16 producten binnen de andere klassen voor (a, b, c d) en daar zijn er 15 van over.
Dus zullen minstens twee van deze producten binnen dezelfde klasse vallen.

Stel dat de producten c₁c₂ ....c_m en c₁c₂...c_n in dezelfde klasse vallen.
Als je ze dan op elkaar deelt dan heeft het resultaat alleen maar even a, b, c en d want oneven - oneven = even en ook even - even = even).

Conclusie: c_m₊₁c_m₊₂...c_n is een kwadraat.

Als er 25 mensen in 30 stoelen zitten, zijn er 5 stoelen leeg.
Die vijf stoelen verdelen de 30 stoelen in 6 groepen (eventueel van nul stoelen)
25 mensen verdelen over 6 groepen: dan moet er een groep met meer dan 5 zijn (6 • 4 = 24)

Elk team speelt 9 wedstrijden.
Omdat geen team alles verliest kan het aantal winstpartijen gelijk zijn aan 1,2,3,4,5,6,7,8 of 9
Dat zijn 9 gaten voor 10 duiven...

het aantal wedstrijden varieert van 0 tm 9.
maar als er een team met 0 is, kan er geen team met 9 zijn.
dus het aantal gespeelde wedstrijden varieert van 1 tm 9 of van 1 tm 8
dat zijn 9 mogelijkheden voor 10 teams....

Omdat ze niet meer dan 12 oefensessies per week willen hebben, zijn er maximaal 132 sessies in 11 weken.
Noem x_n het aantal sessies dat ze na n dagen gehad hebben.
Dan geldt:   1 ≤ x₁ < x₂ < ... < x₇₇ ≤ 132 (serie 1)
Tel bij elk van deze getallen 21 op. Dat geeft:   22 ≤ x₁ + 21 < x₂ + 21 < ... < x₇₇ + 21 ≤ 153 (serie 2)
Serie 1 bestaat uit 77 verschillende getallen.
Serie 2 bestaat uit 77 verschillende getallen.
In totaal dus 154 getallen (de duiven).
Omdat er tussen 1 en 153 maar 153 verschillende getallen zijn (de duivengaten), en omdat er binnen één serie geen dezelfde getallen zijn, moet wel minstens één van de getallen uit serie 1 gelijk zijn aan een getal uit serie 2.
Dus voor bepaalde n en m geldt:   x_n = x_m + 21
Maar in dat geval zijn er tussen dag n en dag m precies 21 sessies geweest.

a_i = aantal aspirines tot en met de i^de dag.
b_i = a_i + 14
Geeft samen 60 getallen, allemaal kleiner of gelijk aan 45 + 14 = 59.
Dus zijn er twee gelijk.
Dat kunnen niet 2 a's of twee b's zijn, dus moet een a gelijk zijn aan een b.

a_i = aantal wedstrijden tot en met de i^de dag.
b_i = a_i + 21
Geeft samen 144 getallen, allemaal kleiner of gelijk aan 122 + 21 = 143.
Dus zijn er twee gelijk.
Dat kunnen niet 2 a's of twee b's zijn, dus moet een a gelijk zijn aan een b.

10.

5 vrouwen met elk 7 keer spelen geeft 7 • 5 = 35 keer een vrouw die meespeelt.
Deze 35 rollen moeten over 17 voorstellingen worden verdeeld.
Met 2 in elke voorstelling zijn er maar 34, dus dat is te weinig.
Dus moet minstens één keer 3 vrouwen meedoen.

11.

Eigenlijk is dat hetzelfde als zeggen: "Er bestaan twee machten van drie waarvan het verschil deelbaar is door 1000".

Bekijk de serie 1, 3¹, 3², 3³, ..., 3¹⁰⁰⁰ die bestaat uit 1001 getallen.

Als je een getal deelt door 1000 zijn er 1000 mogelijke resten.
Volgens ons principe zijn er dus twee getallen uit de rij hierboven die de zelfde rest hebben bij delen door 1000. Dus de ene is a • 1000 + r en de andere b • 1000 + r
Het verschil van die twee is dan (a - b) • 1000 en dat is deelbaar door 1000.