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.