Section 5.3 Principe des tiroirs de Dirichlet
Sous-section 5.3.1 Introduction
Le principe des tiroirs de Dirichlet (ou le principe des nids de pigeons), est un principe très simple, qui peut être utilisé afin de démontrer des résultats complexes, si on l’utilise de façon intelligente.
Exemple 5.3.2. Un petit échauffement.
Soit une classe formée de \(27\) étudiants ou plus, alors il existe au moins deux étudiants tels que leur prénom commence par la même lettre.Solution.
\(26\)
Tel que mentionné plus haut (et comme on peut le constater avec l’exemple précédent), le principe est assez simple et semble même anodin. Cependant, avec un peu d’imagination, on peut s’en servir pour résoudre des problèmes complexes. La partie importante ici est avec un peu d’imagination.
Sous-section 5.3.2 Exemples
Exemple 5.3.3.
Montrer que pour n’importe quel \(n\in \N^\ast\text{,}\) il existe un multiple de \(n\) qui est écrit uniquement avec des \(0\) et des \(1\) dans sa représentation en base dix.Solution.
On considère les \(n+1\) nombres suivants: \(1,\ 11,\ 111\,\dots,\ 11\dots 1\text{,}\) où le dernier nombre est l’entier formé de \(n+1\) chiffres \(1\) dans sa représentation en base dix. On numérote \(n\) boites de \(0\) à \(n-1\text{.}\) Ensuite on place chacun des \(n+1\) nombres précédents dans la boite étiquetée par son reste lors de la division par \(n\text{.}\)
Puisqu’il y a \(n+1\) nombres et \(n\) boites (restes), par le principe des tiroirs de Dirichlet, il existe deux de ces entiers, disons \(k_1\gt k_2\text{,}\) tels que
\begin{equation*}
k_1\equiv k_2 \mod n\text{.}
\end{equation*}
Par la définition de la congruence modulo \(n\text{,}\) on a
\begin{equation*}
n\mid (k_1-k_2)\text{.}
\end{equation*}
Ainsi, \(k_1-k_2\) est un multiple de \(n\) et il s’écrit avec uniquement des \(1\) et des \(0\text{.}\)
Exemple 5.3.4.
Durant un mois de \(30\) jours, une équipe de baseball joue au moins une partie par jour, mais au plus \(45\) parties durant le mois. Montrer qu’il existe un nombre de jours consécutifs durant lesquels l’équipe doit jouer exactement \(14\) parties.Solution.
On note \(a_i\) le nombre de parties jouées avant et durant le jour \(i,\) pour \(i=1,\,2,\,\dots,30.\) Puisque l’équipe joue au moins une partie par jour et moins de \(45\) parties dans le mois, on a \(1\leq a_1\lt a_2\lt\cdots \lt a_n \lt \cdots \lt a_{30} \leq 45.\) En particulier, on a que \(a_i\neq a_j\) si \(i\neq j\text{.}\)
On considère également les \(30\) entiers \(a_i +14\) pour \(i=1,\,2,\,\dots,30.\) On aura alors \(15\leq a_1+14\lt a_2+14\lt \cdots \lt a_n+14\lt \cdots \lt a_{30}+14 \leq 59.\) Encore une fois, on a \(a_i+14\neq a_j + 14 \) si \(i\neq j\text{.}\)
On a donc les \(60\) entiers \(a_1,a_2\dots,a_{30},a_1+14,a_2+14,\dots,a_{30}+14\) compris entre \(1\) et \(59.\) Il y aura donc au moins deux de ces entiers qui sont égaux. Par ce qui précède, on doit avoir \(a_j=a_i+14.\) Ainsi, le nombre de parties jouées entre le jour \(i\) et le jour \(j\) est \(14\text{.}\)
Exemple 5.3.5.
Montrer que si on prend n’importe quel ensemble \(A\) formé de \(n+1\) nombres entiers strictement positifs et inférieurs ou égaux à \(2n\text{,}\) alors au moins un des éléments de \(A\) divise un autre élément de \(A\text{.}\) Symboliquement, si \(A\subset \{1,2,\dots,2n\}\) avec \(|A|=n+1\text{,}\) alors il existe \(a_1\in\ A\) et \(a_2\in\ A\) tels que \(a_1\neq a_2\) et \(a_1\mid a_2\text{.}\)Solution.
Tout entier \(n\in\,A\) peut s’écrire comme \(n=2^kq,\) où \(k\) est un entier naturel et \(q\in\,\{1,2,\dots,2n\}\) est impair. Supposons que la représentation en base deux de \(q\) est \(d={d_md_{m-1}\cdots d_1d_0}\text{.}\) Ainsi, la représentation en base deux de \(n\) est \(\)
\begin{equation*}
n=\overbrace{d_md_{m-1}\cdots d_1d_0}^{\text{représentation binaire de } q}\underbrace{00\cdots0_2}_{\text{ avec } k \text{ }0}\text{.}
\end{equation*}
Puisqu’il y a \(n+1\) éléments de \(A\) et \(n\) nombres impairs de \(\{1,2,\dots,2n\},\) il existe \(a_1,\,a_2\in\,A\) tels que \(a_1=2^{k_1}q\) et \(a_2=2^{k_2}q.\) En supposant \(a_1\lt a_2,\) on a alors \(2^{k_2-k_1}a_1=2^{k_2-k_1}2^{k_1}q=2^{k_2}q=a_2.\) Ainsi, on a \(a_1\mid a_2\text{.}\)
Questions de compréhension de la lecture 5.3.3 Questions de compréhension de la lecture
Ces questions sont à faire avant de venir en classe et à remettre au début du cours.
1.
Utiliser le principe des tiroirs de Dirichlet pour montrer les propositions suivantes.
Lorsqu’on utilise la méthode des tiroirs de Dirichlet, il faut indiquer quels sont les objets, quelles sont les boites et comment on place les objets dans ces boites.
(a)
On forme un groupe de dix personnes pour travailler sur un projet informatique. Montrer qu’il existe au moins deux personnes qui sont nées la même journée de la semaine.
(b)
On écrit aléatoirement \(1001\) nombres entiers positifs. Montrer qu’il existe au moins deux nombres ayant les mêmes trois derniers chiffres.
(c)
On choisit aléatoirement sept entiers dans l’ensemble \(\{1,2,3,4,5,6,7,8,9,10\}.\) Montrer qu’il doit y avoir une paire telle que sa somme est \(11\text{.}\)
Indice.
(d)
Soit un sous-ensemble \(X\subseteq \{1,2,3,\dots,9\}\text{,}\) on définit la fonction \(f(X)\) par \(f(X)=0\) si \(X=\emptyset\text{,}\) et comme la somme des éléments de \(X\) sinon.
On choisit aléatoirement \(26\) sous-ensembles de \(\{1,2,3,\dots,9\}\) contenant trois éléments ou moins (c’est-à-dire, des sous-ensembles \(X\) tels que \(|X|\leq 3\text{.}\) Montrer qu’il existe au moins deux sous-ensembles \(A\) et \(B\) tels que \(f(A)=f(B)\text{.}\)
2.
Noter toute question qui demeure suite à la lecture de la section et la résolution des exercices ci-dessus ou toute précision/clarification à apporter. Note: cette question est facultative.
Exercices 5.3.4 Exercices
À faire en classe
Ces exercices sont faits pour travailler en classe. Ils servent à approfondir les notions de la section et à atteindre les objectifs d’apprentissage plus avancés.
1.
Montrer que si un élève assiste à six cours durant la semaine, chacun des cours se déroulant la même journée chaque semaine, alors il y a un jour durant lequel l’élève assiste à au moins deux cours.2.
Une urne contient \(10\) billes rouges et \(10\) billes bleues. Une personne pige au hasard des billes sans les remettre dans l’urne.
(a)
Combien de billes doit-elle piger avant d’être certaine d’avoir deux billes de la même couleur?
(b)
Combien de billes doit-elle piger avant d’être certaine d’avoir deux billes bleues?
Réponse.
\(12\)
3.
Montrer que si on choisit aléatoirement cinq nombres entiers, alors il y en aura au moins deux ayant le même reste lorsque divisé par \(4\text{.}\)
Solution.
On place les \(5\) objets (les nombres entiers) dans les \(4\) boîtes représentant les classes d’équivalence modulo \(4\text{.}\) On place chaque entier dans sa propre classe d’équivalence. Puisqu’il y a plus d’objets que de boîtes, il ya aura au moins deux objets dans la même boîte.
Ainsi, il y aura deux entiers dans la même classe d’équivalence modulo \(4,\) c’est-à-dire que ces deux entiers auront le même reste lorsque divisé par \(4\text{.}\)
4.
Soit \(d\in\,\N^\ast\text{.}\) Montrer que si on choisit aléatoirement \(d+1\) nombres entiers, alors il y en aura au moins deux ayant le même reste lorsque divisé par \(d\text{.}\)
5.
On choisit aléatoirement \(n+1\) nombres parmi les éléments de \(\{1,2,\dots,2n-1\}\text{.}\) Montrer qu’il existe au moins deux nombres qui somment à \(2n\text{.}\)
Solution.
Puisqu’il ya plus d’objets que de boîtes, il y aura au moins deux objets dans la même boîte. Tout d’abord on remarque qu’il y a un seul élément dans l’ensemble \(\{n,n\}=\{n\}\text{.}\) Ainsi, la boîte contenant deux objets ne peut pas être celle-ci. Finalement, si une boîte contient deux objets, par la définition des boîtes, on a que la somme de ces deux entiers donne \(2n\text{.}\)
6.
Combien d’entiers doit-on choisir aléatoirement dans l’ensemble \(\{1,2,3,4,5,6\}\) afin de garantir qu’au moins une paire aura une somme de \(7\text{?}\)
7.
Soit \(f\) est une fonction \(f:A\to B\text{.}\) En utilisant le principe des tiroirs de Dirichlet, montrer que si \(|B|\lt |A|\lt \infty\text{,}\) alors la fonction n’est pas injective.
Solution.
-
Objets: Les éléments de \(A\text{.}\)
-
Boîtes: Les éléments de \(B\text{.}\)
Puisqu’il ya plus d’objets que de boîtes, il y aura au moins deux objets dans la même boîte. Ainsi, il existe \(a_1\neq a_2\in\,A\) tels que \(f(a_1)=f(a_2).\) La fonction n’est donc pas injective.
8.
Soit \((a_i,b_i),\) des paires d’entiers ordonnés (c’est-à-dire \(a_i,\,b_i\in\,\Z\)) pour \(i=1,2,3,\dots,17.\) Montrer qu’il existe, parmi ces \(17\) paires d’entiers, deux paires d’entiers \((a,b)\) et \((c,d)\) telles que \(a\equiv c\mod 4 \) et \(b \equiv d \mod 4\)Solution.
-
Objets: Les \(17\) paires \((a_i,b_i)\)
-
Boîtes: Les \(16\) paires de classes d’équivalence \((E_{i,4},E_{j,4}),\) pour \(i,j=1,2,3,4\text{.}\)
-
On place un objet \((a,b)\) dans une boîte \((E_{i,4},E_{j,4})\) si \(a\in E_{i,4}\) et \(b\in E_{j,4},\) c’est-à-dire que \(a\equiv i\mod 4\) et \(b\equiv j\mod 4\text{.}\)
Puisqu’il ya plus d’objets que de boîtes, il y aura au moins deux objets dans la même boîte. Ainsi, on aura \((a,b)\) et \((c,d)\) tels que \(a\equiv c \mod 4\) et \(b\equiv d \mod 4\text{.}\)
9.
Soit \((x_i,y_i),\,i=1,2,3,4,5\) cinq points du plan cartésien \(\R^2\text{.}\) Montrer que si \(x_i,\,y_i\in\,\Z\) pour \(i=1,2,3,4,5\) alors le point milieu d’au moins un des segments reliant une paire de ces points a des coordonnées entières.Indice 1.
Indice 2.
Solution.
On remarque qu’un si on a deux points \((x_1,y_1)\) et \((x_2,y_2)\text{,}\) alors leur point milieu est \(\left(\frac{x_1+x_2}{2},\frac{y_1+y_2}{2}\right)\text{.}\) La fraction \(\frac{x_1+x_2}{2}\) sera un entier si et seulement si \(x_1+x_2\equiv 0\ \mod 2\text{.}\) De même la fraction \(\frac{y_1+y_2}{2}\) sera un entier si et seulement si \(y_1+y_2\equiv 0\ \mod 2\text{.}\)
Ensuite, on veut trouver une condition pour vérifier quand est-ce qu’une somme de deux entiers, disons \(a\) et \(b\text{,}\) donne un nombre pair. On remarque que \(1+1 \equiv 0\ \mod 2 \) et \(0+0 \equiv 0\ \mod 2 \text{,}\) alors que \(1+0 \equiv 1\ \mod 2 \) et \(0+1 \equiv 1\ \mod 2 \text{.}\) Ainsi, \(a\equiv b \ \mod 2\) si et seulement si \(a+b\equiv 0 \ \mod 2\text{.}\)
-
Objets: Les \(5\) paires \((x_i,y_i)\)
-
Boîtes: Les \(4\) couples \((0,0),\ (0,1),\ (1,0),\ (1,1)\text{.}\)
-
On place un objet \((x_i,y_i)\) dans une boîte \((r_1,r_2)\) si \(x_1\equiv r_1 \ \mod 2\) et \(y_1\equiv r_2 \ \mod 2\text{.}\) Par exemple, l’objet \((14, 101)\) est placé dans la boîte \((0,1)\) car \(14\equiv 0 \ \mod 2\) et \(101\equiv 1 \ \mod 2\text{.}\)
Puisqu’il ya plus d’objets que de boîtes, il y aura au moins deux objets dans la même boîte. Ainsi, on aura \((x_i,y_i)\) et \((x_j,y_j)\) tels que \(x_i\equiv x_j \mod 2\) et \(y_i\equiv y_j \mod 2\text{.}\) Par ce qui précède, on a que \(\left(\frac{x_1+x_2}{2},\frac{y_1+y_2}{2}\right) \in \Z\times \Z\text{,}\) c’est-à-dire que \(\frac{x_1+x_2}{2}\) et \(\frac{y_1+y_2}{2}\) sont des entiers.
Exercices supplémentaires
10.
Soit \(n\gt 0\) un entier. Démontrer que si on choisit aléatoirement \(n+1\) entiers quelconques, alors deux de ces entiers ont exactement le même reste lorsqu’ils sont divisés par \(n\text{.}\)
11.
Soit \(n \gt 0\) un entier. Démontrer que, dans tout ensemble de \(n\) entiers consécutifs, il y a exactement un entier qui est divisible par \(n\text{.}\)
12.
Soit \((x_i,y_i,z_i),\,i=1,2,\dots,8,9\) neuf points de l’espace \(\R^3\text{.}\) Montrer que si \(x_i,\,y_i\, z_i\in\,\Z\) pour tout \(i\) alors le point milieu d’au moins un des segments reliant une paire de ces points a des coordonnées entières.13.
On suppose qu’une université offre, durant une session \(300\) cours différents. Sachant qu’il existe \(20\) périodes durant lesquels on peut donner un cours, combien de salles de classe sont nécessaires?
