Devoir surveillé — Raisonnement et vocabulaire ensembliste

Soit $n$ un entier naturel non nul. Un tableau carré d'ordre $n$ est la donnée d'un nombre réel $t_{i,j}$ pour chaque couple $(i,j)\in I\times I$, où $I=\{1,2,\dots ,n\}$ ; l'entier $i$ repère la ligne et l'entier $j$ la colonne. Les propositions écrites ci-dessous se lisent donc sur un tableau de n'importe quel ordre, l'ensemble $I$ étant celui de ce tableau. Dans les questions 1. à 5., on prend $n=4$, donc $I=\{1,2,3,4\}$, et l'on travaille sur le tableau $T$ suivant.

On considère les quatre propositions suivantes.

$$P_1:\mathrm{\forall }i\in I,\mathrm{\exists }j\in I,t_{i,j}=0P_2:\mathrm{\exists }j\in I,\mathrm{\forall }i\in I,t_{i,j}=0$$ $$P_3:\mathrm{\exists }i\in I,\mathrm{\forall }j\in I,t_{i,j}⩽2P_4:\mathrm{\forall }i\in I,\mathrm{\forall }j\in I,t_{i,j}=t_{j,i}$$

1. Traduire en langage courant, sans aucun symbole, les propositions $P_1$, $P_2$ et $P_4$. (0,25 point)

2. Déterminer la valeur de vérité de chacune des quatre propositions sur le tableau $T$. Chaque réponse sera justifiée : par un examen complet si la proposition est vraie, par un contre-exemple explicite sinon. (0,75 point)

3. Écrire la négation de chacune des quatre propositions. On donnera une écriture dans laquelle plus aucune négation ne porte sur une proposition composée. (0,5 point)

4. Cette question porte sur un tableau carré d'ordre quelconque, et non plus sur le seul tableau $T$. Démontrer l'implication $P_2⟹P_1$. La réciproque est-elle vraie ? (0,5 point)

5. On note $R$ la proposition : « le tableau possède deux lignes identiques ». (0,5 point)

a. Écrire $R$ à l'aide de quantificateurs.

b. Écrire la négation de $R$ sous une forme où figure une implication.

c. Déterminer la valeur de vérité de $R$ sur le tableau $T$.

6. On pose $P_5:\mathrm{\forall }j\in I,\mathrm{\exists }i\in I,t_{i,j}=0$. Un étudiant affirme que, pour tout tableau carré, $P_1⟹P_5$. Expliquer pourquoi le tableau $T$ ne permet pas de le contredire, puis réfuter son affirmation par un contre-exemple explicite, que l'on cherchera sur un tableau carré d'ordre $2$. Écrire enfin la contraposée de l'affirmation de l'étudiant. (0,5 point)

Dans tout l'exercice, $n$ désigne un entier naturel non nul et $x_1,x_2,\dots ,x_n$ des nombres réels. On appelle moyenne de cette famille le réel

$$m=\frac{1}{n}\sum _{k=1}^n{x}_k\mathrm{.}$$

1. Soient $a_1,a_2,\dots ,a_n$ des réels positifs ou nuls tels que ${\displaystyle \sum _{k=1}^n{a}_k=0}$. Démontrer que $a_k=0$ pour tout $k\in \{1,2,\dots ,n\}$. (0,5 point)

2. (0,75 point)

a. Écrire à l'aide de quantificateurs la proposition $S$ : « il existe un indice $k$ tel que $x_k⩾m$ », puis sa négation.

b. Calculer ${\displaystyle \sum _{k=1}^n(m-x_k)}$, puis démontrer par l'absurde que $S$ est vraie, quelle que soit la famille de réels considérée.

c. En déduire, sans refaire de démonstration, qu'il existe un indice $\mathrm{\ell }$ tel que $x_{\mathrm{\ell }}⩽m$.

3. Démontrer que les trois assertions suivantes sont équivalentes. (0,75 point)

4. Un devoir noté sur $20$ a été rendu à une classe de $24$ élèves, et la moyenne de la classe vaut exactement $\mathrm{12,5}$. (0,5 point)

a. Justifier qu'au moins un élève a une note supérieure ou égale à $\mathrm{12,5}$, et qu'au moins un élève a une note inférieure ou égale à $\mathrm{12,5}$.

b. Peut-on affirmer qu'au moins un élève a une note supérieure ou égale à $13$ ? Justifier.

5. Déterminer, par un raisonnement par analyse et synthèse, tous les triplets $(x_1,x_2,x_3)$ de réels tels que chacun des trois nombres soit égal à la moyenne des deux autres. (0,5 point)

6. On note $G=\{k\in \{1,2,\dots ,n\};x_k>m\}$ l'ensemble des indices des termes strictement supérieurs à la moyenne, et $N=\{k\in \{1,2,\dots ,n\};x_k⩽m\}$ celui des autres. On pourra réutiliser, au signe près, la somme calculée à la question 2. b. Démontrer que

$$\sum _{k=1}^n\mid x_k-m\mid =2\sum _{k\in G}(x_k-m)\mathrm{.}$$

Vérifier le résultat sur la famille $(1,2,6)$. (0,5 point)

Les deux parties sont indépendantes. Chaque démonstration par récurrence fera apparaître explicitement la proposition étudiée, l'initialisation, l'hérédité et la conclusion.

Partie A. Un entier comme combinaison de $3$ et de $5$

On s'intéresse aux entiers naturels $n$ qui peuvent s'écrire $n=3a+5b$, avec $a\in \mathbb{N}$ et $b\in \mathbb{N}$.

1. Écrire chacun des entiers $8$, $9$, $10$, $11$ et $12$ sous cette forme, en précisant le couple $(a,b)$ utilisé. (0,25 point)

2. Démontrer que $7$ ne peut pas s'écrire sous cette forme. (0,25 point)

3. Démontrer par récurrence forte que tout entier $n⩾8$ s'écrit $n=3a+5b$ avec $a\in \mathbb{N}$ et $b\in \mathbb{N}$. (1 point)

4. Un candidat n'a vérifié la propriété qu'au rang $8$, le reste de sa démonstration étant inchangé. Déterminer exactement l'ensemble des entiers $n$ pour lesquels sa rédaction établit $\mathcal{P}(n)$, et le décrire en une phrase. En déduire le nombre d'initialisations que cette récurrence exige réellement. (0,25 point)

Partie B. Encadrer une suite en passant au carré

On considère la suite $(u_n{)}_{n\in \mathbb{N}}$ définie par

$$u_0=1\text{et}\mathrm{\forall }n\in \mathbb{N},u_{n+1}=u_n+\frac{1}{u_n}\mathrm{.}$$

5. Démontrer par récurrence que $u_n⩾1$ pour tout $n\in \mathbb{N}$. Cette inégalité servira deux fois dans la suite du problème, à deux endroits différents et pour deux raisons différentes : après avoir traité les questions 7. et 8., on reviendra dire précisément où, et à quoi elle sert chaque fois. (0,5 point)

6. Calculer les valeurs exactes de $u_1$, $u_2$ et $u_3$. (0,25 point)

7. Démontrer par récurrence que $u_n^2⩾2n+1$ pour tout $n\in \mathbb{N}$, et en déduire une minoration de $u_n$. (0,5 point)

8. On pourra réutiliser le développement $u_{n+1}^2=u_n^2+2+{\displaystyle \frac{1}{u_n^2}}$ obtenu à la question précédente, ainsi que la majoration ${\displaystyle \frac{1}{u_n^2}}⩽1$, conséquence immédiate de la question 5. Démontrer que $u_n^2⩽3n+1$ pour tout $n\in \mathbb{N}$, en déduire un encadrement de $u_n$, et le vérifier pour $n=3$. Expliquer enfin pourquoi les questions 7. et 8. portent sur $u_n^2$ plutôt que sur $u_n$. (0,5 point)

Dans tout l'exercice, $E$ désigne un ensemble fini et non vide. Pour une partie $A$ de $E$, on note $\mathrm{c}\mathrm{a}\mathrm{r}\mathrm{d}(A)$ son nombre d'éléments, et ${\mathbf{1}}_A:E\to \{0,1\}$ sa fonction indicatrice, définie par ${\mathbf{1}}_A(x)=1$ si $x\in A$ et ${\mathbf{1}}_A(x)=0$ sinon. On utilisera librement la formule du cours

$${\mathbf{1}}_{A\cap B}={\mathbf{1}}_A{\mathbf{1}}_B,$$

ainsi que la formule du cours donnant le produit de deux sommes finies,

$$\left(\sum _{i=1}^n{a}_i\right)\left(\sum _{j=1}^m{b}_j\right)=\sum _{i=1}^n\sum _{j=1}^m{a}_i{b}_j\mathrm{.}$$

Toutes les sommes de cet exercice sont indexées par des ensembles finis, et l'on adopte la convention usuelle : une somme indexée par l'ensemble vide vaut $0$.

Enfin, $A_1,A_2,\dots ,A_n$ désignent $n$ parties de $E$, où $n$ est un entier naturel non nul, et l'on pose, pour tout $x\in E$,

$$d(x)=\sum _{i=1}^n{\mathbf{1}}_{A_i}(x)\mathrm{.}$$

1. Démontrer que, pour toute partie $A$ de $E$, ${\displaystyle \mathrm{c}\mathrm{a}\mathrm{r}\mathrm{d}(A)=\sum _{x\in E}{\mathbf{1}}_A(x)}$. (0,5 point)

2. Interpréter $d(x)$ en une phrase, puis démontrer que ${\displaystyle \sum _{x\in E}d(x)=\sum _{i=1}^n\mathrm{c}\mathrm{a}\mathrm{r}\mathrm{d}(A_i)}$. (0,5 point)

3. Démontrer que ${\displaystyle \sum _{x\in E}d(x{)}^2=\sum _{i=1}^n\sum _{j=1}^n\mathrm{c}\mathrm{a}\mathrm{r}\mathrm{d}(A_i\cap A_j)}$. (0,5 point)

4. Pour tout $x\in E$, on note $c(x)$ le nombre de paires $\{i,j\}$ d'indices distincts telles que $x$ appartienne à la fois à $A_i$ et à $A_j$. (1 point)

a. Exprimer $c(x)$ en fonction de $d(x)$, en justifiant le dénombrement.

b. En dénombrant de deux façons les couples $(x,\{i,j\})$ formés d'un élément $x$ de $E$ et d'une telle paire d'indices, démontrer que

$$\sum _{1⩽i<j⩽n}\mathrm{c}\mathrm{a}\mathrm{r}\mathrm{d}(A_i\cap A_j)=\frac{1}{2}\sum _{x\in E}d(x)(d(x)-1)\mathrm{.}$$

5. Contrôler les trois formules des questions 2., 3. et 4. b. sur l'exemple suivant : $E=\{1,2,3,4\}$, $n=3$, $A_1=\{1,2\}$, $A_2=\{2,3\}$ et $A_3=E$. (1 point)

6. On suppose dans cette question que $\mathrm{c}\mathrm{a}\mathrm{r}\mathrm{d}(E)=30$, que $n=10$, et que $d(x)=3$ pour tout $x\in E$. (0,5 point)

a. Déterminer ${\displaystyle \sum _{i=1}^{10}\mathrm{c}\mathrm{a}\mathrm{r}\mathrm{d}(A_i)}$, puis le cardinal commun des $A_i$ dans le cas où ils ont tous le même.

b. Déterminer ${\displaystyle \sum _{1⩽i<j⩽10}\mathrm{c}\mathrm{a}\mathrm{r}\mathrm{d}(A_i\cap A_j)}$.

Dans tout ce problème, $E$ et $F$ sont deux ensembles non vides et $f:E\to F$ est une application. On rappelle que, pour $A\subset E$ et $B\subset F$,

$$f(A)=\{y\in F;\mathrm{\exists }x\in A,y=f(x)\}\text{et}{f}^{-1}(B)=\{x\in E;f(x)\in B\},$$

et que l'écriture $f^{-1}(B)$ ne suppose pas $f$ bijective. Ces deux constructions transforment une partie en une partie : elles définissent donc deux applications entre ensembles de parties,

$$f_{\ast }:\mathcal{P}(E)⟶\mathcal{P}(F),A⟼f(A)\text{et}{f}^{\ast }:\mathcal{P}(F)⟶\mathcal{P}(E),B⟼f^{-1}(B)\mathrm{.}$$

Tout le problème consiste à comparer les propriétés de $f_{\ast }$ et de $f^{\ast }$ à celles de $f$.

Partie A. Un exemple

Dans cette partie seulement, $E=\{1,2,3,4,5\}$, $F=\{a,b,c,d\}$, et $f$ est donnée par le tableau de valeurs suivant.

1. Déterminer les six parties suivantes. (0,5 point)

2. L'application $f$ est-elle injective ? surjective ? Justifier chaque réponse. (0,25 point)

3. Exhiber une partie $A$ de $E$ telle que $f^{\ast }(f_{\ast }(A))\mathrm{\ne }A$, puis deux parties distinctes $B$ et $B^{\mathrm{\prime }}$ de $F$ telles que $f^{\ast }(B)=f^{\ast }(B^{\mathrm{\prime }})$. Qu'en déduit-on sur l'application $f^{\ast }$ ? (0,5 point)

Partie B. Les deux inclusions et leurs cas d'égalité

On revient au cas général.

4. Démontrer que $A\subset f^{\ast }(f_{\ast }(A))$ pour toute partie $A$ de $E$. (0,25 point)

5. Démontrer que $f_{\ast }(f^{\ast }(B))\subset B$ pour toute partie $B$ de $F$. (0,25 point)

6. Démontrer l'équivalence : $f$ est injective si et seulement si $f^{\ast }(f_{\ast }(A))=A$ pour toute partie $A$ de $E$. (0,75 point)

7. Démontrer l'équivalence : $f$ est surjective si et seulement si $f_{\ast }(f^{\ast }(B))=B$ pour toute partie $B$ de $F$. (0,75 point)

Partie C. L'image directe conserve

8. Démontrer que $f_{\ast }$ est injective si et seulement si $f$ est injective. (0,5 point)

9. Démontrer que $f_{\ast }$ est surjective si et seulement si $f$ est surjective. (0,5 point)

Partie D. L'image réciproque renverse

10. Démontrer que $f^{\ast }$ est injective si et seulement si $f$ est surjective. (0,75 point)

11. Démontrer que $f^{\ast }$ est surjective si et seulement si $f$ est injective. (0,5 point)

Partie E. Synthèse

12. Déduire des parties C et D que $f$ est bijective si et seulement si $f_{\ast }$ l'est, si et seulement si $f^{\ast }$ l'est. Dans ce cas, identifier l'application réciproque de $f_{\ast }$. Conclure enfin par une phrase comparant le comportement de $f_{\ast }$ et celui de $f^{\ast }$, et vérifier que la partie A en est un cas particulier, pour $f_{\ast }$ comme pour $f^{\ast }$. (0,5 point)