LE PRINCIPE DES TIROIRS

[Texte en cours pour une chronique de jeux mathématiques à paraître]

Imaginez que vous vouliez ranger des objets dans des tiroirs, en plaçant un seul objet par tiroir. Vous avez 9 objets et neuf tiroirs : tout va bien. Mais si vous avez 10 objets à placer et toujours neuf tiroirs, vous n’y arriverez pas puisqu’un tiroir contiendra deux objets.

Le mathématicien allemand Peter-Gustav Lejeune-Dirichlet (1805-1859) a fait cette observation en 1834 et aussitôt remarqué tout ce qu’on pouvait tirer ce qu’on appelle désormais le principe de Dirichlet — en anglais le pigeon hole principle.

Pour vous convaincre de la puissance de ce principe, considérez la question suivante : y a-t-il à Montréal deux personnes qui ont exactement le même nombre de cheveux?
La question peut à première vue sembler impossible à résoudre sans de longs et fastidieux comptages. Mais grâce aux tiroirs de Dirichlet, on peut prouver que la réponse est nécessairement oui.

Commençons par estimer le nombre maximal de cheveux qu’une personne peut avoir. Pour nous aider — on pourrait compter, mais ce serait long! — rappelons qu’on a, selon la région du cuir chevelu, entre 200 et 300 cheveux par cm². Partant de là et de la surface de cuir chevelu que nous avons en moyenne, on pourra estimer entre 120 000 à 150 000 le nombre de cheveux qui composent une chevelure. Mais soyons excessifs et prudents et doublons ce dernier nombre : disons donc qu’une personne peut avoir entre 1 et 300 000 cheveux — nous mettons de côté les chauves.

Disons qu’on estime, et c’est un nombre ridiculement minimal, qu’il y a un million de personnes à Montréal. Avec ces seules données, grâce au principe des tiroirs, on peut être certain que deux personnes habitant Montréal ont exactement le même nombre de cheveux.

Voici pourquoi.

Ces personnes sont les objets à placer dans les tiroirs; les tiroirs sont les diverses possibilités de nombres de cheveux. Il y a donc 300 000 tiroirs (de 1 à 300 000 cheveux possibles) et un million d’objets (les personnes qui habitent Montréal). La conclusion s’impose d’elle-même.

Voici comment.

Considérons une première personne. Elle a, disons, 3 cheveux et on la range donc dans le tiroir correspondant. Une deuxième personne a 124 566 cheveux : elle va donc dans ce tiroir, différent du précédent. On place de la sorte les 300 000 premières personnes — qui, manque de chance, ont toutes un nombre différent de cheveux — dans les 300 000 tiroirs qui, dès lors, sont tous occupés. MAIS il reste des personnes à placer (il en reste même 700 000!) : de sorte que, nécessairement, la personne suivante va être rangée dans un tiroir déjà occupé. Elle aura donc le même nombre de cheveux qu’une autre personne. Il y a donc, nécessairement, deux — et même bien plus que deux — personnes qui ont le même nombre de cheveux à Montréal.

Si on y pense, c’est un résultat vraiment spectaculaire, obtenu par le seul raisonnement. Il donne une idée de la puissance du principe des tiroirs. On peut ainsi être d’avance certain que, dans des conditions que vous formulerez aisément, nous arriverons au travail à la même minute plus d’une fois durant notre vie; que plusieurs sapins dans les Laurentides ont exactement le même nombre d’épines; que, toujours sous certaines conditions usuelles (relatives au nombre de candidats et au total des points qu’on peut obtenir), plusieurs élèves auront les même résultat à un examen donné.
Quand on connaît le principe des tiroirs, on le voit à l’œuvre partout!
[à suivre...]