vendredi, décembre 05, 2008

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...]

7 commentaires:

Anonyme a dit…

Pas d'accord pour les cheveux !
Prenons le nombre 222,222; il se peut fort bien que personne, à Montréal, ne possède exactement 222,222 cheveux sur sa tête.
Qu'il y en ait 32 qui en ont 250,000, pas de problème, mais que toutes les quantités de 1 à 300,000 soient utilisées, si on peut dire, ce n'est pas obligatoire, théorie des tiroirs ou pas...

Garamond

Anonyme a dit…

Cependant, qu'il y ait deux personnes ayant 223,345 cheveux à Montréal, oui, il n'y a rien de spécial là-dedans...
Quand le nombre de sujets est supérieur au nom de numéros, on a des duplicatas...
Élémentaire, mon cher Watson...

Garamond

Normand Baillargeon a dit…

J'avoue avoir du mal à vous suivre...

N.

José a dit…

Bonjour,

A ce propos, je vous conseille la lecture du texte suivant:

Edsger W. Dijkstra, "The undeserved status of the pigeon-hole principle",1986.

On le trouve facilement sur le internet.

W. Dijkstra propose dans ce texte une définition plus rigoureuse du principe des tiroirs. La voici:

"for a nonempty, finite bag of real numbers, the maximum is at least the average (and the minimum is at most the average)".

Cordialement,

José

Normand Baillargeon a dit…

Merci de la référence.

Normand B.

Anonyme a dit…

Autre anonyme.
Bonjour Normand et Garamond,

Je pense que Garamond exprime son désaccord sur la conclusion qu'il a voulu comprendre et non la conclusion de la démonstration. Petit indice: A aucun moment dans la démonstration il est question d'affirmer que les tiroirs(différents selon les nbres de cheveux) sont tous remplis comme la démonstration de . Mais peu importe car: Oui il est possible que 1 ou 2 ou ... ou 299 tiroirs seulement soit remplis et non 300.
Et dans ces cas comme vous le dites "(Quand) le nombre de sujets est supérieur au nom de numéros(je suppose de tiroir 1 etc, remplis)" et donc on peut seulement conclure qu'au moins un tiroirs contient "des duplicatas..."!

"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?"
"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."

Anonyme a dit…

Oups mes excuses il est dit:

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 n'est pas dit: "obligation" que toutes les quantités de 1 à 300,000 soient utilisées ce n'est qu'un choix d'énoncé et encore moins une (des) conclusion de la démonstration.