Devoir surveillé — Dénombrement

Consignes valables pour tout le sujet. Les cinq exercices sont indépendants et peuvent être traités dans l'ordre de votre choix ; à l'intérieur d'un exercice, en revanche, les questions s'enchaînent, et l'exercice 5 est un problème dont les trois parties se suivent. La calculatrice n'est pas autorisée : tous les calculs demandés se mènent à la main. Chaque dénombrement doit être justifié en décrivant l'ensemble compté et le modèle utilisé (produit cartésien, bijection, réunion disjointe, complémentaire, lemme du berger) ; un résultat numérique sans justification ne vaut aucun point. On donnera systématiquement une conclusion rédigée.

On note $C=[\text{\hspace{0.17em}⁣}[0,9]\text{\hspace{0.17em}⁣}]$ l'ensemble des chiffres. Tout entier $N$ de $[\text{\hspace{0.17em}⁣}[0,9999]\text{\hspace{0.17em}⁣}]$ possède une écriture à quatre chiffres $N=\overline{abcd}$, obtenue en complétant si nécessaire par des zéros à gauche : par exemple $37$ s'écrit $\overline{0037}$. Toutes les questions portent sur cette écriture à quatre chiffres.

1. (0,5 pt) Démontrer que l'application

$$\mathrm{\Phi }:C^4⟶[\text{\hspace{0.17em}⁣}[0,9999]\text{\hspace{0.17em}⁣}],(a,b,c,d)⟼1000a+100b+10c+d$$

est une bijection. Combien d'entiers de $[\text{\hspace{0.17em}⁣}[0,9999]\text{\hspace{0.17em}⁣}]$ ont leurs quatre chiffres deux à deux distincts ?

2. (0,75 pt) Combien d'entiers de $[\text{\hspace{0.17em}⁣}[0,9999]\text{\hspace{0.17em}⁣}]$ ont leurs quatre chiffres rangés dans l'ordre strictement croissant, c'est-à-dire vérifient $a<b<c<d$ ? En déduire, sans aucun nouveau calcul, le nombre de ceux dont les quatre chiffres sont rangés dans l'ordre strictement décroissant.

3. (0,75 pt) Combien d'entiers de $[\text{\hspace{0.17em}⁣}[0,9999]\text{\hspace{0.17em}⁣}]$ s'écrivent avec exactement deux chiffres distincts, c'est-à-dire dont l'écriture à quatre chiffres emploie deux chiffres différents, chacun au moins une fois ?

4. (1 pt) Combien d'entiers de $[\text{\hspace{0.17em}⁣}[0,9999]\text{\hspace{0.17em}⁣}]$ ont une somme de chiffres paire ? On donnera deux démonstrations indépendantes : la première construira une involution de $C^4$, la seconde procédera par un dénombrement direct.

1. (1 pt) Soient $E$ et $F$ deux ensembles finis non vides, $f:E⟶F$ une application et $k$ un entier naturel non nul. Démontrer le principe des tiroirs renforcé : si $\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(E)>k\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(F)$, alors il existe $y\in F$ tel que

$$\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(f^{-1}(\{y\}))⩾k+1.$$

Que devient cet énoncé pour $k=1$ ?

2. (1,25 pt) Soient $n$ un entier naturel non nul et $a_1,a_2,\dots ,a_n$ des entiers relatifs quelconques. Démontrer qu'il existe deux entiers $i$ et $j$ tels que $1⩽i⩽j⩽n$ et tels que $n$ divise

$$a_i+a_{i+1}+\cdots +a_j\mathrm{.}$$

On introduira les sommes $s_0=0$ et $s_m=a_1+\cdots +a_m$, puis leurs restes dans la division euclidienne par $n$.

3. (0,75 pt) Démontrer que le résultat de la question 2. est optimal : pour tout entier $n⩾2$, exhiber $n-1$ entiers $a_1,\dots ,a_{n-1}$ tels qu'aucune des sommes $a_i+\cdots +a_j$, avec $1⩽i⩽j⩽n-1$, ne soit divisible par $n$.

4. (1 pt) Soient $n$ un entier naturel non nul et $a_1,\dots ,a_{2n}$ des entiers relatifs. En appliquant la question 1. avec $k=2$, démontrer qu'il existe quatre indices

$$1⩽i⩽j<i^{\mathrm{\prime }}⩽j^{\mathrm{\prime }}⩽2n$$

tels que les deux sommes $a_i+\cdots +a_j$ et $a_{i^{\mathrm{\prime }}}+\cdots +a_{j^{\mathrm{\prime }}}$ soient toutes deux divisibles par $n$. Autrement dit, la suite contient deux blocs de termes consécutifs, disjoints, dont les deux sommes sont divisibles par $n$.

Soit $n$ un entier naturel non nul. Pour $m\in [\text{\hspace{0.17em}⁣}[0,n]\text{\hspace{0.17em}⁣}]$, on pose

$$T(n,m)=\sum _{k=0}^m(-1{)}^k{\displaystyle \left(\genfrac{}{}{0px}{}{n}{k}\right)}\mathrm{.}$$

On adopte la convention usuelle ${\displaystyle \left(\genfrac{}{}{0px}{}{a}{b}\right)}=0$ dès que $b>a$.

1. (0,5 pt) Écrire les lignes $n=5$ et $n=6$ du triangle de Pascal. Calculer $T(6,m)$ pour $m$ allant de $0$ à $6$, comparer la liste des valeurs absolues obtenues à la ligne $n=5$, et conjecturer une expression de $T(n,m)$.

2. (1,5 pt) Démontrer la conjecture. On pourra poser $u_k=(-1{)}^k{\displaystyle \left(\genfrac{}{}{0px}{}{n-1}{k}\right)}$ pour $k\in [\text{\hspace{0.17em}⁣}[0,n]\text{\hspace{0.17em}⁣}]$ et montrer que le terme général de la somme s'écrit comme la différence de deux termes consécutifs de la suite $(u_k)$.

3. (0,5 pt) Soit $E=[\text{\hspace{0.17em}⁣}[1,n]\text{\hspace{0.17em}⁣}]$ et $m\in [\text{\hspace{0.17em}⁣}[0,n]\text{\hspace{0.17em}⁣}]$. On note ${\mathcal{A}}_m$ l'ensemble des parties de $E$ de cardinal pair inférieur ou égal à $m$, et ${\mathcal{B}}_m$ celui des parties de $E$ de cardinal impair inférieur ou égal à $m$. Exprimer $\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}({\mathcal{A}}_m)-\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}({\mathcal{B}}_m)$, dire lequel de ces deux ensembles est le plus grand selon la parité de $m$, et traiter le cas $n=7$, $m=3$.

4. (0,5 pt) Que donne la formule de la question 2. pour $m=n$ ? Retrouver ce résultat directement par la formule du binôme. Contrôler enfin la formule pour $n=6$ et $m=3$, en calculant séparément les deux membres.

Soit $q$ un entier supérieur ou égal à $2$ : on dispose de $q$ couleurs, numérotées de $1$ à $q$.

Pour $n⩾1$, une file de $n$ cases bien coloriée est un $n$-uplet $x=(x_1,\dots ,x_n)$ de couleurs tel que deux cases voisines portent des couleurs différentes, c'est-à-dire tel que $x_i\mathrm{\ne }{x}_{i+1}$ pour tout $i\in [\text{\hspace{0.17em}⁣}[1,n-1]\text{\hspace{0.17em}⁣}]$. On note $F_n$ l'ensemble de ces $n$-uplets.

Pour $n⩾3$, une ronde de $n$ cases bien coloriée est une file bien coloriée dont, de plus, la dernière case et la première portent des couleurs différentes : les cases sont disposées en cercle et la case $n$ est voisine de la case $1$. On note

$$R_n=\{x\in F_n;x_n\mathrm{\ne }{x}_1\}\mathrm{.}$$

1. (0,75 pt) Démontrer que $\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(F_n)=q(q-1{)}^{n-1}$ pour tout $n⩾1$. On pourra appliquer le lemme du berger à l'application qui supprime la dernière coordonnée.

2. (1,25 pt) Soit $n⩾4$. Démontrer que l'application « supprimer la dernière coordonnée » est une bijection de $\{x\in F_n;x_n=x_1\}$ sur $R_{n-1}$, en explicitant sa réciproque. En déduire que

$$\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}\left(R_n\right)+\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}\left(R_{n-1}\right)=q(q-1{)}^{n-1}\text{pour tout }n⩾4.$$

Calculer par ailleurs $\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(R_3)$.

3. (1,25 pt) En déduire, par récurrence, que pour tout entier $n⩾3$,

$$\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}\left(R_n\right)=(q-1{)}^n+(-1{)}^n(q-1)\mathrm{.}$$

4. (0,75 pt) Applications.

Dans tout le problème, $n$ désigne un entier naturel non nul et $E=[\text{\hspace{0.17em}⁣}[1,n]\text{\hspace{0.17em}⁣}]$.

On appelle chaîne maximale de $\mathcal{P}(E)$ tout $(n+1)$-uplet $\mathcal{C}=(A_0,A_1,\dots ,A_n)$ de parties de $E$ tel que

$$A_0\subset A_1\subset \cdots \subset A_n\text{et}\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}\left(A_i\right)=i\text{ pour tout }i\in [\text{\hspace{0.17em}⁣}[0,n]\text{\hspace{0.17em}⁣}]\mathrm{.}$$

On a donc nécessairement $A_0=\mathrm{\varnothing }$ et $A_n=E$. On note $\mathfrak{C}$ l'ensemble des chaînes maximales. On dit qu'une chaîne maximale $\mathcal{C}=(A_0,\dots ,A_n)$ passe par une partie $A$ de $E$ lorsque $A=A_i$ pour un indice $i$, nécessairement égal à $\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(A)$.

On appelle antichaîne toute famille $\mathcal{A}$ de parties de $E$ (c'est-à-dire toute partie $\mathcal{A}$ de $\mathcal{P}(E)$) dont deux éléments distincts ne sont jamais comparables pour l'inclusion :

$$\mathrm{\forall }A\in \mathcal{A},\mathrm{\forall }{A}^{\mathrm{\prime }}\in \mathcal{A},A\subset A^{\mathrm{\prime }}⟹A=A^{\mathrm{\prime }}\mathrm{.}$$

Le but du problème est de majorer le nombre de parties d'un ensemble fini que l'on peut choisir deux à deux non comparables. Les trois parties s'enchaînent.

Partie A — Les chaînes maximales

A1. (0,75 pt) Démontrer que l'application

$$\mathrm{\Sigma }:{\mathfrak{S}}_n⟶\mathfrak{C},\sigma ⟼(\mathrm{\varnothing },\{\sigma (1)\},\{\sigma (1),\sigma (2)\},\dots ,\{\sigma (1),\dots ,\sigma (n)\})$$

est une bijection, en explicitant sa réciproque. En déduire $\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(\mathfrak{C})$. Énumérer les chaînes maximales dans le cas $n=3$.

A2. (0,5 pt) Soit $A$ une partie de $E$ de cardinal $k$. Démontrer que le nombre de chaînes maximales passant par $A$ vaut $k!(n-k)!$.

A3. (0,5 pt) Vérifier l'égalité $k!(n-k)!={\displaystyle \frac{n!}{{\displaystyle \left(\genfrac{}{}{0px}{}{n}{k}\right)}}}$. Calculer $k!(n-k)!$ pour $n=4$ et pour chacune des valeurs $k=0,1,2,3,4$, puis dire pour quelle valeur de $k$ ce nombre est le plus petit.

Partie B — L'inégalité de Lubell

Dans toute cette partie, $\mathcal{A}$ désigne une antichaîne de parties de $E$.

B1. (0,5 pt) Démontrer qu'une chaîne maximale passe par au plus une partie appartenant à $\mathcal{A}$.

B2. (1,25 pt) En dénombrant de deux façons l'ensemble

$$\mathcal{X}=\{(\mathcal{C},A)\in \mathfrak{C}\times \mathcal{A};\mathcal{C}\text{ passe par }A\},$$

démontrer successivement les deux inégalités

$$\sum _{A\in \mathcal{A}}\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(A)!(n-\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(A))!⩽n!\text{puis}\sum _{A\in \mathcal{A}}\frac{1}{{\displaystyle \left(\genfrac{}{}{0px}{}{n}{\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(A)}\right)}}⩽1.$$

B3. (0,5 pt) Traiter les deux exemples suivants. Pour $k\in [\text{\hspace{0.17em}⁣}[0,n]\text{\hspace{0.17em}⁣}]$ fixé, vérifier que $\mathcal{A}={\mathcal{P}}_k(E)$ est une antichaîne et que la seconde inégalité de B2 y est une égalité. Puis, pour $n=3$ et $\mathcal{A}=\{\{1\},\{2,3\}\}$, vérifier qu'il s'agit d'une antichaîne et calculer la somme correspondante.

Partie C — Le théorème de Sperner

C1. (0,75 pt) Soit $k\in [\text{\hspace{0.17em}⁣}[0,n-1]\text{\hspace{0.17em}⁣}]$. Démontrer l'équivalence

$${\displaystyle \left(\genfrac{}{}{0px}{}{n}{k+1}\right)}⩾{\displaystyle \left(\genfrac{}{}{0px}{}{n}{k}\right)}⟺k⩽\frac{n-1}{2},$$

puis en déduire que le plus grand des coefficients binomiaux ${\displaystyle \left(\genfrac{}{}{0px}{}{n}{0}\right)},{\displaystyle \left(\genfrac{}{}{0px}{}{n}{1}\right)},\dots ,{\displaystyle \left(\genfrac{}{}{0px}{}{n}{n}\right)}$ est ${\displaystyle \left(\genfrac{}{}{0px}{}{n}{\lfloor n\mathrm{/}2\rfloor }\right)}$.

C2. (0,75 pt) En déduire le théorème de Sperner : toute antichaîne $\mathcal{A}$ de parties de $E$ vérifie

$$\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}\left(\mathcal{A}\right)⩽{\displaystyle \left(\genfrac{}{}{0px}{}{n}{\lfloor n\mathrm{/}2\rfloor }\right)}\mathrm{.}$$

C3. (0,5 pt) Démontrer que cette majoration est atteinte. Combien de parties de $[\text{\hspace{0.17em}⁣}[1,10]\text{\hspace{0.17em}⁣}]$ peut-on au maximum choisir, deux à deux non comparables pour l'inclusion ?