icone-challenge-math-OS

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}\]

et

    \[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 {\displaystyle 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