Abonnez-vous

Élémentaire et puissant : le principe des tiroirs


Philippe Fondanaiche

Si votre commode comporte deux tiroirs et que vous y rangez trois vêtements, nécessairement deux habits (voire les trois, mais au moins deux) se trouveront dans le même compartiment. Cette remarque d'apparence triviale est en fait à la base d'un puissant outil de raisonnement !


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 ... Lire la suite gratuitement


références

Le site www.diophante.fr donne accès à une bibliothèque de plus de deux mille problèmes mathématiques, avec leurs énoncés et leurs solutions (souvent plusieurs par problème, les lecteurs ayant toute latitude pour envoyer leurs propres réponses), classés par thèmes et par niveau de difficulté. Chaque mois sont mis en ligne six nouveaux problèmes, dont les solutions sont données au début du mois suivant.