Parties dont le cardinal est un multiple de trois

Exercice de TD · niveau 3 (difficile) · mathématiques (PCSI), chapitre 14 — Dénombrement · C. Combinaisons et identités

Énoncé

Soit $E$ un ensemble à $n \geq 1$ éléments et $j = e^{2 iπ /3}$ .

a) Pour $k \in N$ , calculer $1 + j^{k} + j^{2 k}$ selon le reste de la division euclidienne de $k$ par $3$ .

b) En appliquant la formule du binôme à $(1 + 1)^{n}$ , $(1 + j)^{n}$ et $(1 + j^{2})^{n}$ , montrer que le nombre $A_{n}$ de parties de $E$ dont le cardinal est un multiple de $3$ vérifie $3 A_{n} = 2^{n} + (1 + j)^{n} + (1 + j^{2})^{n} .$

c) Écrire $1 + j$ et $1 + j^{2}$ sous forme exponentielle, et en déduire $A_{n} = \frac{2 ^{n} + 2 cos ( \frac{nπ}{3} )}{3}$ . Vérifier pour $n = 3$ , $4$ et $6$ en dénombrant directement.

d) Retrouver par la même méthode, avec les racines carrées de l'unité $1$ et $- 1$ , le nombre de parties de $E$ de cardinal pair.

Corrigé

La stratégie. Filtrer une somme par les racines de l'unité. La formule du binôme donne toutes les parties à la fois, pondérées par une puissance ; en moyennant sur les trois racines cubiques de l'unité, on fabrique un poids qui vaut $1$ sur les cardinaux multiples de $3$ et $0$ sur les autres.

a) Le filtre. Écrivons $k = 3 q + r$ avec $r \in {0, 1, 2}$ . Comme $j^{3} = 1$ , $j^{k} = j^{r}$ et $j^{2 k} = j^{2 r}$ : la quantité ne dépend que du reste $r$ . Si $r = 0$ , elle vaut $1 + 1 + 1 = 3$ . Si $r = 1$ , elle vaut $1 + j + j^{2} = 0$ , somme des racines cubiques de l'unité. Si $r = 2$ , elle vaut $1 + j^{2} + j^{4} = 1 + j^{2} + j = 0$ . Donc $1 + j^{k} + j^{2 k}$ vaut $3$ si $3$ divise $k$ , et $0$ sinon.

b) Le binôme, trois fois. En classant les parties de $E$ selon leur cardinal, $A_{n} = \sum (k n)$ , la somme portant sur les $k$ multiples de $3$ compris entre $0$ et $n$ . Or, par la formule du binôme, et puisque $(j^{2})^{k} = j^{2 k}$ , $(1 + 1)^{n} + (1 + j)^{n} + (1 + j^{2})^{n} = k = 0 \sum n (k n) (1 + j^{k} + j^{2 k}) = 3 3 divise k \sum (k n) = 3 A_{n},$ par le a) : le filtre garde exactement les termes voulus, chacun trois fois.

c) La forme exponentielle. $1 + j = 1 - \frac{1}{2} + i \frac{3}{2} = \frac{1}{2} + i \frac{3}{2} = e^{iπ /3}$ , et $j^{2} = j$ puisque $∣ j ∣ = 1$ , donc $1 + j^{2} = 1 + j = e^{- iπ /3}$ . Ainsi $(1 + j)^{n} + (1 + j^{2})^{n} = e^{inπ /3} + e^{- inπ /3} = 2 cos (\frac{nπ}{3}),$ et par le b), $A_{n} = \frac{2 ^{n} + 2 cos ( \frac{nπ}{3} )}{3} .$ Contrôles. $n = 3$ : les parties de cardinal $0$ ou $3$ sont au nombre de $1 + 1 = 2$ , et la formule donne $\frac{8 - 2}{3} = 2$ . $n = 4$ : cardinal $0$ ou $3$ , $1 + 4 = 5$ , et $\frac{16 - 1}{3} = 5$ . $n = 6$ : cardinal $0$ , $3$ ou $6$ , $1 + 20 + 1 = 22$ , et $\frac{64 + 2}{3} = 22$ . Le terme correctif $\frac{2 c o s ( nπ /3 )}{3}$ est au plus $\frac{2}{3}$ en valeur absolue : à une unité près, un tiers des parties.

d) La parité. Les racines carrées de l'unité sont $1$ et $- 1$ , et $1 + (- 1)^{k}$ vaut $2$ si $k$ est pair, $0$ sinon. Le binôme donne $(1 + 1)^{n} + (1 - 1)^{n} = \sum_{k} (k n) (1 + (- 1)^{k}) = 2 P_{n}$ , où $P_{n}$ est le nombre de parties de cardinal pair ; comme $n \geq 1$ , $(1 - 1)^{n} = 0$ , et $P_{n} = 2^{n - 1}$ : autant de parties de cardinal pair que de cardinal impair.

Le point délicat. Le filtre marche parce que la somme des racines $m$ -ièmes de l'unité est nulle, et que $j^{k}$ ne dépend que du reste de la division de $k$ par $3$ . Avec les racines quatrièmes $1, i, - 1, - i$ , on compterait de même les parties de cardinal multiple de $4$ .

Ce que l'exercice installe. Filtrer une somme par les racines de l'unité : moyenner sur les racines $m$ -ièmes ne garde que les termes d'indice multiple de $m$ . Au chapitre 15, le même filtre, avec $1$ et $- 1$ , donnera la probabilité qu'une variable de loi binomiale $B (n, t)$ soit paire : $\frac{1 + ( 1 - 2 t ) ^{n}}{2}$ , en développant $((1 - t) + t)^{n} + ((1 - t) - t)^{n}$ .

Les autres exercices de ce chapitre Le cours du chapitre

Un blocage sur cet exercice ? Le tuteur d'Adloun guide par questions, sans donner la réponse.