Langage de programmation - Mathématiques appliquées

Principe des tiroirs

Le principe des tiroirs, également appelé principe de Dirichlet, principe des cases ou pigeonhole principle en anglais, est une méthode élémentaire de dénombrement permettant de démontrer qu'une répétition, une collision ou une concentration minimale doit nécessairement se produire.

Dans sa forme la plus simple, ce principe affirme que si l'on place davantage d'objets que de tiroirs, au moins un tiroir doit contenir plusieurs objets. Il ne précise pas quel tiroir sera concerné ni quels objets s'y retrouveront, mais il garantit qu'une telle situation existe.

Malgré sa simplicité, le principe des tiroirs possède de nombreuses applications en mathématiques et en informatique. Il intervient notamment dans les fonctions de hachage, les collisions, les graphes, les tableaux, les bases de données, les réseaux, la cryptographie, les chaînes de caractères, les preuves d'existence, les bornes minimales et l'analyse des algorithmes.

Principe des tiroirs simple

La forme classique du principe des tiroirs est la suivante :

Si n+1 objets sont placés dans n tiroirs, alors au moins un tiroir contient au moins deux objets.

On peut représenter cette situation par :

Nombre d'objets > Nombre de tiroirs

Donc :

Au moins un tiroir contient
au moins deux objets

Par exemple, si 6 objets sont répartis dans 5 tiroirs, il est impossible que chaque tiroir contienne au plus un objet. Au moins un tiroir doit nécessairement en contenir deux ou davantage.

Exemple élémentaire

Supposons que l'on place 4 boules dans 3 boîtes.

Même si l'on essaie de répartir les boules aussi uniformément que possible, on peut obtenir :

Boîte 1 : 2 boules
Boîte 2 : 1 boule
Boîte 3 : 1 boule

Au moins une boîte contient donc deux boules.

Cette conclusion ne dépend pas de la manière exacte dont les objets sont répartis.

Interprétation en termes de fonction

Le principe des tiroirs peut être formulé à l'aide d'une fonction.

Considérons une fonction :

f : A → B

où :

|A| > |B|

Alors la fonction f ne peut pas être injective.

Il existe nécessairement deux éléments distincts :

x₁ ≠ x₂

tels que :

f(x₁) = f(x₂)

Les éléments de A représentent les objets et les éléments de B représentent les tiroirs.

Collision

En informatique, lorsque deux valeurs d'entrée différentes produisent la même valeur de sortie, on parle généralement de collision.

Selon le principe des tiroirs, si une fonction associe un ensemble d'entrées plus grand à un ensemble de sorties plus petit, les collisions sont inévitables.

Par exemple, une fonction transformant un nombre arbitrairement grand de fichiers en valeurs de hachage de 32 bits ne peut pas produire une valeur unique pour chaque fichier possible.

Principe généralisé des tiroirs

La forme généralisée du principe affirme que si N objets sont répartis dans k tiroirs, alors au moins un tiroir contient au moins :

⌈N/k⌉

objets.

La notation :

⌈x⌉

désigne le **plafond** de x, c'est-à-dire le plus petit entier supérieur ou égal à x.

Exemple du principe généralisé

Supposons que 100 fichiers soient répartis dans 9 dossiers.

Le nombre moyen de fichiers par dossier est :

100/9 ≈ 11,11

Le plafond vaut :

⌈100/9⌉ = 12

Au moins un dossier contient donc au moins :

12 fichiers

Même avec la répartition la plus équilibrée possible, il est impossible que chaque dossier en contienne au plus 11.

Formulation par contradiction

Le principe généralisé peut être démontré par contradiction.

Supposons que chaque tiroir contienne au plus :

⌈N/k⌉ - 1

objets.

Le nombre total d'objets serait alors au plus :

k(
⌈N/k⌉ - 1
)

Cette quantité est strictement inférieure à **N**, ce qui contredit le fait que les N objets ont tous été placés dans les tiroirs.

Il existe donc nécessairement un tiroir contenant au moins :

⌈N/k⌉

objets.

Répartition la plus équilibrée

Lorsque N objets sont distribués aussi uniformément que possible dans k tiroirs, chaque tiroir contient soit :

⌊N/k⌋

objets, soit :

⌈N/k⌉

objets.

La notation :

⌊x⌋

désigne le plus grand entier inférieur ou égal à x.

Si :

N = qk + r

avec :

0 ≤ r < k

alors :

r tiroirs contiennent q+1 objets ;
les k-r autres tiroirs contiennent q objets.

Exemple de répartition équilibrée

Pour répartir 23 objets dans 5 tiroirs :

23 = 4 × 5 + 3

Trois tiroirs contiennent :

5 objets

et deux tiroirs contiennent :

4 objets

La répartition la plus équilibrée est donc :

5, 5, 5, 4, 4

Au moins un tiroir contient :

⌈23/5⌉ = 5

objets.

Forme duale

Une forme duale du principe affirme que si N objets sont répartis dans k tiroirs, alors au moins un tiroir contient au plus :

⌊N/k⌋

objets.

Cette version est utile lorsqu'on cherche une catégorie faiblement représentée.

Ainsi, dans une répartition de 100 éléments entre 9 catégories, au moins une catégorie contient au plus :

⌊100/9⌋ = 11

éléments.

Garantie d'au moins r objets dans un tiroir

Pour garantir qu'au moins un tiroir contienne au moins r objets, il faut placer :

k(r-1)+1

objets dans k tiroirs.

En effet, si chaque tiroir contient au plus :

r-1

objets, le nombre total maximal est :

k(r-1)

L'objet supplémentaire force donc un tiroir à atteindre au moins r objets.

Exemple de garantie

Combien de personnes faut-il pour garantir qu'au moins 4 personnes soient nées le même mois ?

Il existe :

mois.

Chaque mois pourrait contenir au plus 3 personnes sans atteindre 4.

Le nombre maximal de personnes dans cette situation est :

12 × 3 = 36

Il faut donc :

36 + 1 = 37

personnes pour garantir qu'au moins 4 d'entre elles sont nées durant le même mois.

Anniversaires et mois

Dans un groupe de 13 personnes, au moins deux personnes sont nées durant le même mois.

Les objets sont :

13 personnes

Les tiroirs sont :

12 mois

Comme :

13 > 12

au moins un mois correspond à la naissance d'au moins deux personnes.

Cette démonstration ne tient pas compte du jour ni de l'année de naissance.

Anniversaires et jours de l'année

Dans un groupe de 367 personnes, au moins deux personnes partagent nécessairement le même jour d'anniversaire, en considérant une année de 366 jours.

Les objets sont :

367 personnes

Les tiroirs sont :

366 dates possibles

Le principe garantit donc un anniversaire commun.

Avec seulement 366 personnes, cette répétition n'est pas garantie, car chaque personne pourrait avoir une date différente.

Reste d'une division

Lorsque plusieurs entiers sont divisés par un même entier positif m, les restes possibles sont :

0, 1, 2, ..., m-1

Il existe donc exactement :

classes de restes.

Si l'on choisit :

m+1

entiers, au moins deux possèdent le même reste modulo m.

Conséquence modulaire

Si deux entiers a et b possèdent le même reste modulo m, alors :

a ≡ b (mod m)

Donc :

m divise a-b

Le principe des tiroirs permet ainsi de démontrer l'existence de deux nombres dont la différence est divisible par un entier donné.

Exemple modulo 10

Parmi 11 entiers quelconques, au moins deux possèdent le même dernier chiffre.

Les tiroirs correspondent aux dix restes modulo 10 :

0, 1, 2, 3, 4, 5, 6, 7, 8, 9

Les deux nombres ayant le même dernier chiffre ont une différence divisible par 10.

Différence divisible par n

Parmi :

n+1

entiers quelconques, il existe toujours deux entiers dont la différence est divisible par n.

Chaque entier est classé selon son reste modulo n.

Il existe seulement :

restes possibles.

Deux nombres doivent donc appartenir à la même classe de congruence.

Sous-sommes divisibles

Le principe des tiroirs peut également être appliqué aux sommes partielles.

Considérons une suite de n entiers :

a₁, a₂, ..., a_n

Définissons les sommes partielles :

S₁ = a₁

S₂ = a₁+a₂

...

S_n = a₁+a₂+...+a_n

Si une somme partielle est divisible par n, le résultat est immédiat.

Sinon, les n sommes partielles possèdent des restes non nuls parmi seulement :

n-1

valeurs possibles.

Deux sommes partielles possèdent donc le même reste.

Conséquence sur les sous-séquences

Si :

S_i ≡ S_i (mod n)

avec :

i < j

alors :

S_i - S_i

est divisible par n.

Or :

S_i - S_i
=
a_i+1 + a_i+2 + ... + a_i

Il existe donc toujours une sous-séquence contiguë non vide dont la somme est divisible par n.

Exemple de sous-somme

Considérons les cinq entiers :

3, 1, 4, 2, 6

Les sommes partielles sont :

3
4
8
10
16

Modulo 5, les restes sont :

3
4
3
0
1

La somme partielle :

est divisible par 5.

La sous-séquence :

3 + 1 + 4 + 2

possède donc une somme divisible par 5.

Principe des tiroirs et parité

Chaque entier est soit :

pair

soit :

impair

Il existe donc deux tiroirs correspondant à la parité.

Parmi trois entiers quelconques, au moins deux possèdent la même parité.

Leur somme et leur différence sont alors paires.

Exemple avec la parité

Considérons trois entiers :

7, 12, 19

Deux d'entre eux sont impairs :

et :

Leur différence est :

19 - 7 = 12

Elle est paire.

Le principe garantit l'existence d'une telle paire sans qu'il soit nécessaire d'examiner toutes les combinaisons.

Points dans un carré

Le principe des tiroirs peut être appliqué à des régions géométriques.

Supposons qu'un carré soit divisé en quatre petits carrés égaux.

Si cinq points sont placés dans le grand carré, au moins deux points appartiennent au même petit carré.

Les points représentent les objets et les quatre petits carrés représentent les tiroirs.

Cette observation permet ensuite de déterminer une borne sur la distance séparant deux points.

Distance entre deux points

Considérons un carré de côté 2 divisé en quatre carrés de côté 1.

Si cinq points sont placés dans le carré initial, deux d'entre eux se trouvent dans le même petit carré.

La distance maximale entre deux points appartenant à un carré de côté 1 est sa diagonale :

√2

Il existe donc deux points distants d'au plus :

√2

Découpage géométrique

Dans les applications géométriques, le choix des tiroirs est essentiel.

Les tiroirs peuvent être :

des intervalles ;
des carrés ;
des cubes ;
des secteurs angulaires ;
des cellules d'une grille ;
des régions de l'espace.

Le découpage doit être choisi de manière que deux objets placés dans la même région satisfassent la propriété recherchée.

Nombres dans un intervalle

Considérons n+1 nombres réels appartenant à l'intervalle :

[0,1]

On divise l'intervalle en **n sous-intervalles** de longueur :

1/n

Au moins deux nombres se trouvent dans le même sous-intervalle.

Leur distance est donc au plus :

1/n

Cette propriété est une conséquence directe du principe des tiroirs.

Valeurs rapprochées

Plus généralement, si N valeurs sont réparties sur un intervalle de longueur L et que celui-ci est divisé en k segments égaux, au moins deux valeurs se trouvent dans le même segment lorsque :

N > k

Leur distance est alors inférieure ou égale à :

L/k

Cette méthode fournit une borne d'existence sur la proximité de deux valeurs.

Graphe et degrés des sommets

Dans un graphe simple comportant n sommets, le degré d'un sommet peut théoriquement prendre les valeurs :

0, 1, 2, ..., n-1

Cependant, un graphe simple ne peut pas contenir simultanément :

un sommet de degré 0 ;
un sommet de degré n-1.

Si un sommet est relié à tous les autres, aucun sommet ne peut être isolé.

Il existe donc au plus :

n-1

valeurs de degré effectivement disponibles.

Deux sommets de même degré

Comme le graphe contient :

n sommets

et au plus :

n-1

degrés possibles, au moins deux sommets possèdent le même degré.

Cette propriété est vraie pour tout graphe simple fini comportant au moins deux sommets.

Le principe des tiroirs fournit ici une preuve très courte d'un résultat de théorie des graphes.

Chaînes de caractères

Supposons qu'une chaîne utilise un alphabet de m symboles.

Toute chaîne de longueur :

m+1

contient nécessairement au moins un symbole répété.

Les caractères sont les objets et les symboles de l'alphabet sont les tiroirs.

Cette propriété est utilisée dans l'analyse de chaînes et la détection de répétitions.

Fréquence minimale d'un caractère

Dans une chaîne de longueur N utilisant un alphabet de m symboles, au moins un symbole apparaît au moins :

⌈N/m⌉

fois.

Par exemple, dans une chaîne de 100 caractères formée uniquement avec les 26 lettres de l'alphabet, au moins une lettre apparaît au moins :

⌈100/26⌉ = 4

fois.

Octets et valeurs possibles

Un octet peut prendre :

256

valeurs différentes, de :

à :

255

Dans une séquence contenant 257 octets, au moins deux octets possèdent la même valeur.

Dans une séquence contenant N octets, au moins une valeur apparaît :

⌈N/256⌉

fois.

Adresses IP

Une adresse IPv4 contient 32 bits.

Il existe donc au plus :

2³²

adresses binaires différentes.

Si un système devait attribuer plus de :

2³²

adresses IPv4 distinctes simultanément, au moins deux appareils recevraient la même adresse.

Dans la pratique, certaines plages sont réservées, ce qui réduit encore le nombre d'adresses utilisables.

Fonctions de hachage

Une fonction de hachage associe des données de taille variable à une valeur de taille fixe.

Par exemple, une fonction produisant un résultat de **b bits** possède au plus :

2^b

valeurs de sortie possibles.

Comme le nombre de messages possibles est généralement beaucoup plus grand, il existe nécessairement plusieurs messages produisant le même hachage.

Les collisions ne peuvent donc pas être éliminées complètement.

Exemple de hachage sur 8 bits

Une fonction de hachage de 8 bits produit :

256

valeurs possibles.

Si 257 entrées distinctes sont hachées, au moins deux produisent nécessairement la même valeur.

Le principe garantit la collision, même si la fonction répartit les valeurs aussi uniformément que possible.

Table de hachage

Dans une table de hachage possédant m cases, l'insertion de plus de m clefs distinctes provoque nécessairement au moins une collision.

Cependant, une collision peut apparaître bien avant que toutes les cases soient utilisées.

Le principe des tiroirs fournit uniquement une garantie à partir d'un certain seuil. Il ne donne pas la probabilité d'une collision avant ce seuil.

Collision certaine et collision probable

Il faut distinguer :

la collision certaine, démontrée par le principe des tiroirs ;
la collision probable, étudiée par les probabilités.

Dans un espace de m valeurs, une collision est certaine à partir de :

m+1

objets.

Cependant, en raison du paradoxe des anniversaires, une collision peut devenir probable avec un nombre d'objets beaucoup plus faible, approximativement de l'ordre de :

√m

Identifiants et clefs

Supposons qu'un système utilise des identifiants numériques compris entre :

et :

999

Il existe :

1000

identifiants possibles.

Si 1001 enregistrements doivent posséder chacun un identifiant de ce domaine, au moins deux enregistrements partageront le même identifiant.

Pour garantir l'unicité, le domaine des identifiants doit être au moins aussi grand que le nombre d'éléments à identifier.

Bases de données

Dans une base de données, une colonne utilisée comme clé primaire doit contenir des valeurs uniques.

Si son domaine possède seulement m valeurs possibles, elle ne peut identifier plus de m lignes sans répétition.

Le principe des tiroirs permet donc de vérifier si la capacité théorique d'un type de données est suffisante.

Par exemple, une clé sur un entier non signé de 8 bits ne peut identifier que 256 lignes distinctes.

Codes de longueur fixe

Si un code possède n positions et que chaque position peut contenir m symboles, le nombre de codes possibles est :

mⁿ

Si davantage de m^{n^{objets doivent recevoir un code, au moins deux objets partageront le même code.}}

Cette limite est indépendante de l'algorithme utilisé pour attribuer les codes.

Couleurs d'un écran

Supposons qu'une image utilise une palette de 256 couleurs.

Si l'image contient plus de 256 pixels, au moins deux pixels possèdent nécessairement la même couleur.

Dans une image contenant N pixels, au moins une couleur est utilisée :

⌈N/256⌉

fois.

Cette conclusion ne dépend pas de la disposition spatiale des pixels.

Fichiers répartis sur des serveurs

Si N fichiers sont répartis entre k serveurs, au moins un serveur contient au moins :

⌈N/k⌉

fichiers.

Ce résultat permet d'établir une charge minimale inévitable sur au moins une machine.

Il ne prouve toutefois pas que la répartition est équilibrée ni que les tailles des fichiers sont comparables.

Charge de travail

Supposons que 100 tâches soient attribuées à 8 processeurs.

Au moins un processeur reçoit :

⌈100/8⌉ = 13

tâches.

Cette conclusion porte uniquement sur le nombre de tâches.

Si les tâches possèdent des durées différentes, le processeur recevant le plus de tâches n'est pas nécessairement celui dont la charge totale est la plus élevée.

Répartition de requêtes

Si un serveur reçoit 10 000 requêtes réparties sur 60 secondes, au moins une seconde contient :

⌈10 000/60⌉ = 167

requêtes.

Le principe permet de déduire l'existence d'un pic minimal de requêtes par seconde.

Il ne précise pas la seconde concernée ni la distribution exacte dans le temps.

Mémoire et adresses

Si un programme tente de stocker davantage d'objets simultanés que de positions mémoire disponibles, au moins deux objets devraient partager la même position.

Sans mécanisme de remplacement, de pagination ou de stockage externe, cette situation est impossible.

Le principe des tiroirs exprime ici une limite fondamentale de capacité.

Registres et valeurs

Un registre de **b bits** peut représenter au plus :

2^b

configurations binaires.

Si un calcul doit distinguer davantage de 2^b états, certaines configurations devront partager la même représentation.

Cela peut conduire à :

un dépassement de capacité ;
une troncature ;
une collision ;
une représentation ambiguë.

Automates finis

Un automate fini possède un nombre limité d'états.

Si l'automate traite une entrée suffisamment longue, il doit nécessairement revisiter un état déjà rencontré.

Les positions successives dans le traitement sont les objets, et les états de l'automate sont les tiroirs.

Cette observation est à la base de plusieurs résultats sur les langages réguliers.

Répétition d'état dans un automate

Considérons un automate possédant m états.

Après avoir observé :

m+1

configurations successives, au moins deux configurations utilisent le même état.

La portion de traitement comprise entre ces deux occurrences forme une boucle potentiellement répétable.

Cette idée intervient dans le lemme de l'étoile, également appelé lemme de pompage.

Suites ultimement périodiques

Considérons un système déterministe possédant m états possibles.

À partir d'un état initial, il produit une suite :

s₀, s₁, s₂, ...

Après au plus :

m+1

termes, un état doit se répéter.

Comme l'évolution est déterministe, la suite devient ensuite périodique.

Générateurs pseudo-aléatoires

Un générateur pseudo-aléatoire utilisant un état interne de b bits possède au plus :

2^b

états différents.

Après un nombre suffisant d'itérations, un état doit se répéter.

À partir de cette répétition, la séquence produite recommence selon un cycle.

La période maximale ne peut donc pas dépasser le nombre d'états disponibles.

Détection de cycles

Le principe des tiroirs justifie l'existence d'un cycle dans toute suite déterministe évoluant dans un ensemble fini.

Des algorithmes comme :

l'algorithme du lièvre et de la tortue de Floyd ;
l'algorithme de Brent ;

permettent de détecter ce cycle sans stocker tous les états précédents.

Exemple d'évolution modulo m

Considérons la suite :

xⁿ⁺¹ =
f(x_n) mod m

Les valeurs possibles sont seulement :

0, 1, ..., m-1

Après au plus :

m+1

termes, une valeur se répète.

La suite devient alors ultimement périodique.

Sous-tableaux et sommes

Le principe des tiroirs est utile pour démontrer l'existence de sous-tableaux possédant certaines propriétés.

Par exemple, dans un tableau de n entiers, il existe toujours un sous-tableau contigu non vide dont la somme est divisible par n.

Cette propriété repose sur les restes modulo n des sommes préfixes.

Sommes préfixes

Pour un tableau :

a[1..n]

on définit :

préfixe[0] = 0

et :

préfixe[i]
=
a[1] + a[2] + ... + a[i]

Il existe :

n+1

sommes préfixes.

Leurs restes modulo n appartiennent à seulement :

classes possibles.

Démonstration avec préfixe nul

Comme il existe n+1 sommes préfixes et seulement n restes, deux sommes préfixes possèdent le même reste.

Supposons :

préfixe[i]
≡
préfixe[j]
(mod n)

avec :

i < j

Alors :

préfixe[j] - préfixe[i]

est divisible par n.

Cette différence correspond à la somme du sous-tableau :

a[i+1..j]

Algorithme de recherche d'un sous-tableau divisible

MODULE TrouverSousTableauDivisible(tableau)

   n ← longueur(tableau)
   premièrePosition[0..n-1] ← -1

   somme ← 0
   premièrePosition[0] ← 0

   POUR i ← 1 JUSQU'A n

      somme ← somme + tableau[i]
      reste ← ((somme MOD n)+n) MOD n
      SI premièrePosition[reste] ≠ -1 ALORS
         début ← premièrePosition[reste] + 1
         fin ← i
         RETOURNER (début,fin)
      SINON
         premièrePosition[reste] ← i
      FIN SI
   FIN POUR

L'algorithme mémorise la première position associée à chaque reste.

Complexité de l'algorithme

L'algorithme examine chaque élément une seule fois.

Sa complexité temporelle est :

O(n)

La mémoire supplémentaire utilisée est :

O(n)

pour conserver la première position de chaque reste possible.

Recherche de doublons

Pour détecter un doublon dans un tableau de n+1 entiers dont les valeurs appartiennent à :

{1,2,...,n}

le principe des tiroirs garantit qu'au moins une valeur apparaît plusieurs fois.

Cette garantie est indépendante de l'ordre des éléments.

Le problème consiste ensuite à localiser le doublon efficacement.

Exemple de doublon garanti

Considérons le tableau :

[1, 4, 3, 2, 5, 3]

Il contient 6 éléments, mais les valeurs possibles sont limitées à :

1, 2, 3, 4, 5

Comme :

6 > 5

un doublon est obligatoire.

Dans cet exemple, la valeur répétée est :

Détection avec une table de fréquences

MODULE TrouverDoublon(tableau,n)
   vu[1..n] ← FAUX
   POUR CHAQUE valeur DANS tableau
      SI vu[valeur] ALORS
         RETOURNER valeur
      FIN SI
      vu[valeur] ← VRAI
   FIN POUR
   RETOURNER AUCUN

Cet algorithme fonctionne en :

O(n)

temps et utilise :

O(n)

mémoire supplémentaire.

Détection sans mémoire proportionnelle

Lorsque le tableau contient n+1 valeurs appartenant à :

{1,...,n}

et qu'il peut être interprété comme une structure de pointeurs, l'algorithme de Floyd peut parfois trouver un doublon en :

O(n)

temps et :

O(1)

mémoire supplémentaire.

Le principe des tiroirs garantit l'existence du doublon, tandis que l'interprétation en cycle permet de le localiser.

Séquences et préfixes identiques

Si un ensemble contient davantage de chaînes que de préfixes possibles d'une longueur donnée, au moins deux chaînes possèdent le même préfixe.

Par exemple, il existe :

26³

préfixes possibles de trois lettres majuscules.

Parmi :

26³ + 1

noms utilisant uniquement ces lettres, au moins deux commencent par le même préfixe de trois lettres.

Suffixes et extensions de fichiers

Le même raisonnement s'applique aux suffixes.

Si un système classe des fichiers selon m extensions possibles, tout ensemble de plus de m fichiers contient au moins deux fichiers possédant la même extension.

Dans un ensemble de N fichiers, une extension apparaît au moins :

⌈N/m⌉

fois.

Résidus de hachage et partitionnement

Dans certains systèmes, une clef est affectée à une partition selon :

partition =
hachage(clef) mod k

Il existe :

partitions.

Pour N clefs, au moins une partition reçoit au moins :

⌈N/k⌉

clefs.

Cette borne ne garantit toutefois pas que la fonction de hachage répartit correctement les clefs.

Processus distribués

Supposons que N processus soient répartis entre k machines.

Au moins une machine exécute :

⌈N/k⌉

processus.

Cette borne peut servir à estimer la charge minimale maximale d'une répartition, également appelée charge du serveur le plus occupé.

Une stratégie optimale ne peut pas produire une charge maximale inférieure à cette valeur.

Ordonnancement

Dans un problème d'ordonnancement, si N tâches doivent être réparties entre k processeurs, la charge en nombre de tâches du processeur le plus occupé est au moins :

⌈N/k⌉

Cette borne inférieure peut être utilisée pour évaluer la qualité d'une solution.

Cependant, lorsque les durées des tâches diffèrent, une borne basée sur la somme des durées est généralement plus pertinente.

Borne inférieure sur la charge

Si les tâches possèdent des durées :

t₁, t₂, ..., t_n

et qu'elles sont réparties entre k processeurs, au moins un processeur possède une charge d'au moins :

⌈
(t₁+t₂+...+t_n)/k
⌉

lorsque les durées sont entières.

Cette version applique le même raisonnement à la charge totale plutôt qu'au simple nombre de tâches.

Compression sans perte

Une méthode de compression sans perte doit permettre de reconstituer exactement les données initiales.

Il est impossible que toutes les chaînes de longueur n soient compressées en chaînes strictement plus courtes.

En effet, le nombre total de chaînes plus courtes est inférieur au nombre de chaînes de longueur n.

Le principe des tiroirs implique que deux entrées distinctes recevraient la même représentation comprimée, rendant la décompression ambiguë.

Démonstration pour les chaînes binaires

Il existe :

2ⁿ

chaînes binaires de longueur n.

Le nombre total de chaînes binaires de longueur strictement inférieure à n est :

1 + 2 + 2² + ... + 2^n-1

soit :

2ⁿ - 1

Il n'existe donc pas assez de chaînes plus courtes pour représenter sans collision toutes les chaînes de longueur n.

Conséquence sur la compression

Un algorithme de compression sans perte peut raccourcir certaines données, mais il doit nécessairement :

laisser certaines données de même longueur ;
ou allonger certaines données.

Il ne peut pas compresser strictement toutes les entrées possibles.

Cette limite est une conséquence directe du principe des tiroirs.

Cryptographie

En cryptographie, le principe des tiroirs intervient dans l'étude :

des collisions de hachage ;
des tailles de clefs ;
des espaces de messages ;
des blocs de chiffrement ;
des codes d'authentification ;
des états internes ;
des générateurs pseudo-aléatoires.

Il établit plusieurs limites théoriques indépendantes de la puissance de calcul disponible.

Chiffrement déterministe

Un chiffrement réversible utilisant une clé fixe doit être injectif sur son espace de messages.

Si l'espace des textes chiffrés est plus petit que l'espace des messages possibles, deux messages distincts produiraient le même texte chiffré.

La décryption ne pourrait alors pas déterminer le message initial.

Le domaine de sortie doit donc avoir une capacité au moins égale à celle du domaine d'entrée.

Principe des tiroirs infini

Une version infinie du principe affirme que si une infinité d'objets est répartie dans un nombre fini de tiroirs, au moins un tiroir contient une infinité d'objets.

Par exemple, si tous les entiers naturels sont classés selon leur reste modulo 5, chaque classe contient une infinité d'entiers.

Au moins une classe doit nécessairement être infinie, et dans cet exemple elles le sont toutes.

Suite infinie sur un alphabet fini

Toute suite infinie formée à partir d'un alphabet fini contient au moins un symbole apparaissant une infinité de fois.

Si chaque symbole apparaissait seulement un nombre fini de fois, la suite entière serait finie.

Cette contradiction démontre le résultat.

Version pondérée

Le principe peut être généralisé à des charges ou à des poids.

Si des objets de poids total W sont répartis dans k tiroirs, au moins un tiroir reçoit un poids d'au moins :

W/k

Plus précisément, pour des poids entiers, un tiroir reçoit au moins :

⌈W/k⌉

unités de poids.

Cette version est utilisée dans les problèmes de répartition de ressources.

Moyenne et principe des tiroirs

Le principe généralisé peut être interprété à partir de la moyenne.

Si la moyenne du nombre d'objets par tiroir est :

N/k

alors au moins un tiroir contient un nombre d'objets supérieur ou égal à cette moyenne.

Comme le contenu est entier, il contient au moins :

⌈N/k⌉

objets.

De même, au moins un tiroir contient au plus :

⌊N/k⌋

objets.

Principe de la moyenne

Une formulation apparentée affirme que, parmi plusieurs valeurs, au moins une est supérieure ou égale à leur moyenne et au moins une est inférieure ou égale à leur moyenne.

Pour des valeurs :

x₁, x₂, ..., x_k

de moyenne :

μ =
(x₁+x₂+...+x_k)/k

il existe au moins un indice i tel que :

x_i ≥ μ

et au moins un indice j tel que :

x_i ≤ μ

Principe des tiroirs et invariants

Dans certaines preuves, les objets sont classés selon un invariant.

Un invariant peut être :

un reste modulo un entier ;
une parité ;
une couleur ;
une longueur ;
une valeur de hachage ;
un état ;
une catégorie ;
une position ;
une signature.

Si le nombre d'objets dépasse le nombre de valeurs possibles de l'invariant, deux objets partagent la même valeur.

Choix des tiroirs

La principale difficulté d'un problème utilisant le principe des tiroirs consiste souvent à déterminer les tiroirs appropriés.

Les tiroirs doivent être choisis de manière que :

chaque objet appartienne à un tiroir ;
le nombre de tiroirs soit connu ;
deux objets dans le même tiroir impliquent la propriété recherchée.

Un mauvais choix de catégories peut produire une conclusion vraie mais inutile.

Méthode de résolution

Une méthode générale consiste à suivre les étapes suivantes :

Identifier les objets.
Déterminer les catégories possibles.
Compter les objets.
Compter les catégories.
Comparer les deux quantités.
Appliquer la forme simple ou généralisée.
Traduire la collision obtenue

dans le contexte du problème.

Cette démarche permet d'éviter les erreurs d'interprétation.

Exemple de méthode

Problème :

Montrer que, parmi 17 entiers, deux possèdent le même reste modulo 16.

Les objets sont :

17 entiers

Les tiroirs sont :

16 restes possibles

Comme :

17 > 16

deux entiers possèdent le même reste.

Leur différence est donc divisible par 16.

Problème inverse

Le principe des tiroirs peut également être utilisé pour déterminer le nombre maximal d'objets pouvant être placés sans produire une certaine concentration.

Si l'on veut éviter qu'un tiroir contienne r objets, chaque tiroir peut en contenir au plus :

r-1

Avec k tiroirs, le nombre maximal d'objets est :

k(r-1)

L'objet suivant rend la propriété inévitable.

Exemple du problème inverse

Combien de personnes peut-on avoir sans garantir que 5 soient nées le même mois ?

Chaque mois peut contenir au plus :

4 personnes

Il existe 12 mois.

Le nombre maximal est donc :

12 × 4 = 48

Avec 49 personnes, au moins 5 partagent nécessairement un mois de naissance.

Nombre minimal requis

Le nombre minimal d'objets requis pour garantir qu'un tiroir contienne au moins r objets est :

k(r-1)+1

Cette formule doit être distinguée de :

⌈N/k⌉

La première détermine combien d'objets sont nécessaires pour atteindre une garantie donnée. La seconde détermine la concentration minimale garantie pour un nombre d'objets déjà connu.

Tableau récapitulatif

Situation	Conclusion
n+1 objets dans n tiroirs	Un tiroir contient au moins 2 objets
N objets dans k tiroirs	Un tiroir contient au moins ⌈N/k⌉ objets
N objets dans k tiroirs	Un tiroir contient au plus ⌊N/k⌋ objets
Garantir au moins r objets dans un tiroir	Il faut k(r-1)+1 objets
Plus de m entrées pour m sorties	Une collision existe
m+1 entiers modulo m	Deux possèdent le même reste
Suite déterministe dans m états	Un état se répète après au plus `m+1` observations
Plus de mⁿ objets avec des codes de longueur n sur m symboles	Deux objets partagent le même code

Algorithme de calcul de la borne minimale

MODULE ChargeMinimaleMaximale(nombreObjets,nombreTiroirs)
   SI nombreObjets < 0 ALORS
      ERREUR
   FIN SI

   SI nombreTiroirs ≤ 0 ALORS
      ERREUR
   FIN SI

   RETOURNER
      (
         nombreObjets
         +
         nombreTiroirs
         -
         1
      )
      DIV
      nombreTiroirs

Cette formule calcule :

⌈nombreObjets/nombreTiroirs⌉

sans utiliser de nombres réels.

Algorithme du nombre minimal d'objets

MODULE NombreMinimalPourGarantie(nombreTiroirs,quantitéGarantie)

   SI nombreTiroirs ≤ 0 ALORS
      ERREUR
   FIN SI

   SI quantitéGarantie ≤ 0 ALORS
      ERREUR
   FIN SI

   RETOURNER
      nombreTiroirs
      ×
      (quantitéGarantie-1)
      +
      1

Pour 12 mois et une garantie de 4 personnes :

12 × (4-1) + 1
=
37

Exemple en Java


public final class PrincipeDesTiroirs {
 
    private PrincipeDesTiroirs() {
    }
 
    public static long concentrationMinimale(
        long nombreObjets,
        long nombreTiroirs
    ) {
        if (nombreObjets < 0) {
            throw new IllegalArgumentException(
                "Le nombre d'objets ne peut pas être négatif."
            );
        }
 
        if (nombreTiroirs <= 0) {
            throw new IllegalArgumentException(
                "Le nombre de tiroirs doit être positif."
            );
        }
 
        if (nombreObjets == 0) {
            return 0;
        }
 
        return 1
            + (nombreObjets - 1)
            / nombreTiroirs;
    }
 
    public static long objetsPourGarantir(
        long nombreTiroirs,
        long quantiteGarantie
    ) {
        if (nombreTiroirs <= 0) {
            throw new IllegalArgumentException(
                "Le nombre de tiroirs doit être positif."
            );
        }
 
        if (quantiteGarantie <= 0) {
            throw new IllegalArgumentException(
                "La quantité garantie doit être positive."
            );
        }
 
        long produit = Math.multiplyExact(
            nombreTiroirs,
            quantiteGarantie - 1
        );
 
        return Math.addExact(produit, 1);
    }
 
    public static void main(String[] args) {
        System.out.println(
            "Concentration minimale : "
            + concentrationMinimale(100, 9)
        );
 
        System.out.println(
            "Personnes requises : "
            + objetsPourGarantir(12, 4)
        );
    }
}

Le programme affiche :

Concentration minimale : 12 Personnes requises : 37

Vérification d'une collision en Java


import java.util.HashMap;
import java.util.Map;
import java.util.Optional;
 
public final class CollisionSample {
 
    private CollisionSample() {
    }
 
    public static Optional<int[]> trouverCollisionModulo(
        int[] valeurs,
        int module
    ) {
        if (module <= 0) {
            throw new IllegalArgumentException(
                "Le module doit être positif."
            );
        }
 
        Map<Integer, Integer> premierePosition =
            new HashMap<>();
 
        for (int i = 0; i < valeurs.length; i++) {
            int reste =
                Math.floorMod(valeurs[i], module);
 
            Integer autrePosition =
                premierePosition.putIfAbsent(
                    reste,
                    i
                );
 
            if (autrePosition != null) {
                return Optional.of(
                    new int[] {
                        autrePosition,
                        i
                    }
                );
            }
        }
 
        return Optional.empty();
    }
 
    public static void main(String[] args) {
        int[] valeurs = {
            8, 19, 27, 42, 58, 71
        };
 
        trouverCollisionModulo(valeurs, 5)
            .ifPresent(indices ->
                System.out.println(
                    "Collision entre les positions "
                    + indices[0]
                    + " et "
                    + indices[1]
                )
            );
    }
}

La méthode recherche deux valeurs possédant le même reste modulo le module fourni.

Complexité de la recherche de collision

Avec une table de hachage ou un tableau de positions, la recherche d'une collision peut être réalisée en :

O(N)

temps.

La mémoire utilisée dépend du nombre de tiroirs :

O(k)

Le principe des tiroirs garantit l'existence d'une collision lorsque :

N > k

mais l'algorithme reste nécessaire pour identifier les objets concernés.

Preuve d'existence et construction

Le principe des tiroirs est principalement un outil de preuve d'existence.

Il démontre qu'un objet, une paire ou une collision existe, mais il ne fournit pas toujours une méthode directe pour la trouver.

Il faut distinguer :

la preuve non constructive d'existence ;
l'algorithme permettant de localiser l'exemple garanti.

Dans de nombreux cas informatiques, une table de fréquences, un tri ou une structure de hachage permet de rendre la preuve constructive.

Applications

Le principe des tiroirs est utilisé dans de nombreux domaines :

combinatoire ;
théorie des nombres ;
arithmétique modulaire ;
théorie des graphes ;
géométrie discrète ;
analyse des algorithmes ;
recherche de doublons ;
détection de cycles ;
automates finis ;
compression de données ;
fonctions de hachage ;
cryptographie ;
bases de données ;
systèmes distribués ;
équilibrage de charge ;
ordonnancement ;
réseaux ;
traitement des chaînes ;
allocation de ressources ;
preuves d'existence.

Avantages

Le principe des tiroirs présente plusieurs avantages :

il est simple à énoncer et à appliquer ;
il permet de démontrer rapidement l'existence d'une répétition ;
il fournit des bornes minimales garanties ;
il s'applique à des objets très variés ;
il ne nécessite pas de connaître la répartition exacte ;
il permet d'identifier des limites fondamentales ;
il explique l'inévitabilité des collisions de hachage ;
il aide à analyser les capacités des types et des identifiants ;
il intervient dans des preuves algorithmiques et combinatoires ;
il peut être combiné avec l'arithmétique modulaire et les sommes préfixes.

Limites et précautions

Plusieurs précautions doivent être prises :

le principe garantit une existence, mais pas l'identité des objets concernés ;
il ne fournit pas la distribution complète ;
il ne donne pas la probabilité d'une collision avant le seuil certain ;
le choix des tiroirs doit être pertinent ;
les catégories doivent couvrir tous les objets ;
un même objet doit être classé de manière cohérente ;
la borne obtenue peut être faible par rapport à la réalité ;
le nombre d'objets et le nombre de tiroirs doivent être clairement distingués ;
la formule avec le plafond doit être utilisée pour la forme généralisée ;
le principe ne tient pas compte du poids ou de la taille des objets, sauf dans une version pondérée ;
une preuve d'existence ne constitue pas automatiquement un algorithme efficace.

Remarque

Le principe des tiroirs repose sur une idée très simple : lorsqu'un nombre insuffisant de catégories doit accueillir un nombre plus élevé d'objets, une répétition devient inévitable. Cette observation permet de prouver l'existence de doublons, de collisions, de valeurs rapprochées, de sous-sommes divisibles, d'états répétés et de charges minimales.

En programmation, ce principe explique pourquoi les fonctions de hachage possèdent nécessairement des collisions, pourquoi un automate fini finit par revisiter un état, pourquoi une compression sans perte ne peut raccourcir toutes les données et pourquoi un domaine d'identifiants doit être suffisamment grand. Il prépare naturellement à l'étude des relations de récurrence, des probabilités discrètes, de la théorie des graphes, des algorithmes de hachage et des méthodes de détection de cycles.

Dernière mise à jour : Jeudi, le 16 juillet 2026