Principe combinatoire qui affirme que lorsque des objets discrets sont placés dans un nombre moindre de conteneurs, au moins un conteneur contient plus d'un objet.

Principe

Si n+1 objets ou plus sont affectés à n conteneurs, alors un conteneur contient au moins deux objets ; en général, si m objets sont placés dans n boîtes, il existe une boîte contenant au moins ⌈m/n⌉ objets.

Démonstration

Si l'on place 13 chaussettes dans 12 tiroirs, au moins un tiroir contient au moins deux chaussettes. Dans l'exemple des anniversaires, avec 367 personnes et 366 dates possibles (avec le 29 février), deux personnes ont la même date d'anniversaire.

Mauvaise application

Utiliser le principe pour déduire quel conteneur est surchargé, déduire des fréquences probabilistes à partir d'une assertion d'existence déterministe, ou l'appliquer à des distributions continues non discrétisées sans précautions.

Conséquence

Permet des preuves d'existence simples et des bornes inférieures en combinatoire, théorie des nombres et informatique ; il assure l'existence de collisions ou de doublons sans identifier constructivement où ils se produisent.

Inversion

Si le nombre d'objets est inférieur à celui des conteneurs, il est possible que tous les conteneurs soient vides ou contiennent au plus un objet ; l'existence d'un conteneur non vide n'est pas garantie dans ce sens.

Limite

S'applique aux allocations finies et discrètes ou à des situations pouvant être discrétisées en un nombre fini de cases ; il ne quantifie pas combien de cases sont surchargées au-delà de l'existence et requiert une définition claire d'objet et de contenant.

Tension sémantique

Tension entre l'affirmation d'existence déterministe et les interprétations statistiques ou probabilistes (probabilité de collision, occupation attendue) : ces interprétations demandent des hypothèses supplémentaires.

Synthèse

Le principe des tiroirs est une loi combinatoire d'existence minimale : devant une allocation finie d'objets discrets dans un nombre moindre de conteneurs distingués, il garantit l'existence d'au moins un conteneur contenant plusieurs objets, outil fondamental pour des preuves non constructives et des arguments de collision.