Solution pour le challenge n° 22

Notons, pour tout $n\in\mathbb{N}$ et pour tout ensemble $E$ de cardinal $n$ :

$A_{n}$ le nombre de parties de $E$ de cardinal congru à 0 modulo 3
$B_{n}$ le nombre de parties de $E$ de cardinal congru à 1 modulo 3
$C_{n}$ le nombre de parties de $E$ de cardinal congru à 2 modulo 3

Comme le nombre de parties de $E$ de cardinal $k$ est égal à $\binom{n}{k},$ alors :

$A_{n}=\binom{n}{0}+\binom{n}{3}+\binom{n}{6}+\cdots$

sachant que cette somme doit se poursuivre “tant que c’est possible”, ce qui veut dire qu’on ajoute les entiers $\displaystyle{\binom{n}{3k}}$ tant que $3k\leqslant n$ . Bref :

$\boxed{A_{n}=\sum_{k=0}^{\left\lfloor n/3\right\rfloor }\binom{n}{3k}}$

où le symbole $\left\lfloor x\right\rfloor$ désigne la partie entière par défaut du réel $x,$ c’est-à-dire le plus grand entier inférieur ou égal à $x$ . On voit de la même manière que :

$B_{n}=\sum_{k=0}^{\left\lfloor (n-1)/3\right\rfloor }\binom{n}{3k+1}\qquad\text{et}\qquad C_{n}=\sum_{k=0}^{\left\lfloor (n-2)/3\right\rfloor }\binom{n}{3k+2}$

Afin, de calculer explicitement $A_{n},$ voici un astuce géniale.

On va faire intervenir le nombre complexe :

$j=e^{\frac{2i\pi}{3}}=-\frac{1}{2}+i\frac{\sqrt{3}}{2}$

qui a le bon goût d’être une “racine cubique de l’unité” ce qui signifie simplement que $j^{3}=1.$

En effet, d’après la formule de Moivre :

$j^{3}=\left(e^{\frac{2i\pi}{3}}\right)^{3}=e^{2i\pi}=1$

En conséquence, la suite géométrique $\left(j^{n}\right)_{n\geqslant0}$ est périodique, de période $3,$ ce qui va s’avérer crucial pour la suite des opérations.

On observe en outre que :

$1+j+j^{2}=\frac{1-j^{3}}{1-j}=0\qquad\left(\spadesuit\right)$

Maintenant, appliquons la formule du binôme :

$\left(1+1\right)^{n}=\sum_{k=0}^{n}\binom{n}{k}=A_{n}+B_{n}+C_{n}\qquad\left(1\right)$

On a simplement séparé les $n+1$ termes qui composent cette somme en trois groupes : d’un côté les termes d’indice multiple de 3, d’un autre côté ceux dont l’indice est congru à 1 modulo 3 et, pour finir, ceux dont l’indice est congru à 2 modulo 3.

Compte tenu de ce qui a été dit au sujet du nombre complexe $j,$ on dispose de deux égalités supplémentaires :

$\left(1+j\right)^{n}=\sum_{k=0}^{n}\binom{n}{k}j^{k}=A^{n}+jB_{n}+j^{2}C_{n}\qquad\left(2\right)$

$\left(1+j^{2}\right)^{n}=\sum_{k=0}^{n}\binom{n}{k}j^{2k}=A_{n}+j^{2}B_{n}+jC_{n}\qquad\left(3\right)$

Si l’on ajoute membre à membre les relations (1), (2) et (3), tout en tenant compte de $\left(\spadesuit\right),$ il vient :

$2^{n}+\left(1+j\right)^{n}+\left(1+j^{2}\right)^{n}=3A_{n}$

Or, $j$ et $j^{2}$ sont conjugués et, par conséquent, $\left(1+j\right)^{n}$ et $\left(1+j^{2}\right)^{n}$ sont aussi conjugués.

Ceci conduit à :

$\boxed{A_{n}=\frac{1}{3}\left[2^{n}+2\thinspace\text{Re}\left(\left(1+j\right)^{n}\right)\right]}$

Voilà déjà une formule explicite pour $A_{n},$ mais elle est un peu “compliquée”. On sait bien que $A_{n}$ est un entier naturel et l’on préférerait disposer d’une formule plus simple.

Pour cela, on va tâcher de faire disparaître toute référence aux nombres complexes et à la trigonométrie…

On observe que, pour tout $n\in\mathbb{N}$ :

$\left(1+j\right)^{n}=\left(-j^{2}\right)^{n}=e^{in\pi/3}$

d’où, en passant aux parties réelles :

$\text{Re}\left(\left(1+j\right)^{n}\right)=\cos\left(\frac{n\pi}{3}\right)=\left\{ \begin{array}{cc}1 & \text{si }n\equiv0\pmod{6}\\\\\frac{1}{2} & \text{si }n\equiv1\pmod{6}\\\\-\frac{1}{2} & \text{si }n\equiv2\pmod{6}\\\\-1 & \text{si }n\equiv3\pmod{6}\\\\-\frac{1}{2} & \text{si }n\equiv4\pmod{6}\\\\\frac{1}{2} & \text{si }n\equiv5\pmod{6}\end{array}\right.$

Finalement :

$A_{n}=\left\{ \begin{array}{cc}\frac{1}{3}\left(2^{n}+2\right) & \text{si }n\equiv0\pmod{6}\\\\\frac{1}{3}\left(2^{n}+1\right) & \text{si }n\equiv1,5\pmod{6}\\\\\frac{1}{3}\left(2^{n}-1\right) & \text{si }n\equiv2,4\pmod{6}\\\\\frac{1}{3}\left(2^{n}-2\right) & \text{si }n\equiv3\pmod{6}\end{array}\right.$

Passons à l’examen de la parité de $A_{n}.$ Cette question ne semble pas facile d’accès avec la formule explicite obtenue ci-dessus.

Pourtant, en rédigeant un programme de calcul de $A_{n}$ (voir en annexe pour une version écrite en Python) et en observant la parité de $A_{n}$ pour de petites valeurs de $n,$ on découvre une apparente régularité :

$1,\:1,\:1,\:2,\:5,\:11,\:22,\:43,\:85,\:170,\:341,\:683,\:1\thinspace366,\:2\thinspace731,\:5\thinspace461,\:10\thinspace922,\:...$

Pour $0\leqslant n\leqslant15,$ , les $A_{n}$ pairs sont $A_{3,}$ $A_{6},$ $A_{9},$ $A_{12}$ et $A_{15}.$

On conjecture donc naturellement que, pour tout $n\geqslant3$ :

$A_{n}\text{ est pair}\Leftrightarrow3\mid n$

ce qu’on va maintenant établir rigoureusement.

Pour cela, on va faire un petit raisonnement combinatoire.

Considérons un ensemble $E$ de cardinal $n+1$ et nommons $\alpha$ un élément particulier. Les parties de $E$ dont le cardinal est multiple de $3$ sont :

les parties de $E-\left\{ \alpha\right\}$ de cardinal multiple de $3,$
les unions du singleton $\left\{ \alpha\right\}$ avec une partie de $E-\left\{ \alpha\right\}$ de cardinal congru à 2 modulo 3

Par conséquent :

$A_{n+1}=A_{n}+C_{n}\qquad\left(\star\right)$

Considérons maintenant un ensemble de cardinal $n+2$ et nommons $\alpha,\beta$ deux éléments particuliers. Les parties de $E$ dont le cardinal est multiple de 3 sont :

les parties de $E-\left\{ \alpha,\beta\right\}$ de cardinal multiple de $3,$
les unions de l’un des deux singletons $\left\{ \alpha\right\}$ ou $\left\{ \beta\right\}$ avec une partie de $E-\left\{ \alpha,\beta\right\}$ de cardinal congru à 2 modulo 3
les unions de la paire $\left\{ \alpha,\beta\right\}$ avec une partie de $E-\left\{ \alpha,\beta\right\}$ de cardinal congru à 1 modulo 3

Par conséquent :

$A_{n+2}=A_{n}+2C_{n}+B_{n}\qquad\left(\star\star\right)$

Considérons enfin un ensemble de cardinal $n+3$ et nommons $\alpha,\beta,\gamma$ trois éléments particuliers. Les parties de $E$ dont le cardinal est multiple de 3 sont :

les parties de $E-\left\{ \alpha,\beta,\gamma\right\}$ de cardinal multiple de $3,$
les unions de l’un des trois singletons $\left\{ \alpha\right\} ,$ $\left\{ \beta\right\}$ ou $\left\{ \gamma\right\}$ avec une partie de $E-\left\{ \alpha,\beta,\gamma\right\}$ de cardinal congru à 2 modulo 3
les unions de l’une des trois paires $\left\{ \alpha,\beta\right\} ,$ $\left\{ \alpha,\gamma\right\}$ ou $\left\{ \beta,\gamma\right\}$ avec une partie de $E-\left\{ \alpha,\beta,\gamma\right\}$ de cardinal congru à 1 modulo 3
l’union de $\left\{ \alpha,\beta,\gamma\right\}$ avec une partie de $E-\left\{ \alpha,\beta,\gamma\right\}$ de cardinal multiple de 3

Par conséquent :

$A_{n+3}=2A_{n}+3C_{n}+3B_{n}\qquad\left(\star\star\star\right)$

En combinant $\left(\star\right),$ $\left(\star\star\right)$ et $\left(\star\star\star\right),$ on obtient la relation de récurrence linéaire d’ordre 3 suivante :

$\boxed{A_{n+3}=3A_{n+2}-3A_{n+1}+2A_{n}}$

Notons désormais : $q_{n}=A_{n}\mod2$ (c’est le reste de la division de $A_{n}$ par 2 : cet entier vaut 0 si $A_{n}$ est pair et 1 sinon). Alors, pour tout $n\in\mathbb{N}$ (en réduisant modulo 2 l’égalité précédente) :

$q_{n+3}=\left(q_{n+2}+q_{n+1}\right)\mod2$

Comme $\left(q_{0},q_{1},q_{2}\right)=\left(1,1,1\right),$ on voit que les premiers termes de la suite $\left(q_{n}\right)_{n\in\mathbb{N}}$ sont :

$1,\:1,\:1,\:0,\:1,\:1,\:0,\:1,\:1,\:0,\:1,\:1,\:0,\:1,\:1,\:0,...$

On peut aisément montrer par récurrence que, pour tout $k\in\mathbb{N}^{\star}$ :

$q_{3k}=0,\quad q_{3k+1}=q_{3k+2}=1$

ce qui permet de conclure.

Annexe : programmation en Python

Calcul des coefficients binomiaux (solution récursive, utilisant la formule du pion)

def binomial(n,k):
  if k == 0:
    return 1
  elif 2 * k > n:
    return binomial(n, n-k)
  else:
    return (n * binomial(n-1,k-1)) // k

Calcul de la somme $A_{n}=\sum_{k=0}^{\left\lfloor n/3\right\rfloor }\binom{n}{3k}$

def A(n):
  s = 0
  k = 0
  while k <= n:
    s += binomial(n, k)
    k += 3
  return s

Pour consulter l’énoncé, c’est ici

Partager cet article

Remplissez ce formulaire et recevez GRATUITEMENT le Bonus TS+ :
30 exercices de mathématiques entièrement corrigés, regroupés dans un document PDF de grande qualité.
Fin de terminale S / Début d'enseignement supérieur

Annexe : programmation en Python

Remplissez ce formulaire et recevez GRATUITEMENT le Bonus TS+ :
30 exercices de mathématiques entièrement corrigés, regroupés dans un document PDF de grande qualité.
Fin de terminale S / Début d'enseignement supérieur

Votre adresse email ne sera jamais cédée ni revendue. En vous inscrivant ici, vous recevrez des articles, vidéos, offres (commerciales ou non) de formations et autres conseils pour vous aider à progresser en mathématiques.

Vous pouvez vous désabonner à tout instant.

Annexe : programmation en Python

Remplissez ce formulaire et recevez GRATUITEMENT le Bonus TS+ :30 exercices ​de mathématiques entièrement corrigés, regroupés dans un document PDF de grande qualité.Fin de terminale S / Début d'enseignement supérieur

Votre adresse email ne sera jamais cédée ni revendue. En vous inscrivant ici, vous recevrez des articles, vidéos, offres (commerciales ou non) de formations et autres conseils pour vous aider à progresser en mathématiques.

Vous pouvez vous désabonner à tout instant.

Remplissez ce formulaire et recevez GRATUITEMENT le Bonus TS+ :
30 exercices de mathématiques entièrement corrigés, regroupés dans un document PDF de grande qualité.
Fin de terminale S / Début d'enseignement supérieur