mathématiques (PTSI) · Chapitre 15 · Exercice de TD

Parties dont le cardinal est un multiple de trois

Dénombrement · C. Combinaisons et identités · niveau 3 (difficile)

É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é de la question 1

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.

Question 2 : comment l'IA t'aide

Élève

Pour le b), je développe les trois binômes, mais chaque développement contient tous les $(k n)$ , pour tous les $k$ . Je ne vois pas comment isoler ceux pour lesquels $3$ divise $k$ .

Les trois développements portent sur les mêmes $(k n)$ , avec des poids différents. Que devient le poids de $(k n)$ si tu combines les trois, et quel résultat du a) reconnais-tu alors ?

Élève

En les additionnant, $(k n)$ se retrouve multiplié par $1 + j^{k} + (j^{2})^{k}$ , c'est-à-dire par la quantité du a).

Exactement. Que vaut ce poids selon $k$ , et pourquoi la somme qui reste compte-t-elle bien les parties de $E$ dont le cardinal est un multiple de $3$ ?

L'IA ne donne pas la réponse : elle pose la question qui fait avancer. À toi de continuer.

Continue cet exercice avec l'IA

Reprends la question 2 là où le dialogue s'arrête, puis la suite de l'exercice.

Continuer avec l'IA — gratuit, sans inscription

Gratuit, sans inscription. L'IA te guide pas à pas, sans te donner la réponse.

Le cours du chapitre · Tous les exercices du chapitre

Continuer avec l'IA, gratuit →