Solution pour le challenge n° 22

Solution pour le challenge 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 $\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}$

$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 fait 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 :
$\displaystyle{1+j+j^{2}=\frac{1-j^{3}}{1-j}=0\quad\left(\spadesuit\right)}$
Maintenant, appliquons la formule du binôme :

$\begin{eqnarray*}& &\left(1+1\right)^{n}\\&=&\sum_{k=0}^{n}\binom{n}{k}\\&=&A_{n}+B_{n}+C_{n}\end{eqnarray*}$

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 :

$\begin{eqnarray*}& &\left(1+j\right)^{n}\\&=&\sum_{k=0}^{n}\binom{n}{k}j^{k}\\&=&A_{n}+jB_{n}+j^{2}C_{n}\end{eqnarray*}$

$\begin{eqnarray*}& &\left(1+j^{2}\right)^{n}\\&=&\sum_{k=0}^{n}\binom{n}{k}j^{2k}\\&=&A_{n}+j^{2}B_{n}+jC_{n}\end{eqnarray*}$

Nous disposons donc des trois relations suivantes :
$\displaystyle{2^n=A_n+B_n+C_n}$
$\displaystyle{\left(1+j)^n=A_n+jB_n+j^2C_n}$
$\displaystyle{\left(1+j^2)^n=A_n+j^2B_n+jC_n}$

En les ajoutant membre à membre, et en tenant compte de $\left(\spadesuit\right),$ il vient :

$\displaystyle{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{\displaystyle{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)$

c’est-à-dire :
$\displaystyle{\text{Re}\left(\left(1+j\right)^{n}\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 :

$\boxed{\displaystyle{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, 1366, 2731, 5461, 10922, …

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

On est donc naturellement conduit à la …

Conjecture

Pour tout entier $n\geqslant3$ :

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

ce qu’on va maintenant tâcher d’é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 de $E$ . 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\}$ et d’une partie de $E-\left\{ \alpha\right\}$ de cardinal congru à 2 modulo 3

Par conséquent :
$\boxed{A_{n+1}=A_{n}+C_{n}\quad\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\}$ et d’une partie de $E-\left\{ \alpha,\beta\right\}$ de cardinal congru à 2 modulo 3
les unions de la paire $\left\{ \alpha,\beta\right\}$ et d’une partie de $E-\left\{ \alpha,\beta\right\}$ de cardinal congru à 1 modulo 3

Par conséquent :
$\boxed{A_{n+2}=A_{n}+2C_{n}+B_{n}\quad\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\}$ et d’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\}$ et d’une partie de $E-\left\{ \alpha,\beta,\gamma\right\}$ de cardinal congru à 1 modulo 3
l’union de $\left\{ \alpha,\beta,\gamma\right\}$ et d’une partie de $E-\left\{ \alpha,\beta,\gamma\right\}$ de cardinal multiple de 3

Par conséquent :
$\boxed{A_{n+3}=2A_{n}+3C_{n}+3B_{n}\quad\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}\,\text{mod}\,2$

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)\,\text{mod}\,2$

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