1.7 Existence: Le principe des nids de pigeons

On veut montrer que dans une classe de 13 élèves, au moins deux élèves sont né le même mois. Pour ce faire, commençons par identifier nos boites et nos objets. On a donc:

Comme nous avons plus d’objets que de boites, le principe des nids de pigeon nous affirme donc qu’au moins une boite contiendra plus qu’un objet, c’est à dire qu’au moins deux élèves sont né le même mois.

Dans le cours MATH-1234, les résultats de l’examen final sont des entiers entre $\displaystyle 0$ et $\displaystyle 100$. Combien d’étudiants sont nécessaire pour être certain que deux étudiants obtiennent le même résultat ? Premièrement, remarquons qu’il y a $\displaystyle 101$ entiers entre $\displaystyle 0$ et $\displaystyle 100$, car les deux extrémités sont incluse. Il est possible qu’un étudiant obtienne $\displaystyle 0\%$, et il est possible qu’un étudiant obtienne $\displaystyle 100\%$. Intuitivement, le nombre minimal d’étudiant nécessaire devrait donc être $\displaystyle 102$. Nous allons donc le démontrer en deux étapes:

1. 1.
   ​

   Premièrement, nous voulons montrer que $\displaystyle 101$ étudiants n’est pas suffisant. Pour ce faire, un exemple est suffisant (Penser au démonstration par contre-exemple). Donc si on a $\displaystyle 101$ étudiants et que leur résultats sont respectivement:

   $$\displaystyle\{0\%,1\%,2\%,3\%,4\%,...,99\%,100\%\}$$

   alors tout les étudiants ont obtenues des résultats différent. On peut donc affirmer que dans une classe de $\displaystyle 101$ étudiants on ne peut pas être certain que deux étudiants obtiennent le même résultat.

2. 2.
   ​

   Dans un deuxième temps, on veut montrer qu’avec $\displaystyle 102$ étudiants on peut être certain que deux étudiants obtiennent le même résultat. Pour ce faire, on applique le principe des nids de pigeon:

   Objets: Les étudiants (102)

   Boites: Les différents résultats possible (101)

Par le principe des nids de pigeon, comme nous avons plus d’objet que de boite, au moins une boite contiendra plus qu’un objet, c’est à dire qu’au moins deux étudiants auront le même résultat.

Supposons que vous possédez exactement 8 paires de bas bleus, et 10 paires de bas rouges, et supposons qu’après avoir fait votre lavage, vous décidé de former des paires aléatoirement, sans tenir compte de la couleur de chaque bas. Démontrer qu’on peut être certain qu’au moins une des paires formé contiendra deux bas de la même couleur. Premièrement, remarquer qu’il est tout à fait possible qu’aucune pair ne contienne deux bas bleus (pouvez-vous trouver un exemple ?), on va donc chercher à démontrer qu’au moins une paire contiendra deux bas rouge. Pour ce faire, on applique le principe des nids de pigeons.

Par le principe des nids de pigeon, comme il y a plus d’objet que de boite, alors au moins une boite contiendra deux objets. Dans ce cas, ceci signifie qu’au moins une paire de bas contiendra deux bas rouges.

Lors d’une soirée, 20 personnes sont invités. Au début de la soirée, un certain nombre de poignées de main sont échangé. Bien entendu, personne ne se sert la main à lui même. Démontrer qu’on peut être certain qu’au moins deux des invités ont serré la main au même nombre de personnes. Ici le problème est un peu plus difficile. Il est facile d’identifier que nos objets devrait être les différents invités, mais que sont nos boites ? Comme nous voulons montrer que deux invités on serré le même nombre de poignées de main, nous allons donc choisir le nombre de poignée de main comme nos objet. Une personne pourra donc avoir serré 0 poignée de mains, 1 poignée de mains, 2 poignée de mains, … etc, jusqu’à 19 poignées de mains. il y a donc 20 possibilités pour le nombre de poignées de main. On a donc:

Le problème étant que nous avons autant d’objet que de boite. Le principe des nids de pigeons ne peut donc pas s’appliquer directement. Pour remédier au problème, il s’agit de remarquer qu’il est impossible qu’un invité n’est serré aucune poignée de mains, alors qu’un autre invité est serré la main à tout le monde. On va donc pouvoir séparer le problème en deux cas disjoint.

1. 1.
   ​

   Dans un premier temps, supposons que tout les invitées ont serrés au moins une poignée de main. Donc la boite correspondant aux personnes ayant serré aucune poignée de mains est disparu. On a donc:

   Objets: Les invités (20)

   Boites: Le nombre de poignées de main (19)

   Donc si tout les invitées on serré au moins une poignée de main, par le principe des nids de pigeons on peut être certain qu’au moins deux invités ont serré le même nombre de poignées de main.

2. 2.
   ​

   Dans un deuxième temps, supposons qu’au moins un invité n’a serré aucune poignée de main. Donc la boite correspondant aux personnes ayant serré la main de tous les autres invités est disparu. On a donc:

   Objets: Les invités (20)

   Boites: Le nombre de poignées de main (19)

   Donc si au moins un invité n’a serré la main à personne, par le principe des nids de pigeons on peut être certain qu’au moins deux invités ont serré le même nombre de poignées de main.

En combinant ces deux résultats, on peut donc conclure qu’au moins deux invités on serré la main au même nombres de personnes.

Dans un groupe de $\displaystyle 1500$ étudiants, démontrer qu’au moins deux sont né le même jour.

Par le principe des nids de pigeon, comme il y a plus d’objet que de boite, alors au moins une boite contiendra deux objets. Dans ce cas, ceci signifie qu’au moins deux étudiants sont né la même journée.

Dans un groupe de $\displaystyle 1500$ étudiants, il y en a au moins $\displaystyle\left\lceil\frac{1500}{366}\right\rceil=5$ qui sont né la même journée.