principe des tiroirs

Imaginez 13 personnes et seulement 12 mois de naissance possibles. Même sans connaître leurs dates d’anniversaire, deux personnes au moins sont nécessairement nées le même mois.

Les personnes jouent le rôle des objets, et les mois celui des tiroirs. Dès qu’il y a plus d’objets que de tiroirs, tous les tiroirs ne peuvent pas contenir au plus un objet. Le principe garantit donc un regroupement, mais il ne dit pas dans quel tiroir il se trouve.

Le principe des tiroirs, aussi appelé principe de Dirichlet ou pigeonhole principle, est un argument de combinatoire qui établit l’existence d’une répétition. Dans sa forme élémentaire, si l’on place n + 1 objets dans n tiroirs, où n est un entier positif, un tiroir contient au moins deux objets. Les objets et les tiroirs peuvent être abstraits : personnes et mois de naissance, entiers et restes, ou éléments d’un ensemble et valeurs prises par une fonction.

Dans la forme générale, m désigne le nombre d’objets et n le nombre de tiroirs, avec m et n entiers positifs. Si chaque objet est affecté à l’un des n tiroirs, au moins un tiroir contient au minimum $\lceil m\mathrm{/}n\rceil \backslash lceil\; m/n\; \backslash rceil$ objets. Cette conclusion équivaut à dire qu’il en contient strictement plus que $\lfloor (m-1)\mathrm{/}n\rfloor \backslash lfloor\; (m-1)/n\; \backslash rfloor$.

En termes d’ensembles finis, si l’ensemble de départ E possède plus d’éléments que l’ensemble d’arrivée F, toute fonction de E vers F est non injective : deux éléments distincts de E ont la même image dans F. L’argument prouve qu’un tel couple existe sans nécessairement l’identifier.

Un groupe compte 13 personnes. On veut montrer que deux d’entre elles au moins ont leur anniversaire le même mois, sans connaître aucune date précise. Les données sont les suivantes : 13 personnes à répartir et 12 mois possibles. Chaque personne est placée dans le tiroir correspondant à son mois de naissance.

1. Les 13 personnes sont les objets.
2. Les 12 mois sont les tiroirs.
3. Comme 13 = 12 + 1, il y a un objet de plus que de tiroirs.
4. Le principe impose donc qu’un mois contienne au moins deux personnes.

Le résultat garanti est au moins 2 personnes nées pendant un même mois. Pour contrôler le raisonnement, supposons au contraire que chaque mois contienne au plus une personne : les 12 mois accueilleraient alors au plus 12 personnes, ce qui contredit l’effectif de 13. La figure présente une répartition possible qui rend cette collision visible.

Dans un problème d’existence, on cherche d’abord une classification finie : les objets deviennent les éléments étudiés et les tiroirs, les catégories possibles. Si le nombre d’objets dépasse le nombre de catégories, une catégorie répétée est certaine.

Pour obtenir une garantie chiffrée, on divise le nombre d’objets par celui des tiroirs et on arrondit au supérieur. Avec 25 objets et 12 tiroirs, un tiroir en contient au moins 3, car $\lceil 25\mathrm{/}12\rceil =3\backslash lceil\; 25/12\; \backslash rceil=3$.

Si le problème demande quel tiroir est surchargé, le principe seul ne suffit pas. Il faut alors examiner la répartition ou employer une construction explicite ; le critère est l’identification d’un cas précis, et non la seule preuve de son existence.

Avec le paradoxe des anniversaires. Le principe des tiroirs donne une certitude dès que 13 personnes sont classées par mois de naissance. Le paradoxe des anniversaires étudie plutôt une probabilité de coïncidence entre dates précises ; avec 13 personnes, une date commune n’est pas garantie.

Avec un simple calcul de moyenne. La moyenne vaut m/n objets par tiroir, mais elle peut ne pas être entière. Le principe transforme cette moyenne en une conclusion sur au moins un tiroir : sa charge atteint l’entier supérieur. Par exemple, une moyenne de 13/12 impose une charge d’au moins 2.

Pas de dépassement, pas de collision garantie. Avec 12 objets et 12 tiroirs, chaque tiroir peut recevoir exactement un objet. Il faut donc vérifier le seuil : pour garantir une paire dans n tiroirs, il faut au moins n + 1 objets.

Une affectation doit être bien définie. Chaque objet doit être associé à un tiroir parmi les n tiroirs comptés. Si un objet peut rester hors classement ou si les catégories ne couvrent pas tous les cas, le dénombrement annoncé ne justifie plus la conclusion.

La borne est un minimum garanti. Pour m objets et n tiroirs positifs, un tiroir contient au moins $\lceil m\mathrm{/}n\rceil \backslash lceil\; m/n\; \backslash rceil$ objets, mais il peut en contenir davantage. Avec 25 objets et 12 tiroirs, la garantie vaut 3, pas exactement 3.

Existence ne signifie pas localisation. Le raisonnement révèle qu’une répétition est inévitable, sans désigner les objets concernés. Pour les trouver, il faut inspecter les catégories ou ajouter un argument constructif.

L’analyse combinatoire replace ce raisonnement d’existence parmi les méthodes qui organisent et dénombrent des configurations finies.