Principe des tiroirs

En mathématiques, le principe des tiroirs de Dirichlet, affirme que, sans perte de généralité, si chaussettes sont rangées dans tiroirs, alors au moins un tiroir contient plus d’une chaussette. Mathématiquement, le principe peut s'énoncer ainsi : Si et sont deux ensembles finis tels que , alors il n'existe pas d'application injective de dans . La première version du principe fut énoncée par Dirichlet en 1834 sous le nom de Schubfachprinzip (« principe du tiroir ») ; sa première utilisation lui est cependant antérieure d'au moins deux siècles. Dans certains pays comme la Russie, ce principe s'appelle le principe de Dirichlet (à ne pas confondre avec le principe du maximum pour les fonctions harmoniques portant le même nom). Ce principe est aussi appelé principe des tiroirs de Dirichlet-Schläfli. En anglais, ce principe est appelé pigeonhole principle. Il fait référence à la répartition des pigeons dans les cases (ou « boulins ») d'un pigeonnier. Une version généralisée de ce principe déclare que, si n objets discrets occupent m récipients, alors au moins un récipient doit contenir au moins objets où est la fonction partie entière par excès, qui associe à un réel x le plus petit entier supérieur ou égal à x ; ce nombre peut s'écrire avec la fonction partie entière : . Le principe des tiroirs est un exemple d'argument de dénombrement. Ce principe peut être appliqué à de nombreux problèmes sérieux, y compris ceux qui impliquent des ensembles infinis qui ne peuvent pas être mis en correspondance univoque. En approximation diophantienne, l'application quantitative du principe montre l'existence de solutions entières d'un système d'équations linéaires, résultat qui porte le nom de lemme de Siegel. Des généralisations aux ensembles infinis existent ; ainsi, une partition d'un ensemble de cardinal α en β sous-ensembles, avec β