Le principe des tiroirs : Cours et exercices

Qu’est-ce que le principe des tiroirs ? Cet article vous donnera la réponse !
Principe des tiroirs

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 :

Divisibilité et ensembles

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 !

Lemme des tiroirs

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.

Théorème de Liouville suite

Vous pouvez trouver la correction en vidéo à ce lien

Total
0
Partages

Laisser un commentaire

Articles similaires