Nous allons décrire dans cet article ce principe mathématique qui peut sembler évident mais qui se révèle bien pratique : le principe des tiroirs
Définition du principe des tiroirs
Le principe des tiroirs, appelé aussi principe de Dirichlet est un principe qui dit que si on a n chaussettes et p tiroirs avec n > p alors il existe un tiroir qui contient strictement plus d’une chaussette.
Mathématiquement cela s’écrit : Si E et F sont deux ensembles finis tels que Card(E) > Card(f) et si f: E \to F alors il existe un élément de F qui admet au moins deux antécédents pour f.
Si on veut le dire autrement : il n’existe pas d’application injective de E dans F.
Le principe des tiroirs est souvent utilisé en dénombrement pour démontrer certaines propriétés.
Généralisation du principe des tiroirs
Si n chaussettes sont réparties dans q tiroirs alors l’un de ces tiroirs doit avoir au moins \lceil \dfrac{n}{q} \rceil objets. \lceil x \rceil désigne la partie supérieure c’est à dire l’entier arrondi par excès.
Par exemple, si on a 31 chaussettes et 10 tiroirs, alors l’un des tiroirs aura au moins 4 chaussettes.
Quelques exercices utilisant le principe des tiroirs
Exercice 1
Cet exercice corrigé utilise le lemme des tiroirs :
Voici sa correction en vidéo :
Exercice 2
Cet exercice est un peu plus simple, je vous laisse chercher comment le démontrer. N’hésitez pas à proposer une correction dans les commentaires !
Exercice 3
Cet exercice vous donnera un peu plus de fil à retordre, mais il faudra utiliser le principe des tiroirs et construire une suite de couples vérifiant la propriété recherchée.
