Devoir surveillé — Raisonnement et vocabulaire ensembliste

Dans tout l'exercice, $E$ désigne un ensemble non vide et $A$, $B$ deux parties de $E$. Le complémentaire d'une partie $X$ de $E$ est noté $\bar{X}$.

1. Traduire chacune des propositions suivantes à l'aide de quantificateurs portant sur les éléments de $E$. Les symboles $\subset$, $\cap$, $\cup$, $\mathrm{\varnothing }$ et la barre de complémentaire sont interdits dans les réponses. (0,75 point)

   a. $A\subset B$

   b. $A\cap B=\mathrm{\varnothing }$

   c. $A$ contient au moins deux éléments distincts

   d. $A=B$

2. Écrire la négation de chacune des trois propositions a., b., c. de la question 1, d'abord à l'aide de quantificateurs, puis en une phrase en français. (0,5 point)

3. Démontrer que $A\subset B$ si et seulement si $\bar{B}\subset \bar{A}$. On rédigera le sens direct en revenant à la définition de l'inclusion ; pour le sens réciproque, on pourra appliquer le sens direct aux parties $\bar{B}$ et $\bar{A}$, en admettant que $\overline{\stackrel{‾}{X}}=X$ pour toute partie $X$ de $E$. (0,5 point)

4. On considère la proposition : « pour toutes parties $X$ et $Y$ de $E$, on a $X\subset Y$ ou $Y\subset X$ ». Écrire sa négation, puis démontrer que cette proposition est fausse dans le cas $E=\{1,2,3,4\}$. (0,5 point)

Pour tout entier $n⩾1$, on pose

$$S_n=\sum _{k=1}^n{\displaystyle \frac{1}{k^2}}$$

L'objectif est de démontrer que, pour tout entier $n⩾1$, on a $S_n⩽2$.

1. Calculer $S_1$, $S_2$ et $S_3$ sous forme de fractions irréductibles. (0,25 point)

2. Pour tout entier $n⩾1$, on note ${\mathcal{H}}_n$ la proposition : « $S_n⩽2$ ». Exprimer $S_{n+1}$ en fonction de $S_n$. En supposant ${\mathcal{H}}_n$ vraie, déterminer le meilleur majorant de $S_{n+1}$ que cette seule hypothèse permette d'obtenir, et calculer de combien il dépasse $2$. (0,75 point)

3. Pour tout entier $n⩾1$, on note maintenant ${\mathcal{K}}_n$ la proposition : « $S_n⩽2-{\displaystyle \frac{1}{n}}$ ». (1,25 point)

   a. Démontrer que, pour tout entier $n⩾1$, ${\displaystyle \frac{1}{(n+1{)}^2}}⩽{\displaystyle \frac{1}{n}}-{\displaystyle \frac{1}{n+1}}$.

   b. Démontrer par récurrence que ${\mathcal{K}}_n$ est vraie pour tout entier $n⩾1$.

4. En déduire que $S_n⩽2$ pour tout entier $n⩾1$. (0,25 point)

5. La proposition ${\mathcal{K}}_n$ est plus forte que la proposition ${\mathcal{H}}_n$ : elle affirme davantage, puisqu'elle entraîne ${\mathcal{H}}_n$ sans lui être équivalente. Expliquer en trois lignes au plus, en s'appuyant sur le nombre calculé à la question 2, pourquoi une proposition plus forte peut être plus facile à démontrer par récurrence que la proposition que l'on visait. (0,25 point)

Pour tout entier $n⩾1$, on pose

$$B_n=\sum _{k=1}^n(-1{)}^k{k}^2$$

On rappelle les deux sommes usuelles : pour tout entier $p⩾1$,

$$\sum _{k=1}^{p}k={\displaystyle \frac{p(p+1)}{2}}\text{et}\sum _{k=1}^p{k}^2={\displaystyle \frac{p(p+1)(2p+1)}{6}}$$

1. Calculer $B_1$, $B_2$, $B_3$, $B_4$ et $B_5$, puis conjecturer une expression de $B_n$ valable pour tout entier $n⩾1$. On pourra faire apparaître le facteur $(-1{)}^n$. (0,5 point)

2. Dans cette question, $p$ désigne un entier. (1,75 point)

   a. Soit $p⩾1$. On regroupe les termes de $B_{2p}$ par paquets de deux, en réunissant les indices $2j-1$ et $2j$ pour $j$ allant de $1$ à $p$. Justifier que ce regroupement utilise chaque indice de $1$ à $2p$ une fois et une seule, puis écrire $B_{2p}$ comme une somme indexée par $j$, sans aucun point de suspension.

   b. En déduire que $B_{2p}=p(2p+1)$ pour tout entier $p⩾1$.

   c. Calculer $B_{2p+1}$ pour tout entier $p⩾0$, en traitant à part le cas $p=0$.

   d. En déduire une démonstration de la conjecture de la question 1, valable pour tout entier $n⩾1$.

3. On pose, pour tout entier $k⩾1$, $c_k=(-1{)}^{k-1}{\displaystyle \frac{k(k-1)}{2}}$. (1,25 point)

   a. Démontrer que, pour tout entier $k⩾1$, $c_{k+1}-c_k=(-1{)}^k{k}^2$.

   b. En déduire la valeur de $B_n$ par télescopage, pour tout entier $n⩾1$.

4. On pose (1 point)

   $$T_n=\sum _{i=1}^n\sum _{j=1}^n(-1{)}^{i+j}{i}^2{j}^2$$

   a. Soit $i\in \{1,\dots ,n\}$ fixé. Calculer la somme intérieure ${\displaystyle \sum _{j=1}^n(-1{)}^{i+j}{i}^2{j}^2}$ en fonction de $i$ et de $B_n$. On précisera quels facteurs sortent de la somme et pourquoi.

   b. En déduire $T_n$ en fonction de $n$.

Un logiciel d'archivage doit repérer par des entiers naturels des niveaux qui, dans la réalité, sont numérotés par des entiers relatifs : le rez-de-chaussée porte le numéro $0$, les étages les numéros $1$, $2$, $3$, et les sous-sols les numéros $-1$, $-2$, $-3$. On cherche donc une façon de faire correspondre à chaque entier naturel un entier relatif et un seul, sans en oublier aucun.

On considère pour cela l'application $f:\mathbb{N}\to \mathbb{Z}$ définie, pour tout entier naturel $n$, par

$$f(n)={\displaystyle \frac{n}{2}}\text{ si }n\text{ est pair},f(n)=-{\displaystyle \frac{n+1}{2}}\text{ si }n\text{ est impair}$$

Tout entier naturel étant pair ou impair, et jamais les deux, cette écriture définit bien une application de $\mathbb{N}$ dans $\mathbb{Z}$.

1. Recopier et compléter le tableau suivant. (0,25 point)

   $n$	$0$	$1$	$2$	$3$	$4$	$5$	$6$	$7$
   $f(n)$	?	?	?	?	?	?	?	?

2. Démontrer que, si $n$ est pair, alors $f(n)⩾0$, et que, si $n$ est impair, alors $f(n)⩽-1$. (0,5 point)

3. Démontrer que $f$ est injective. On commencera par établir, à l'aide de la question 2, que deux entiers ayant la même image ont nécessairement la même parité. (1 point)

4. Démontrer que $f$ est surjective. En déduire que $f$ est bijective, puis expliciter son application réciproque $f^{-1}:\mathbb{Z}\to \mathbb{N}$. (1 point)

5. On modifie un seul signe dans la définition, ce qui permet de prendre $\mathbb{N}$ comme ensemble d'arrivée : on considère l'application $g:\mathbb{N}\to \mathbb{N}$ définie par (0,5 point)

   $$g(n)={\displaystyle \frac{n}{2}}\text{ si }n\text{ est pair},g(n)={\displaystyle \frac{n+1}{2}}\text{ si }n\text{ est impair}$$

   L'application $g$ est-elle injective ? est-elle surjective ? Justifier chaque réponse.

Dans tout ce problème, pour tout entier $n⩾1$, on note

$$E_n=\{1,2,\dots ,n\}$$

l'ensemble des entiers compris entre $1$ et $n$. Les trois parties s'enchaînent : la partie A construit un outil, la partie B démontre un résultat à l'aide de cet outil, la partie C exploite ce résultat.

Partie A — Retirer une valeur à l'ensemble d'arrivée

Soient $n⩾1$ un entier et $b$ un élément de $E_{n+1}$. On définit l'application

$${\sigma }_b:E_{n+1}\setminus \{b\}\to E_n,{\sigma }_b(x)=x\text{ si }x<b,{\sigma }_b(x)=x-1\text{ si }x>b$$

où $E_{n+1}\setminus \{b\}$ désigne l'ensemble $E_{n+1}$ privé de l'élément $b$. Cette application « rebouche le trou » laissé par $b$ en décalant d'un cran tout ce qui se trouve au-dessus de lui.

1. Dans cette question uniquement, on prend $n=4$ et $b=2$. Écrire l'ensemble de départ de ${\sigma }_2$ en extension, puis dresser le tableau des valeurs de ${\sigma }_2$. (0,25 point)

2. Revenons au cas général. Démontrer que, pour tout $x\in E_{n+1}\setminus \{b\}$, on a bien ${\sigma }_b(x)\in E_n$, c'est-à-dire $1⩽{\sigma }_b(x)⩽n$. (0,5 point)

3. Démontrer que ${\sigma }_b$ est injective. On pourra commencer par établir que ${\sigma }_b(x)⩽b-1$ lorsque $x<b$, et ${\sigma }_b(x)⩾b$ lorsque $x>b$. (0,75 point)

Partie B — Le lemme fondamental

Pour tout entier $n⩾1$, on note ${\mathcal{L}}_n$ la proposition :

« il n'existe aucune application injective de $E_{n+1}$ dans $E_n$ ».

4. Démontrer que ${\mathcal{L}}_1$ est vraie. (0,5 point)

5. Soit $n⩾1$ un entier. On suppose ${\mathcal{L}}_n$ vraie et l'on veut en déduire ${\mathcal{L}}_{n+1}$. Pour cela, on raisonne par l'absurde : on suppose qu'il existe une application injective $f:E_{n+2}\to E_{n+1}$, et l'on pose $b=f(n+2)$.

   a. Démontrer que, pour tout $k\in E_{n+1}$, l'image $f(k)$ appartient à $E_{n+1}\setminus \{b\}$. (0,5 point)

   b. On définit l'application $g:E_{n+1}\to E_n$ par $g(k)={\sigma }_b(f(k))$ pour tout $k\in E_{n+1}$. Justifier que $g$ est bien définie, puis démontrer qu'elle est injective. (0,75 point)

   c. Conclure que ${\mathcal{L}}_{n+1}$ est vraie. (0,5 point)

6. Rédiger la conclusion du raisonnement par récurrence mené aux questions 4 et 5. (0,25 point)

Partie C — Exploitation

7. Soient $p$ et $q$ deux entiers tels que $1⩽p<q$. Démontrer qu'il n'existe aucune application injective de $E_q$ dans $E_p$. On pourra considérer la restriction à $E_{p+1}$ d'une telle application, c'est-à-dire l'application qui à tout $k\in E_{p+1}$ associe la même image que celle-ci. (0,75 point)

   Lecture concrète du résultat : si l'on range $q$ objets dans $p$ tiroirs et que $q>p$, alors deux objets au moins se retrouvent dans le même tiroir. C'est le principe dit « des tiroirs ».

8. Un service reçoit $40$ dossiers, et chaque dossier est affecté à l'un des $7$ jours de la semaine. Démontrer qu'il existe un jour auquel au moins $6$ dossiers sont affectés. (0,5 point)

   On remarquera que la question 7 ne suffit pas : elle donne seulement deux dossiers affectés au même jour. On raisonnera par l'absurde en majorant une somme.

9. Le théorème. Soit $n⩾1$ un entier et soit $f:E_n\to E_n$ une application injective. Démontrer que $f$ est surjective. (1,25 point)

   On traitera d'abord à part le cas $n=1$. Pour $n⩾2$, on raisonnera par l'absurde : si $f$ n'est pas surjective, il existe $c\in E_n$ qui n'a aucun antécédent, et l'on pourra alors reprendre, avec ${\sigma }_c$ à la place de ${\sigma }_b$, la construction de la question 5. b.

10. Le théorème de la question 9 cesse d'être vrai si l'on remplace $E_n$ par un ensemble infini. On considère l'application $s:\mathbb{N}\to \mathbb{N}$ définie par $s(k)=k+1$. (0,75 point)

    a. Démontrer que $s$ réalise une bijection de $\mathbb{N}$ sur $\mathbb{N}\setminus \{0\}$, et préciser sa réciproque. En déduire que $s$ est injective sans être surjective.

    b. En une phrase, dire quel maillon de la démonstration de la question 9 l'existence de cette bijection fait céder.