Devoir surveillé — Dénombrement

Consignes générales pour l'ensemble du sujet, à lire avant de commencer. Les cinq exercices sont indépendants et peuvent être traités dans l'ordre de votre choix ; à l'intérieur de l'exercice 5, en revanche, les trois parties s'enchaînent et la partie A sert d'outil aux deux suivantes. Chaque dénombrement doit être justifié : on précisera l'ensemble compté, le modèle utilisé, et la raison pour laquelle la construction proposée fournit chaque objet une fois et une seule. Un résultat numérique sans justification ne rapporte aucun point ; une justification correcte dont le calcul final est faux en rapporte presque tous. La calculatrice est interdite, et tous les nombres demandés sont calculables à la main.

On note $E$ l'ensemble des entiers qui s'écrivent avec exactement cinq chiffres en base dix, c'est-à-dire

$$E=[\text{\hspace{0.17em}⁣}[10000,99999]\text{\hspace{0.17em}⁣}]\mathrm{.}$$

Un élément $N$ de $E$ s'écrit de façon unique $N=\overline{a_1{a}_2{a}_3{a}_4{a}_5}$, où $a_1$ est le chiffre des dizaines de milliers et $a_5$ celui des unités, avec $a_1\in [\text{\hspace{0.17em}⁣}[1,9]\text{\hspace{0.17em}⁣}]$ et $a_2,a_3,a_4,a_5\in [\text{\hspace{0.17em}⁣}[0,9]\text{\hspace{0.17em}⁣}]$. La contrainte $a_1\mathrm{\ne }0$ est la seule différence avec une suite libre de cinq chiffres, et c'est elle qu'il faudra surveiller à chaque question.

1. (0,25 pt) Déterminer $\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(E)$ de deux façons : en comptant les entiers de l'intervalle, puis par le principe multiplicatif appliqué aux cinq chiffres.

2. (0,5 pt) Combien d'éléments de $E$ ont leurs cinq chiffres deux à deux distincts ?

3. (0,5 pt) Combien d'éléments de $E$ comportent au moins un chiffre égal à $7$ ?

4. (0,5 pt) Un élément de $E$ est dit palindrome lorsqu'il se lit de la même façon dans les deux sens, c'est-à-dire lorsque $a_1=a_5$ et $a_2=a_4$. Combien $E$ compte-t-il de palindromes ?

5. (0,75 pt) a. Combien d'éléments de $E$ ont leurs chiffres rangés dans l'ordre strictement croissant, c'est-à-dire vérifient $a_1<a_2<a_3<a_4<a_5$ ?

b. Combien d'éléments de $E$ ont leurs chiffres rangés dans l'ordre strictement décroissant ? Expliquer pourquoi les deux réponses diffèrent.

6. (0,5 pt) Combien d'éléments de $E$ ont une somme de chiffres $a_1+a_2+a_3+a_4+a_5$ paire ? On construira un tel entier par choix successifs en traitant le dernier chiffre en dernier.

Soient $m$ et $n$ deux entiers naturels non nuls. On appelle quadrillage $m\times n$ la figure formée, dans le plan, par les $m+1$ droites verticales d'équations $x=0$, $x=1$, …, $x=m$ et les $n+1$ droites horizontales d'équations $y=0$, $y=1$, …, $y=n$. Ces droites découpent le rectangle $[0,m]\times [0,n]$ en $mn$ petits carrés de côté $1$, appelés cases : pour $i\in [\text{\hspace{0.17em}⁣}[1,m]\text{\hspace{0.17em}⁣}]$ et $j\in [\text{\hspace{0.17em}⁣}[1,n]\text{\hspace{0.17em}⁣}]$, la case de coordonnées $(i,j)$ est le carré $[i-1,i]\times [j-1,j]$.

On appelle rectangle du quadrillage tout rectangle dont les quatre côtés sont portés par des droites du quadrillage et dont les deux dimensions sont non nulles. Un tel rectangle est réunion d'un certain nombre de cases, et ce nombre est son aire.

1. (0,5 pt) Justifier qu'un rectangle du quadrillage est entièrement déterminé par la donnée d'une paire de droites verticales distinctes et d'une paire de droites horizontales distinctes, et que réciproquement toute telle donnée définit un rectangle du quadrillage. En déduire le nombre de rectangles du quadrillage $m\times n$, puis les valeurs numériques pour $m=6$, $n=4$, et pour $m=n=8$.

2. (0,5 pt) Soit $c$ un entier tel que $1⩽c⩽\min (m,n)$. Dénombrer les rectangles du quadrillage qui sont des carrés de côté $c$, puis en déduire le nombre total de carrés du quadrillage sous forme d'une somme. Donner les valeurs numériques pour $m=6$, $n=4$, et pour $m=n=8$.

3. (0,5 pt) Soient $i\in [\text{\hspace{0.17em}⁣}[1,m]\text{\hspace{0.17em}⁣}]$ et $j\in [\text{\hspace{0.17em}⁣}[1,n]\text{\hspace{0.17em}⁣}]$. Démontrer que le nombre de rectangles du quadrillage contenant la case $(i,j)$ vaut

$$i(m+1-i)\times j(n+1-j)\mathrm{.}$$

Donner les valeurs numériques, pour $m=n=8$, dans le cas d'une case de coin et dans le cas de la case $(4,4)$.

4. (0,75 pt) Démontrer que, pour tout entier $m⩾1$,

$$\sum _{i=1}^{m}i(m+1-i)=\left(\genfrac{}{}{0px}{}{m+2}{3}\right)\mathrm{.}$$

On comptera de deux façons l'ensemble des triplets d'entiers $(a,i,b)$ vérifiant $0⩽a<i⩽b⩽m$. Contrôler la formule pour $m=3$.

5. (0,75 pt) On note $\mathcal{A}$ la somme des aires de tous les rectangles du quadrillage $m\times n$. Démontrer, par un double comptage que l'on décrira soigneusement, que

$$\mathcal{A}=\left(\genfrac{}{}{0px}{}{m+2}{3}\right)\left(\genfrac{}{}{0px}{}{n+2}{3}\right)\mathrm{.}$$

6. (0,5 pt) Contrôler la formule de la question 5. sur les deux cas $m=n=1$ et $m=2$, $n=1$, en énumérant les rectangles concernés. Donner enfin la valeur de $\mathcal{A}$ pour $m=n=8$ et l'aire moyenne d'un rectangle de ce quadrillage.

Soit $n$ un entier naturel non nul et $E=[\text{\hspace{0.17em}⁣}[1,n]\text{\hspace{0.17em}⁣}]$. On note $\mathcal{F}(E,E)$ l'ensemble des applications de $E$ dans $E$. Une application $f\in \mathcal{F}(E,E)$ est dite idempotente lorsque

$$f\circ f=f,$$

c'est-à-dire lorsque $f(f(x))=f(x)$ pour tout $x\in E$. On note ${\mathcal{I}}_n$ l'ensemble des applications idempotentes de $E$ dans $E$, et $I_n=\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}({\mathcal{I}}_n)$.

Pour $f\in \mathcal{F}(E,E)$, on note $\mathrm{I}\mathrm{m}(f)=f(E)=\{f(x);x\in E\}$ son image et $\mathrm{F}\mathrm{i}\mathrm{x}(f)=\{x\in E;f(x)=x\}$ l'ensemble de ses points fixes. Une application de $[\text{\hspace{0.17em}⁣}[1,n]\text{\hspace{0.17em}⁣}]$ dans $[\text{\hspace{0.17em}⁣}[1,n]\text{\hspace{0.17em}⁣}]$ est notée par la liste de ses valeurs $(f(1),f(2),\dots ,f(n))$.

1. (0,5 pt) Soit $f\in \mathcal{F}(E,E)$. Démontrer que $f$ est idempotente si et seulement si tout élément de $\mathrm{I}\mathrm{m}(f)$ est un point fixe de $f$. En déduire que, pour une application idempotente, $\mathrm{I}\mathrm{m}(f)=\mathrm{F}\mathrm{i}\mathrm{x}(f)$.

2. (0,5 pt) Déterminer ${\mathcal{I}}_1$, puis ${\mathcal{I}}_2$ en écrivant les quatre applications de $[\text{\hspace{0.17em}⁣}[1,2]\text{\hspace{0.17em}⁣}]$ dans lui-même et en indiquant lesquelles sont idempotentes. Donner $I_1$ et $I_2$.

3. (0,75 pt) Soit $k\in [\text{\hspace{0.17em}⁣}[1,n]\text{\hspace{0.17em}⁣}]$. Démontrer que le nombre d'applications idempotentes de $E$ dans $E$ dont l'image possède exactement $k$ éléments vaut

$$\left(\genfrac{}{}{0px}{}{n}{k}\right)k^{n-k}\mathrm{.}$$

On décrira précisément la construction d'une telle application et l'on justifiera qu'elle fournit chaque application cherchée une fois et une seule.

4. (0,5 pt) En déduire une expression de $I_n$ sous forme de somme, puis calculer $I_3$, $I_4$ et $I_5$.

5. (0,5 pt) Démontrer qu'une application idempotente injective est nécessairement l'identité de $E$. Qu'en est-il d'une application idempotente surjective ?

6. (0,75 pt) On suppose $n⩾2$. Combien y a-t-il d'applications idempotentes de $E$ dans $E$ dont l'image possède exactement $n-1$ éléments ? Combien sont constantes ? Vérifier la cohérence de ces deux réponses avec le détail du calcul de $I_4$ effectué à la question 4.

Soit $n$ un entier naturel non nul. On appelle permutation de $[\text{\hspace{0.17em}⁣}[1,n]\text{\hspace{0.17em}⁣}]$ toute bijection de $[\text{\hspace{0.17em}⁣}[1,n]\text{\hspace{0.17em}⁣}]$ sur lui-même, et l'on note ${\mathcal{B}}_n$ l'ensemble de ces permutations. Une permutation $\sigma$ est notée par la liste de ses valeurs $(\sigma (1),\sigma (2),\dots ,\sigma (n))$. On dit que $j\in [\text{\hspace{0.17em}⁣}[1,n]\text{\hspace{0.17em}⁣}]$ est un point fixe de $\sigma$ lorsque $\sigma (j)=j$.

L'objet des questions 2. à 5. est d'établir, de deux façons indépendantes, l'identité

$$\sum _{k=1}^{n}k\times k!=(n+1)!-1.$$

1. (0,5 pt) Rappeler $\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}({\mathcal{B}}_n)$ en justifiant brièvement. Écrire la liste des éléments de ${\mathcal{B}}_3$, et repérer ceux qui vérifient $\sigma (1)<\sigma (2)$.

2. (0,75 pt) On suppose $n⩾2$. Pour $m\in [\text{\hspace{0.17em}⁣}[1,n]\text{\hspace{0.17em}⁣}]$, on note ${\mathcal{A}}_m$ l'ensemble des permutations $\sigma$ de $[\text{\hspace{0.17em}⁣}[1,n]\text{\hspace{0.17em}⁣}]$ telles que

$$\sigma (j)=j\text{ pour tout }j\in [\text{\hspace{0.17em}⁣}[m+1,n]\text{\hspace{0.17em}⁣}]\text{et}\sigma (m)\mathrm{\ne }m,$$

autrement dit celles dont $m$ est le plus grand point non fixe. Démontrer que ${\mathcal{A}}_1$ est vide, puis que les ensembles ${\mathcal{A}}_2,{\mathcal{A}}_3,\dots ,{\mathcal{A}}_n$ et le singleton $\{\mathrm{i}\mathrm{d}\}$ forment une partition de ${\mathcal{B}}_n$.

3. (0,75 pt) Soit $m\in [\text{\hspace{0.17em}⁣}[2,n]\text{\hspace{0.17em}⁣}]$. Démontrer que

$$\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}({\mathcal{A}}_m)=m!-(m-1)!=(m-1)(m-1)!\mathrm{.}$$

4. (0,75 pt) En déduire que, pour tout entier $n⩾2$,

$$\sum _{k=1}^{n-1}k\times k!=n!-1,$$

puis l'identité annoncée en préambule. Contrôler celle-ci pour $n=5$ en écrivant les cinq termes de la somme.

5. (0,5 pt) Retrouver l'identité par un second raisonnement, en remarquant que $k\times k!$ s'écrit comme une différence de deux factorielles consécutives.

6. (0,75 pt) On suppose $n⩾2$. À une permutation $\sigma$ de $[\text{\hspace{0.17em}⁣}[1,n]\text{\hspace{0.17em}⁣}]$, on associe l'application ${\sigma }^{\star }$ définie par

$${\sigma }^{\star }(1)=\sigma (2),{\sigma }^{\star }(2)=\sigma (1),{\sigma }^{\star }(j)=\sigma (j)\text{ pour }j\in [\text{\hspace{0.17em}⁣}[3,n]\text{\hspace{0.17em}⁣}]\mathrm{.}$$

a. Démontrer que ${\sigma }^{\star }$ est une permutation de $[\text{\hspace{0.17em}⁣}[1,n]\text{\hspace{0.17em}⁣}]$, que ${\sigma }^{\star }\mathrm{\ne }\sigma$, et que ${\left({\sigma }^{\star }\right)}^{\star }=\sigma$.

b. En déduire que le nombre de permutations de $[\text{\hspace{0.17em}⁣}[1,n]\text{\hspace{0.17em}⁣}]$ vérifiant $\sigma (1)<\sigma (2)$ vaut ${\displaystyle \frac{n!}{2}}$. Contrôler ce résultat sur la liste établie à la question 1.

Dans tout le problème, $n$ désigne un entier supérieur ou égal à $2$ et $E$ un ensemble de $n$ personnes. On note ${\mathcal{P}}_2(E)$ l'ensemble des parties à $2$ éléments de $E$, dont les éléments sont appelés paires.

On appelle réseau sur $E$ toute partie $R$ de ${\mathcal{P}}_2(E)$. L'interprétation est la suivante : lorsque $\{x,y\}\in R$, on dit que $x$ et $y$ se connaissent ; lorsque $\{x,y\}\mathrm{\notin }R$, on dit qu'ils s'ignorent. La relation est donc symétrique et personne ne se connaît soi-même. Pour $x\in E$, on appelle degré de $x$, et l'on note $d(x)$, le nombre de personnes que $x$ connaît :

$$d(x)=\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(\{y\in E\setminus \{x\};\{x,y\}\in R\})\mathrm{.}$$

Enfin, une partie $T$ à $3$ éléments de $E$ est appelée triple, et l'on dit que le triple $T=\{x,y,z\}$ est monochrome lorsque ses trois paires $\{x,y\}$, $\{y,z\}$ et $\{x,z\}$ appartiennent toutes à $R$, ou bien n'appartiennent aucune à $R$ : autrement dit lorsque les trois personnes se connaissent deux à deux, ou bien s'ignorent deux à deux.

Les trois parties s'enchaînent : les résultats de la partie A servent dans les parties B et C.

Partie A — Compter les réseaux, compter les degrés

1. (0,5 pt) Déterminer $\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}({\mathcal{P}}_2(E))$, puis le nombre de réseaux sur $E$, et enfin, pour $p$ entier, le nombre de réseaux comportant exactement $p$ paires. Donner les trois valeurs numériques pour $n=6$ et $p=5$, et énoncer l'identité que l'on obtient en classant les réseaux selon leur nombre de paires.

2. (0,75 pt) Soit $R$ un réseau sur $E$. On pose

$$\mathcal{C}=\{(x,P)\in E\times R;x\in P\}\mathrm{.}$$

En dénombrant $\mathcal{C}$ de deux façons, démontrer que

$$\sum _{x\in E}d(x)=2\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(R)\mathrm{.}$$

3. (0,5 pt) En déduire que le nombre de personnes de degré impair est pair. Peut-on réunir cinq personnes de sorte que chacune en connaisse exactement trois autres ?

4. (0,5 pt) Démontrer que, dans tout réseau sur $E$, deux personnes au moins ont le même degré. On observera d'abord dans quel intervalle vit $d(x)$, puis on raisonnera par l'absurde en examinant les degrés extrêmes.

Partie B — Un réseau de six personnes

Dans toute cette partie, $n=6$.

5. (0,25 pt) Combien $E$ possède-t-il de triples ?

6. (1 pt) Démontrer que, quel que soit le réseau $R$ sur $E$, il existe au moins un triple monochrome. On fixera une personne $x$ et l'on commencera par établir que $x$ connaît au moins trois personnes ou en ignore au moins trois.

7. (0,5 pt) Le résultat précédent tombe-t-il en défaut avec cinq personnes ? On étudiera le réseau $R_0$ sur $\{1,2,3,4,5\}$ formé des cinq paires $\{1,2\}$, $\{2,3\}$, $\{3,4\}$, $\{4,5\}$ et $\{5,1\}$, et l'on conclura quant au caractère optimal du nombre $6$.

Partie C — Il y en a au moins deux

On garde $n=6$ et l'on se donne un réseau $R$ sur $E$. Pour $x\in E$, on appelle angle bicolore en $x$ toute paire $\{y,z\}$ de personnes distinctes de $x$ telle que $x$ connaisse exactement l'une des deux. On note $b(x)$ le nombre d'angles bicolores en $x$, et $N$ le nombre de triples monochromes.

8. (0,5 pt) Démontrer que $b(x)=d(x)(5-d(x))$, puis que $b(x)⩽6$ pour tout $x\in E$. Préciser les valeurs de $d(x)$ pour lesquelles ce maximum est atteint.

9. (0,5 pt) Soit $T=\{x,y,z\}$ un triple. Démontrer que $T$ porte exactement deux angles bicolores lorsqu'il n'est pas monochrome, et aucun lorsqu'il l'est. On appelle ici angle bicolore porté par $T$ tout angle bicolore en l'une des trois personnes de $T$ constitué par les deux autres.

10. (0,75 pt) En dénombrant de deux façons l'ensemble des couples $(x,A)$ où $x\in E$ et où $A$ est un angle bicolore en $x$, démontrer que $N⩾2$.

11. (0,25 pt) On partage les six personnes en deux groupes de trois, $G_1$ et $G_2$, et l'on prend pour réseau $R_1$ l'ensemble des paires formées d'une personne de $G_1$ et d'une personne de $G_2$. Déterminer le nombre de triples monochromes de ce réseau et conclure quant à la minoration de la question 10.