Imaginez dix pigeons volant dans votre pigeonhole fait maison, mais vous n'en avez fabriqué que 9. Où va le dernier pigeon ? Quelle est l’histoire derrière le Principe du pigeonhole ?

Étant donné que la population de Londres dépasse le nombre maximal de cheveux sur la tête d’un être humain, le principe du pigeonhole exige qu’au moins deux personnes à Londres aient le même nombre de cheveux sur la tête. Ce principe mathématique existe depuis 1624.

Le principe du pigeonhole

Le principe du pigeonhole est l’un des concepts les plus fondamentaux mais précieux des mathématiques. Il a été enregistré dès 1624. Il est communément connu sous le nom de principe de la boîte de Dirichlet ou principe du tiroir de Dirichlet. (Source : Jeff 560)

Dans son explication la plus simple, le principe stipule que si dix pigeons se rassemblent dans neuf pigeonholes, au moins l’un des pigeonholes contiendra plus d’un pigeon. 

Dans le théorème : si X est le nombre moyen de pigeons par trou, où X n’est pas un entier, alors au moins un pigeonhole contient le nombre maximal autorisé de pigeons, et les pigeonholes restants auront très probablement le nombre minimal de pigeons. (Source : Geeks For Geeks)

Pour expliquer davantage, si n+1 objets sont placés dans n contenants, alors au moins un contenant contiendra deux objets ou plus. Le principe du pigeonhole est utilisé pour montrer que les résultats doivent être valides parce qu’ils sont « trop grands pour échouer ». Cela signifie qu’au moins deux objets auront ou partageront une propriété pour tout nombre significatif d’objets avec une limite ou un nombre spécifique de propriétés. Et les applications de ce principe sont intéressantes, surprenantes et stimulantes. (source : Stanford)

Quelques exemples du principe

Le premier exemple, comme indiqué ci‑dessus, illustre le principe du pigeonhole ainsi : la population de Londres, en excluant les personnes chauves, est d’environ 7,5 millions. Le nombre maximal de cheveux chez une personne moyenne est d’environ 150 000. Le principe indiquerait qu’environ 50 personnes auraient le même nombre de cheveux. (Source : Maths Careers)

Ensuite, supposons que deux personnes ou plus lisent cet article et qu’elles aient le même anniversaire. Le principe indique qu’il y a 366 anniversaires possibles lors d’une année bissextile. Cet article compte plus de 367 lecteurs. Ainsi, deux de vous partagent le même anniversaire.

Un autre exemple serait celui d'un jeu de cartes à jouer ordinaire. Si une personne choisit cinq cartes parmi les 52 cartes d'un jeu de cartes standard, au moins deux de ces cinq cartes auront la même couleur. En effet, il y a quatre couleurs dans un jeu de cartes ordinaire – trèfles, piques, cœurs et carreaux. Chacune des cinq cartes doit appartenir à l'une des quatre couleurs. Il en découle donc que deux de ces cartes partagent la même couleur. (Source: Mind Your Decisions) 

Y a-t-il une application pratique de ce principe ?

Le principe des tiroirs aide à démontrer la compression sans perte utilisée en sciences des données. La compression de données est la théorie selon laquelle les données du monde réel peuvent être compressées en omettant simplement les redondances.

C’est une théorie cruciale utilisée aujourd’hui sous forme de transfert de données, que l’information soit transmise via le réseau, les DVD, les clés USB ou les courriels, pour n’en citer que quelques exemples.

L’idée de la compression sans perte est de remplacer chaque chaîne de bits d’information par une chaîne de bits plus courte. Cependant, une fois la chaîne de bits plus courte décompressée, elle révèle toujours l’information intacte de la chaîne de bits originale. (Source : Stanford)

Le principe des tiroirs prouve la compression sans perte dans la mesure où il n’est possible de compresser que des données très répétitives, où deux « pigeons », morceaux de données, occupent un même « tiroir » ou emplacement dans la chaîne de bits. (Source : Stanford)