Exercice national 2 — Nous sommes toutes distinctes (spécialité maths)

1. Nombre de parties non vides d'un ensemble à \(n\) éléments : \(2^n-1\) (total des parties \(2^n\), moins la partie vide).

3. Si \(0\in A\) et \(A\) a au moins un autre élément \(a\), comparer la somme \(\{a\}\) et \(\{0,a\}\) : elles sont égales, donc \(A\) n'est jamais STD sauf si \(A=\{0\}\).

5. Une somme d'entiers est toujours entière ; ajouter \(\frac12\) (non entier) à une somme d'entiers de \(A\) donne un résultat qui ne peut coïncider avec aucune somme purement entière (partie décimale différente) — argumenter de même pour \(\sqrt2\) (irrationnel), qui ne peut apparaître dans aucune combinaison purement rationnelle.

9-10. Comme \(u_{n+1}=S_n+1\) où \(S_n=u_1+\cdots+u_n\), toute somme partielle de \(\{u_1,\ldots,u_{n+1}\}\) impliquant \(u_{n+1}\) dépasse strictement toute somme n'impliquant que \(u_1,\ldots,u_n\) : cela garantit le caractère STD par récurrence. Pour la question 10, calculer \(u_{n+1}-2u_n\) à l'aide de la relation de récurrence.

12a. \(E(X_1)=\frac12\times1+\frac12\times(-1)=0\) ; \(V(X_1)=E(X_1^2)-E(X_1)^2=1-0=1\).

12b. \(X\) est une somme signée des \(u_i\) : ses valeurs possibles sont exactement les \(2^n\) sommes \(\pm u_1\pm u_2\pm\cdots\pm u_n\), toutes distinctes par caractère STD de \((u_i)\), symétriques par le changement de signe global, non nulles (car \(0\) ne peut s'écrire comme somme signée non triviale d'un ensemble STD), et de même parité (la parité de \(X\) ne dépend que de la parité de la somme \(u_1+\cdots+u_n\), fixée).

Partie 1

1. Pourquoi \(2^n-1\) sommes ?

Un ensemble \(A\) de cardinal \(n\) possède \(2^n\) parties (y compris la partie vide). Les parties non vides sont donc au nombre de \(2^n - 1\). Chaque partie non vide donne une somme de ses éléments. Le nombre total de ces sommes est donc \(2^n - 1\).

2. \(\{1,3,5\}\) STD ? \(\{4,6,7,9\}\) ?

• Pour \(A = \{1,3,5\}\) : les parties non vides sont :

• \(\{1\}\) : somme \(1\)

• \(\{3\}\) : somme \(3\)

• \(\{5\}\) : somme \(5\)

• \(\{1,3\}\) : somme \(4\)

• \(\{1,5\}\) : somme \(6\)

• \(\{3,5\}\) : somme \(8\)

• \(\{1,3,5\}\) : somme \(9\)

Toutes ces sommes sont distinctes. Donc \(\{1,3,5\}\) est STD.

• Pour \(A = \{4,6,7,9\}\) : les parties non vides sont :

• \(\{4\}\) : \(4\)

• \(\{6\}\) : \(6\)

• \(\{7\}\) : \(7\)

• \(\{9\}\) : \(9\)

• \(\{4,6\}\) : \(10\)

• \(\{4,7\}\) : \(11\)

• \(\{4,9\}\) : \(13\)

• \(\{6,7\}\) : \(13\) (déjà obtenu avec \(\{4,9\}\))

Donc deux sommes sont égales (13). L'ensemble n'est pas STD.

3. Quels ensembles contenant 0 sont STD ?

Soit \(A\) un ensemble contenant \(0\). Alors pour toute partie non vide \(P\) de \(A\), la somme des éléments de \(P\) est égale à la somme des éléments de \(P \setminus \{0\}\) (si \(0 \in P\)). Donc si \(P\) et \(Q\) sont deux parties non vides distinctes telles que \(P \setminus \{0\} = Q \setminus \{0\}\), alors leurs sommes sont égales. Pour éviter cela, il faut que \(0\) soit le seul élément de \(A\) (car sinon, prenons \(P = \{0, a\}\) et \(Q = \{a\}\) avec \(a \neq 0\), on a somme \(a\) pour les deux). Donc les seuls ensembles STD contenant \(0\) sont \(\{0\}\) et éventuellement l'ensemble vide (mais ici on parle d'ensembles finis non vides ? L'énoncé dit "ensembles contenant 0", donc \(\{0\}\) est le seul.

4. Si \(A \subset B\) et \(B\) STD, \(A\) l'est-il ? Réciproque ?

• Si \(B\) est STD, alors toutes les sommes de parties non vides de \(B\) sont distinctes. En particulier, les sommes des parties non vides de \(A\) (qui sont aussi des parties de \(B\)) sont distinctes. Donc \(A\) est STD.

• La réciproque est fausse : par exemple, \(A = \{1,2,5\}\) est STD (donné dans l'énoncé), mais \(B = \{1,2,5,8\}\) peut ne pas l'être (vérifions : \(\{1,8\}=9\), \(\{2,5\}=7\), \(\{1,2,5\}=8\), \(\{8\}=8\) donc conflit). Donc \(A\) STD n'implique pas \(B\) STD.

5. Si \(A\) STD (entiers), montrer que \(A \cup \{\frac12\}\) puis \(A \cup \{\frac12, \sqrt2\}\) le sont aussi.

• Soit \(A\) un ensemble d'entiers STD. Considérons \(B = A \cup \{\frac12\}\). Les sommes des parties non vides de \(B\) sont de deux types :

• celles qui ne contiennent pas \(\frac12\) : ce sont les sommes des parties non vides de \(A\), toutes distinctes.

• celles qui contiennent \(\frac12\) : elles sont de la forme \(\frac12 + s\) où \(s\) est une somme d'une partie (éventuellement vide) de \(A\). Si \(s\) est la somme de la partie vide, on obtient \(\frac12\). Sinon, \(s\) est une somme d'une partie non vide de \(A\).

Supposons qu'une somme du premier type soit égale à une somme du second type : alors \(s_1 = \frac12 + s_2\) avec \(s_1, s_2\) sommes de parties de \(A\). Comme \(s_1, s_2\) sont des entiers, \(\frac12\) ne peut pas être égal à une différence d'entiers. Donc pas de conflit entre les deux types.

Supposons deux sommes du second type égales : \(\frac12 + s = \frac12 + t\) implique \(s = t\), donc les parties de \(A\) correspondantes sont identiques (car \(A\) STD). Donc toutes les sommes sont distinctes. Ainsi \(B\) est STD.

• Pour \(C = A \cup \{\frac12, \sqrt2\}\), on raisonne de même. Les sommes sont de quatre types :

1. sans \(\frac12\) ni \(\sqrt2\) : sommes de \(A\).

2. avec \(\frac12\) seulement : \(\frac12 + s\).

3. avec \(\sqrt2\) seulement : \(\sqrt2 + s\).

4. avec les deux : \(\frac12 + \sqrt2 + s\).

Les nombres des types 1 sont entiers. Ceux des types 2 sont de la forme \(\frac12 + \text{entier}\), donc demi-entiers non entiers. Ceux des types 3 sont de la forme \(\sqrt2 + \text{entier}\), irrationnels. Ceux des types 4 sont de la forme \(\frac12 + \sqrt2 + \text{entier}\), irrationnels. Aucune égalité possible entre types différents car les parties fractionnaires ou irrationnelles diffèrent. À l'intérieur d'un même type, l'égalité implique l'égalité des sommes de \(A\) correspondantes, donc des parties identiques. Donc \(C\) est STD.

Partie 2

6. Vérifier \(u_2=2, u_3=4\), calculer \(u_5\).

On a \(u_1 = 1\) et \(u_{n+1} = u_1 + u_2 + \dots + u_n + 1\).

• Pour \(n=1\) : \(u_2 = u_1 + 1 = 1 + 1 = 2\).

• Pour \(n=2\) : \(u_3 = u_1 + u_2 + 1 = 1 + 2 + 1 = 4\).

• Pour \(n=3\) : \(u_4 = u_1 + u_2 + u_3 + 1 = 1 + 2 + 4 + 1 = 8\).

• Pour \(n=4\) : \(u_5 = u_1 + u_2 + u_3 + u_4 + 1 = 1 + 2 + 4 + 8 + 1 = 16\).

Donc \(u_5 = 16\).

7. Programme Python pour \(u_{100}\).

```python

def u_n(n):

u = [0] * (n+1) # indexation à partir de 1

u[1] = 1

somme = 1 # somme des termes précédents

for i in range(2, n+1):

u[i] = somme + 1

somme += u[i]

return u[n]

print(u_n(100))

```

8. Sens de variation.

Montrons que \((u_n)\) est strictement croissante. Pour tout \(n \ge 1\), \(u_{n+1} = u_1 + \dots + u_n + 1 > u_n\) car \(u_1 + \dots + u_{n-1} + 1 \ge 1\) (et même strictement positif). Donc \(u_{n+1} > u_n\). La suite est strictement croissante.

9. Montrer que \(\{u_1, \dots, u_n\}\) est STD.

Montrons par récurrence que pour tout \(n\), l'ensemble \(U_n = \{u_1, \dots, u_n\}\) est STD.

• Initialisation : \(n=1\), \(U_1 = \{1\}\), une seule somme non vide : 1, donc STD.

• Hérédité : supposons \(U_n\) STD. Considérons \(U_{n+1} = U_n \cup \{u_{n+1}\}\). Les sommes des parties non vides de \(U_{n+1}\) sont :

• celles qui ne contiennent pas \(u_{n+1}\) : ce sont les sommes de \(U_n\), toutes distinctes par hypothèse.

• celles qui contiennent \(u_{n+1}\) : elles sont de la forme \(u_{n+1} + s\) où \(s\) est une somme d'une partie (éventuellement vide) de \(U_n\). La plus petite de ces sommes est \(u_{n+1}\) (pour \(s=0\)), et la plus grande est \(u_{n+1} + (u_1+\dots+u_n) = u_{n+1} + (u_{n+1}-1) = 2u_{n+1}-1\).

Or, la plus grande somme sans \(u_{n+1}\) est \(u_1+\dots+u_n = u_{n+1}-1\). Donc toutes les sommes avec \(u_{n+1}\) sont \(\ge u_{n+1}\), tandis que toutes les sommes sans \(u_{n+1}\) sont \(\le u_{n+1}-1\). Il n'y a donc pas de conflit entre les deux groupes. De plus, à l'intérieur du groupe avec \(u_{n+1}\), si \(u_{n+1}+s = u_{n+1}+t\) alors \(s=t\), donc les parties de \(U_n\) sont identiques. Donc \(U_{n+1}\) est STD.

10. Montrer que \((u_n)\) est géométrique (raison à déterminer).

On a \(u_{n+1} = u_1 + \dots + u_n + 1\). Pour \(n \ge 2\), on a aussi \(u_n = u_1 + \dots + u_{n-1} + 1\). En soustrayant :

\[u_{n+1} - u_n = u_n \quad \text{donc} \quad u_{n+1} = 2u_n.\]

Pour \(n=1\), on vérifie : \(u_2 = 2 = 2 \times 1\). Donc pour tout \(n \ge 1\), \(u_{n+1} = 2 u_n\). La suite est géométrique de raison 2, avec \(u_1 = 1\), donc \(u_n = 2^{n-1}\).

Partie 3

11a. Montrer \(u_1 + \dots + u_n \ge 2^n - 1\).

Soit \((u_n)\) une suite STD (strictement croissante, entiers positifs, et \(\{u_1,\dots,u_n\}\) STD pour tout \(n\)). Les sommes des parties non vides de \(\{u_1,\dots,u_n\}\) sont toutes distinctes et sont au nombre de \(2^n - 1\). La plus petite somme possible est \(u_1\) (car les \(u_i\) sont positifs et strictement croissants, donc \(u_1\) est le plus petit élément). La plus grande somme est \(u_1 + \dots + u_n\). Comme les sommes sont des entiers distincts, elles sont au moins égales à \(1, 2, 3, \dots, 2^n - 1\) (dans le meilleur des cas, les plus petites possibles). Donc la plus grande somme, qui est \(u_1 + \dots + u_n\), est au moins \(2^n - 1\). Ainsi :

\[u_1 + \dots + u_n \ge 2^n - 1.\]

11b. En déduire \(u_n \ge \frac{2^n}{n}\) (pour \(n\ge2\)).

Le bornage grossier \(u_1+\cdots+u_n\le nu_n\) ne donne que \(u_n\ge\frac{2^n-1}n\), un peu trop faible. Comme les \(u_i\) sont des entiers strictement croissants, on a plus précisément \(u_n\ge u_{n-1}+1\ge u_{n-2}+2\ge\cdots\ge u_i+(n-i)\), donc \(u_i\le u_n-(n-i)\) pour chaque \(i\). En sommant :

\[u_1+\cdots+u_n\le nu_n-\sum_{i=1}^n(n-i)=nu_n-\frac{n(n-1)}2.\]

Combiné à la question 11a (\(u_1+\cdots+u_n\ge2^n-1\)) :

\[nu_n\ge2^n-1+\frac{n(n-1)}2\quad\Longrightarrow\quad u_n\ge\frac{2^n}n+\left(\frac{n-1}2-\frac1n\right).\]

Or \(\frac{n-1}2-\frac1n\ge0\iff n(n-1)\ge2\), ce qui est vrai pour tout \(n\ge2\) (égalité exactement à \(n=2\)). Donc pour \(n\ge2\), \(u_n\ge\frac{2^n}n\).

12. Affiner via les probabilités : \(X = u_1 X_1 + \dots + u_n X_n\) (\(X_i\) uniformes sur \(\{-1,1\}\)).

a) Calculer \(E(X)\), exprimer \(V(X)\).

Les \(X_i\) sont indépendants et uniformes sur \(\{-1,1\}\). Donc \(E(X_i) = 0\) pour tout \(i\). Par linéarité :

\[E(X) = \sum_{i=1}^n u_i E(X_i) = 0.\]

La variance : \(V(X) = E(X^2) - (E(X))^2 = E(X^2)\). Comme les \(X_i\) sont indépendants et de variance \(V(X_i) = E(X_i^2) - (E(X_i))^2 = 1 - 0 = 1\), on a :

\[V(X) = \sum_{i=1}^n u_i^2 V(X_i) = \sum_{i=1}^n u_i^2.\]

b) Montrer que \(X\) suit une loi uniforme sur \(2^n\) entiers relatifs symétriques, non nuls, de même parité.

Les valeurs possibles de \(X\) sont les \(2^n\) sommes \(\sum_{i=1}^n \epsilon_i u_i\) avec \(\epsilon_i \in \{-1,1\}\), équiprobables. Elles sont toutes distinctes : si deux choix de signes différents donnaient la même valeur, en regroupant les indices où les signes diffèrent on obtiendrait deux sommes distinctes de parties (disjointes) de \(\{u_1,\ldots,u_n\}\) égales entre elles (après avoir déplacé les termes de signe négatif de l'autre côté), contredisant le caractère STD. Elles sont symétriques (changer tous les signes change \(X\) en \(-X\)), non nulles (si \(X=0\), les indices à \(+1\) et à \(-1\) formeraient deux parties disjointes non vides de même somme, contredisant STD — sauf partition triviale, exclue car \(\epsilon_i\ne0\)), et de même parité (chaque \(u_i\) est entier, donc \(X\) et \(u_1+\cdots+u_n\) ont toujours la même parité, quels que soient les signes).

c) En déduire \(u_n^2 \ge \frac{1}{n 2^{n-1}} (1^2 + 3^2 + \dots + (2^n-1)^2)\).

Les \(2^{n-1}\) valeurs strictement positives de \(X\) sont des entiers distincts de même parité : rangées en ordre croissant \(a_1

\[u_n^2\ge\frac1{n2^{n-1}}(1^2+3^2+\cdots+(2^n-1)^2).\]

d) Proposer un \(n \ge 2\) où cette minoration bat celle de 11b.

Notons \(S(m)=1^2+3^2+\cdots+(2m-1)^2\) (somme de \(m\) carrés impairs). La minoration de 12c s'écrit \(u_n\ge\sqrt{S(2^{n-1})/(n2^{n-1})}\), à comparer à celle de 11b, \(u_n\ge2^n/n\). Calculons pour les petites valeurs de \(n\) (avec \(S(2^{n-1})\), donc \(2^{n-1}\) termes) :

• \(n=2\) : \(S(2)=1^2+3^2=10\), 12c donne \(u_2\ge\sqrt{10/4}\approx1{,}58\) contre 11b \(u_2\ge2\) : 11b meilleur.

• \(n=3\) : \(S(4)=1+9+25+49=84\), 12c donne \(u_3\ge\sqrt{84/12}\approx2{,}65\) contre 11b \(u_3\ge8/3\approx2{,}67\) : 11b encore (très légèrement) meilleur.

• \(n=4\) : \(S(8)=1+9+25+49+81+121+169+225=680\), 12c donne \(u_4^2\ge680/(4\times8)=85/4=21{,}25\), soit \(u_4\ge\sqrt{85}/2\approx4{,}61\), contre 11b \(u_4\ge2^4/4=4\) : 12c est ici strictement meilleur que 11b !

Donc \(n=4\) convient (et plus généralement tout \(n\ge4\), l'écart en faveur de 12c ne faisant que croître).