Duivenhok principe

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.

 

Het duivenhokprincipe

Als je 5 ballen moet verdelen over 4 dozen, dan zal er een doos zijn met minstens 2 ballen. Immers de eerste 4 ballen kan je nog over de 4 dozen verdelen, maar voor het 5 de balletje is er geen doos meer over. Algemeen: verdeel je meer dan n objecten over n laden, dan bevat minstens één lade minstens 2 van die objecten. Dit eenvoudig principe werd voor het eerst expliciet gebruikt door Dirichlet (1805 – 1859) en wordt daarom ook het  ladenprincipe of duivenhokprincipe van Dirichlet  genoemd. Het principe kan in een nog algemenere vorm gegoten worden: Als je kq+r ( met q,r \in \mathbb{N} en 1<r<k ) objecten verdeelt over k laden, dan is er minstens \’e\’en lade met minstens q objecten.

Een voorbeeld:

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.