Comment choisir « la » bonne méthode de résolution du problème qui vous occupe ? C’est qu’il y a l’embarras du choix : discours de Descartes, raisonnement par l’absurde, démonstration par récurrence, recherche d’invariants, principe de l’extremum, descente infinie de Fermat, preuve par les coloriages… En fait, tout dépend du contexte et du problème qui vous préoccupe. Une catégorie de problèmes combinatoires, dont quelques exemples d’application sont développés ici (et vous êtes invités à réfléchir par vous-mêmes aux énoncés avant de vous précipiter sur leur solution !), font appel au fameux et puissant principe des tiroirs. En anglais, il est appelé pigeonhole principle et fait référence à la répartition imagée des pigeons dans les lucarnes d’un pigeonnier.
La première version en a été donnée, de façon élémentaire, par le mathématicien allemand Johann Peter Gustav Lejeune Dirichlet en 1834 sous le nom de Schubfachprinzip, littéralement « principe du tiroir » :
si l’on range n + 1 objets dans les n tiroirs d’une commode,
alors au moins un tiroir contient au moins deux objets.
On peut immédiatement le généraliser : si l’on range kn + 1 objets dans n tiroirs, k étant un entier naturel non nul, alors au moins un tiroir contiendra au moins k + 1 objets. Ou encore : si l’on range p objets ...
Lire la suite gratuitement