Verdeel je meer dan n duiven over n hokken, dan bevat minstens één hok minstens 2 van die duiven. Over dit duivenhok principe hebben we het gehad op een andere pagina van deze website. Het is niet altijd even gemakkelijk om de juiste ‘hokken’ te kiezen om alzo het principe te kunnen toepassen. Volgende opgaven lijken op elkaar, maar toch is de keuze van de ‘hokken’ totaal anders.

Kies 51 getallen uit de verzameling {1,2,3,…,100}. Toon aan dat :

er in die 51 getallen twee getallen bestaan die geen gemeenschappelijke priemdeler hebben.
er in die 51 getallen twee getallen bestaan zodat de ene een deler is van de andere.

Voor de eerste vraag neem je 50 paar opeenvolgende koppels: (1,2),(3,4),…,(99,100). Vermits er 51 getallen gekozen worden, moet er daartussen dus zeker een paar (k,k+1) zitten. Als k en k+1 een zelfde priemdeler p zouden hebben zou p ook een deler zijn van (k+1)-k=1 en dat kan niet. Dus k en k+1 hebben geen gemeenschappelijke priemdeler.

Voor het tweede probleem neem je de 50 oneven getallen 1,3,5,…,99. Voor elk van die getallen vorm je een ‘hok’ met daarin het oneven getal en alle producten ervan met machten van 2. Zo bevat het eerste hok de elementen 1,2,4,8,16,32,64 en het tweede hok de elementen 3,6,12,24,48,96. Volgens het duivenhok principe moeten er tussen de 51 gekozen getallen er zeker twee zijn die in hetzelfde hok zitten. Die twee getallen zijn dan van de vorm $2^m.k$ en $2^n.k$ met k een oneven getal. Het is duidelijk dat het ene getal het andere deelt.

Neem willekeurig $n+1$ getallen uit de verzameling $\{1,2,\cdots,2n \}$ . Bewijs dat er in die $n+1$ getallen steeds een getal bestaat dat deelbaar is door een ander van die $n+1$ getallen.

Neem $n+1$ getallen en noteer die door $a_1,a_2,\cdots,a_{n+1}$ en schrijf ze in de vorm $a_i=2^k.b_i$ waarin $b_i$ oneven is.

We hebben $n+1$ oneven getallen $b_i$ , allen uit het interval $\left[1,2n-1\right]$ .

In het interval $\left[1,2n-1\right]$ zijn er maar $n$ oneven getallen.

Volgens het duivenhokprincipe moeten er dus een $p$ en een $q$ bestaan zodat $b_p=b_q$ . Dan is één van de getallen $a_p$ of $a_q$ deelbaar door het andere.

Wiskunde is leuk

Tag archieven: principe van dirichlet

Duivenhok principe

Kies 51 getallen uit de verzameling {1,2,3,…,100}. Toon aan dat :

er in die 51 getallen twee getallen bestaan die geen gemeenschappelijke priemdeler hebben.

er in die 51 getallen twee getallen bestaan zodat de ene een deler is van de andere.

Het duivenhokprincipe

Neem willekeurig $n+1$ getallen uit de verzameling $\{1,2,\cdots,2n \}$ . Bewijs dat er in die $n+1$ getallen steeds een getal bestaat dat deelbaar is door een ander van die $n+1$ getallen.

Kies 51 getallen uit de verzameling {1,2,3,…,100}. Toon aan dat :

er in die 51 getallen twee getallen bestaan die geen gemeenschappelijke priemdeler hebben.

er in die 51 getallen twee getallen bestaan zodat de ene een deler is van de andere.

Neem willekeurig getallen uit de verzameling . Bewijs dat er in die getallen steeds een getal bestaat dat deelbaar is door een ander van die getallen.

Neem willekeurig $n+1$ getallen uit de verzameling $\{1,2,\cdots,2n \}$ . Bewijs dat er in die $n+1$ getallen steeds een getal bestaat dat deelbaar is door een ander van die $n+1$ getallen.