Exo Maths X MP #34 - Coefficients binomiaux impairs

Exos Maths X MP

Published

Revised

December 22, 2020

9 months ago

Exercice d'oral de maths de Polytechnique filière MP tombé en 2020.

Soit $0 \leq e_{1} < . . . < e_{r}$ des entiers et $n = \sum_{i = 1}^{r} 2^{e_{i}}$ . Montrer que $Card {k \in [[0, n]] ∣ (k n) \equiv 1 [2]} = 2^{r}$ .

Merci au polytechnicien qui a souhaité rester anonyme d'avoir partagé l'exercice qu'il a eu à l'oral de l'X ! Pour partager les tiens, contacte Lucas Willems.

Correction

Bravo à Anas Orjy (MP*, Mohamed V) d'avoir réussi à résoudre cet exercice et merci à lui d'avoir rédigé une correction !

Rejoins le groupe Facebook Exos Maths X MP pour te préparer à l'X.

D'une part, si on note $E = {k \in [[0, n]] ∣ (k n) \equiv 1 [2]}$ :

(1 + X)^{n} \equiv k \in E \sum X^{k} [2]

et le nombre de monômes est égal à $Card (E)$ .

D'autre part, si $n = \sum_{i = 1}^{r} 2^{e_{i}}$ :

(1 + X)^{n} = i = 1 \prod r (1 + X)^{2^{e_{i}}}

On remarque que $(1 + X)^{2^{m}} \equiv 1 + X^{2^{m}} [2]$ pour tout $m \in N$ car par récurrence :

$(1 + X)^{2^{0}} \equiv 1 + X \equiv 1 + X^{2^{0}} [2]$ ,
$(1 + X)^{2^{n + 1}} \equiv ((1 + X)^{2^{n}})^{2} \equiv (1 + X^{2^{n}})^{2} \equiv 1 + X^{2^{n + 1}} [2]$

Donc :

(1 + X)^{n} \equiv i = 1 \prod r (1 + X^{2^{e_{i}}}) [2]

Si on note $F = {\sum_{c \in I} 2^{c} ∣ I \in P ({e_{1}, . . ., e_{r}})}$ :

(1 + X)^{n} \equiv k \in F \sum X^{k} [2]

On en déduit que $Card (E) = Card (F)$ . Or, $I \in P ({e_{1}, . . ., e_{r}}) ⟼ \sum_{c \in I} 2^{c}$ est injective par unicité de la décomposition en base 2. Donc :

Card (E) = Card (F) = Card (P ({e_{1}, . . ., e_{r}})) = 2^{r}

Exos Maths X MP

Prépare-toi aux oraux de maths de Polytechnique filière MP en résolvant les exercices tombés les années précédentes.