icone-challenge-math-OS

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 {\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
  •  
  •  
  •  
  •  
Fermer le menu