Formule de Cayley

Exercice

La formule de Cayley affirme que pour $n \gt 1$, le nombre $C_n$ d’arbres qu’on peut construire sur $n$ sommets est $n^{n-2}$.

Le matrix tree theorem ou théorème de Kirchhoff, déjà présenté en exercice, nous permet de calculer directement cette valeur.

$1)$ Prouver la formule de Cayley à l’aide du Matrix Tree Theorem.

Une autre preuve, due à Jim Pitman, consiste en une preuve par double dénombrement.

On cherche à dénombre de deux façons différentes le nombre $D_n$ de façon d’ajouter consécutivement $n-1$ arêtes orientées au graphe nul à $n$ sommets : le graphe $G_n$ à $n$ sommets sans arêtes.

On commence par un dénombrement à partir d’arbres orientés.

$2)$ À partir d’un arbre non orienté sur $n$ sommets, expliquer comment obtenir un arbre orienté.

$3)$ En déduire une méthode en partant d’un arbre non orienté pour trouver plusieurs manières d’ajouter $n-1$ arêtes orientées à $G_n$.

$4)$ Montrer qu’utiliser cette méthode à partir de tous les arbres non orientés permet d’obtenir chaque construction possible une et une seule fois.

$5)$ Exprimer $D_n$ en fonction de $C_n$ et $n$.

On effectue maintenant un comptage directe.

$6)$ Combien compte-t-on de composante connexes après avoir ajouté $k \lt n$ arêtes à $G_n$ ?

$7)$ Après avoir ajouté $k \lt n-1 $ arêtes à $G_n$, combien de possibilité reste-t-il pour placer la prochaine ?

$8)$ En déduire une expression de $D_n$ ne dépendant que de $n$.

$9)$ Calculer $C_n$.

Correction

$1.$ Le nombre d’arbres non-orientés pouvant être construits sur $n$ sommets correspond au nombre d’arbre couvrant du graphe complet à $n$ sommets. Soit $L$ la matrice de dimension $n-1 \times n-1$ avec des $n-1$ sur la diagonale, et des $-1$ partout ailleurs. On a donc par le théorème de Kirchhoff :

\[C_n = \det\left(L\right)\]

\[C_n = \begin{vmatrix} n-1 & -1 & -1 & \cdots & -1 \\ -1 & n-1 & -1 & \cdots & -1 \\ \vdots & -1 & -1 & n-1 & \dots & -1\\ \vdots & \ddots & \ddots & \vdots \\ -1 & -1 & -1 & \cdots & n-1\end{vmatrix}\]

On soustrait à chaque colonne autre que la première la première colonne :

\[C_n = \begin{vmatrix} n-1 & -n & -n & \cdots & -n \\ -1 & n & 0 & \cdots & 0\\ -1 & 0 & n & \ldots & 0 \\ \vdots & \vdots & \ddots & \ddots & \vdots \\ -1 & 0 & 0 & \cdots & n\end{vmatrix}\]

On ajoute maintenant à la première ligne les $n-2$ suivantes.

\[C_n = \begin{vmatrix} 1 & 0 & 0 & \cdots & 0 \\ -1 & n & 0 & \cdots & 0\\ -1 & 0 & n & \ldots & 0 \\ \vdots & \vdots & \ddots & \ddots & \vdots \\ -1 & 0 & 0 & \cdots & n\end{vmatrix}\]

En développant par rapport à la première ligne, on obtient bien :

\[C_n = n^{n-2}\]

$2.$ Un arbre composé d’arêtes orientées est un arbre enraciné. Ainsi, en partant d’un arbre non orienté, choisir un de ses sommets comme racine suffit à définir un arbre orienté.

$3.$ En partant d’un arbre non-orienté, on commence par l’enraciner, puis on choisit l’ordre d’insertion des arêtes. Cela nous donne une façon de construire un arbre orienté à partir de $G_n$ en ajoutant successivement les arêtes.

$4.$ On commence par noter qu’à partir d’un même arbre, toutes les constructions obtenues sont distinctes. De plus, si on supprime l’orientation des arêtes de l’arbre obtenu, on retrouve l’arbre de départ. De ce fait, toutes nos constructions sont distinctes. Enfin, si on considère une construction, on note qu’on peut l’obtenir à partir de l’arbre final auquel on a supprimé l’orientation. Ainsi, nous obtenons bien toutes les constructions une et une seule fois.

$5.$ Pour chaque arbre, on dispose de $n$ choix possible pour la racine. De plus, il existe $(n-1)!$ ordre différents pour la sélection des arêtes. Autrement dit $\displaystyle D_n = C_n n!$.

$6.$ On note que $G_n$ comporte $n$ composantes connexes distincts, tous composés d’un unique sommet. À la fin de la construction, il nous reste plus qu’un arbre. De plus, ajouter une arête diminue au plus le nombre de composantes de $1$. Or, on ajoute $n-1$ arêtes. Il en résulte qu’après avoir ajouté $k \lt n$ arêtes, il reste $n-k$ composantes connexes.

$7.$ On rappel qu’un arbre enraciné, est un graphe acyclique tel que tous les sommets sauf un ont un degré entrant de $1$. Lors de notre construction, on doit donc conserver le caractère acyclique et que chaque sommet ait au plus $1$ parents.

Ainsi, après avoir placé $k \lt n-1$ arêtes dans $G$, on dispose de $n-k$ composante connexe. Chacune de ces composante connexes possède un unique élément sans arête entrante. En effet, tous les sommets ont degré entrant au plus $1$ et pour assurer la connexité, la composante est constitué d’au moins autant d’arête que le nombre de sommets moins un.

De ce fait, pour ajouter une arête, on peut sélectionner n’importe quel sommet comme parent, et pour l’enfant, on doit nécessairement sélectionner une autre composante connexe. Or dans chaque autre composante connexe, il existe un unique sommet ayant degré entrant nul. De ce fait, pour chaque sommet, on peut le connecter à exactement $n-k-1$ arêtes.

Autrement dit, après avoir placé $k$ arêtes, il y a $n(n-k-1)$ possibilités pour sélectionner la prochaine arête.

$8.$ On peut donc exprimer $D_n$ sous forme d’un produit.

\[D_n = \prod\limits_{k=0}^{n-2} n(n-k-1)\]

On sort les $n$ du produit.

\[D_n = n^{n-1}\prod\limits_{k=0}^{n-2} (n-1-k) \]

Donc on reconnaît l’expression de la factorielle. Ce qui nous permet donc d’exprimer $D_n$.

\[D_n = n^{n-1}(n-1)!\]

$9.$ On réunit donc les deux formules de $D_n$.

\[C_n n! = n^{n-1}(n-1)!\]

Ce qui nous donne donc bien :

\[C_n = n^{n-2}\]

Sudoku #1

Sudoku au carré

sudoku_carre

Résoudre le sudoku en ligne.

Les règles habituelles du sudoku s’appliquent. On ajoute la règle suivante relative aux zones vertes.

  • Chaque case appartient à exactement une zone verte délimitée par un encadré vert.
  • Au sein d’une même zone verte, tous les nombres sont distincts.
  • La somme des nombres à l’intérieur d’une zone verte est toujours égale à un entier au carré (par exemple, 25, 36, 81…)

Bonne chance !

Mot croisé cryptique #1

Horizontal

1 : Pourtant dans le port $(2)$ — L’excitation de secouer un flacon $(5)$

2 : Piège le son d’un DJ et de sa flûte $(4-5)$

3 : Prêt à attaquer un parent $(4)$

4 : Piste des extrémités de l’apéro proche de Valence $(9)$

5 : Langue interne d’un hibou $(3)$ — Désigne la compression d’une entrée de conflit $(4)$

6 : Empereur dans tous ses états couronné $(5)$ — Mousse en bordure d’une pièce $(3)$

7 : Arbres s’emmêlant dans les cieux $(6)$ — À couper pour cela $(2)$

8 : Dans un déferlement cranté $(7)$

9 : Tu doserais, confus, ce que tu me dois $(8)$

Vertical

A : Terres des finales anglaises $(7)$

B : Soit chez nous $(2)$ — À table sans elle, un plaisir renversant $(4)$

C : Blâmer un ami dans le métro $(9)$

D : Se débarrassa du flou d’un principe $(3)$ — Redonne de l’ordre à ce dîner sans complexe $(4)$

E : Poudre d’un froussard pincé $(4)$ — Donc le sang bouleverse $(4)$

F : Opéra amputé et greffé et donc soigné $(5)$ — Titre hindou du crépuscule renversant des soirs $(3)$

G : S’inverse à Madrid $(2)$ — Interjection pour prendre son café dans l’arène $(3)$ — Se renverse avant le centième élément $(2)$

H : Archives d’une limace chamboulée et peu gentille $(9)$

I : Tu existes vers l’aube $(2)$ — Sondage désuet, truqué $(6)$

Solution ici !

Théorème de Kirchhoff

On présente ici un résultat important de la théorie des graphes pourtant méconnus des étudiants. Le but de cet exercice est de démontrer le théorème de Kirchhoff, aussi appelé matrix tree theorem. Ce théorème donne une formule pour compter le nombre d’arbres couvrants d’un graphe.

Cet exercice nécessite une bon maîtrise mathématique de la notion de matrice et de déterminant.

Exercice

Soit $G = (S,A)$ un graphe non orienté, avec $n = |S|$ et $m=|A|$. On associe chaque sommet de $S$ à un élément de l’ensemble $\{1,\,\ldots,\,n\}$ et on pose $A = \{a_1,\, \ldots,\, a_m\}$. Enfin, on note $\tau(G)$ le nombre d’arbres couvrants de $G$.

Soit $M$ matrice de $\mathcal{M}_{n}(\mathbb{R})$ et $i,j \leq n$. On note $M_{i,j}$ la valeur de $M$ à la coordonnée $i,j$. On définit $M[i]$ comme la matrice $M$ où on a supprimé la $i$-ème ligne de $M$ et $M[i,j]$ comme la matrice $M$ où on a supprimé la $i$-ème ligne et $j$-ème colonne de $M$.

On considère maintenant $L \in \mathcal{M}_{n}(\mathbb{R})$ la matrice Laplacienne de $G$. Pour rappel, elle est définie ainsi. Pour $i,j \leq n$ :

\[L_{i,j} = \begin{cases} \text{ degré de } i & \text{ si } i = j \\ -1 & \text{ si } (i,j) \in A \\ 0 & \text{ sinon } \end{cases}\]

On pose $B$ la matrice de $\mathcal{M}_{n,m}(\mathbb{R})$ définie pour $x \leq m$, et $(i,j) = a_x$ avec $i \lt j$, par $B_{i,x} = 1$, $B_{j,x} = -1$, et toutes les autres coordonnées sont égales à $0$.

$1.$ Prouver que $L = BB^{T}$.

$2.$ Prouver que pour tout $i$, $L[i,i] = B[i]B[i]^{T}$.

Soit $U$ un ensemble d’arêtes de $A$. On définit $B_U$ comme la matrice $B$ dont on ne garde la colonne $i$ que si $a_i \in U$.

$3.$ Montrer que tout ensemble de $n-1$ arêtes de $G$ forme un arbre couvrant si et seulement si il ne possède pas de cycles.

$4.$ Soit $U \subset A$ de taille $n-1$ tel que $U$ ne forme pas un arbre couvrant. Pour tout $i \leq n$, calculer $\det(B_U[i])$.

$5.$ Soit $U \subset A$ de taille $n-1$ tel que $U$ forme un arbre couvrant. Montrer que pour tout $i$, $\det\left(B_U[i]\right) = \pm 1$.

Donnons la formule de Binet-Cauchy. Soit $C$ et $D$ des matrices de $\mathcal{M}_{n,m}(\mathbb{R})$ et $\mathcal{M}_{m,n}(\mathbb{R})$. Pour tout ensemble $U \subset \{1,\,\ldots,\,m\}$ de $n$ éléments, on note $C_U$ la sous-matrice de $C$ dont on n’a gardé que les colonnes de $U$ et $D_U$ la sous-matrice de $D$ dont on n’a gardé que les lignes de $U$. On a alors l’égalité suivante :

\[\det(CD) = \sum\limits_{U \subset \{1,\,\ldots,\,m\} \atop |U| = n} \det(C_U)\det(D_U)\]

$6.$ En déduire que pour tout $i \leq n$ on a $\det(L[i,i]) = \tau(G)$.

Correction

$1.$ Pour tout $i$, on note $A_i$ l’ensemble des arêtes de $G$ contenant $i$. Soit $M = BB^{T}$. On a :

\begin{align*}
M_{i,i} & = \sum\limits_{x \in A} B_{i,x}B^{T}_{x,i} \\
& = \sum\limits_{x \in A_i} B_{i,x}B^{T}_{x,i} \\
& = \sum\limits_{x \in A} 1 \\
M_{i,i} & = |A_i|
\end{align*}

Ainsi, $M_{i,i}$ est bien égal au degré de $i$ et donc à $L_{i,i}.

Pour $i \neq j$, s’il n’existe pas d’arête $(i,j)$ on a pour toute arête $a \in A$, soit $B_{i,x} = 0$, soit $B_{j,x} = 0$. De ce fait, $M_{i,j} = 0 = L_{i,j}$.

Enfin, si $(i,j) \in A$, on a $B_{i,(i,j)}B_{j,(i,j)} = -1$ et pour tout $a$ de $A$ différent de $(i,j)$, $B_{i,a}B_{j,a} = 0$. Donc $M_{i,j} = -1 = L_{i,j}$.

En conclusion on a donc bien prouvé l’égalité suivante :

\[\boxed{L = BB^{T}}\]

$2.$ Si on considère que les lignes sont indicées par les sommets, on peut écrire : pour tout $j,k$ différents de $i$ on a $L[i,i]_{j,k} = L_{j,k}$. De plus $\displaystyle L_{j,k} = \sum\limits_{x \in A} B_{j,x}B^{T}_{x,k}$. Or pour tout $x$, $B_{j,x} = B[i]_{j,x}$. On a donc bien :

\[\boxed{L[i,i] = B[i]B[i]^{T}}\]

$3.$ Tout d’abord, on rappelle qu’un arbre est un graphe connexe sans cycle. Il ne reste donc qu’à prouver qu’un sous ensemble d’arêtes sans cycle de taille $n-1$ est connexe.

Commençons par préciser que tout arbre couvrant de $G$ a exactement $n-1$ arêtes. Pour s’en convaincre, il suffit d’enraciner l’arbre dans un de ses sommets. Chaque autre sommet possède alors exactement un parent et chaque arête définit une relation parent-enfant. Donc, il y a autant d’arêtes que de parents. De ce fait, il y a exactement $n-1$ arêtes.

Ainsi, si un sous-ensemble sans cycle de $n-1$ arêtes n’est pas connexe, on peut le prolonger en un arbre couvrant de taille strictement supérieure à $n-1$, ce qui n’est pas possible.

De ce fait, tout ensemble de $n-1$ arêtes de $G$ forme un arbre couvrant si et seulement si il ne possède pas de cycles.

$4.$ Si $U$ ne forme pas d’arbre couvrant, par la question précédente, on en déduit que $U$ possède un cycle. Soit $C$ les arêtes traversées dans le cycle de taille minimale de $U$. On s’intéresse à la matrice $B_C[i]$. Pour toute arête $x=(i,j) \in C$ avec $i \lt j$, on pose $\lambda_x$ qui vaut $1$ si notre cycle va de $i$ à $j$ et $-1$ si on parcourt l’arête dans l’autre sens. On note que pour tout $i$ on a :

\[\boxed{\sum\limits_{x \in C}\lambda_xB_{i,x} = 0}\]

En effet, si $i$ est un sommet apparaissant dans notre cycle, il apparaît dans exactement deux arêtes, pour assurer que $C$ soit bien un cycle minimal. Soit $x$ l’arête qui emmène à $i$ et $y$ celle qui en part. On a alors $B_{i,x} = -1$ et $B_{i,y} = 1$. Donc $B_{i,x} + B_{i,y} = 0$. De plus, si $i$ n’apparaît pas dans notre cycle, alors pour tout $x \in C$, $B_{i,x} = 0$.

Ainsi, les colonnes de $B_C$ sont linéairement dépendantes, donc les colonnes de $B_C[i]$ et de $B_U[i]$ aussi. De ce fait, $\displaystyle \boxed{\det(B_U[i]) = 0}$.

$5.$ Pour prouver ce résultat, on procède par récurrence sur $n \geq 2$, le nombre de sommets dans $G$. On pose donc $\mathcal{P}(n) = $ « Pour tout graphe $G$ à $n$ sommets et pour tout sous-ensemble $U$ d’arêtes de $G$ formant un arbre couvrant, on a pour tout sommet $i$, $\det(B_U[i]) = \pm 1$ ».

Pour le cas $n = 2$, on note que $B_U$ est une matrice à une colonne et deux lignes ayant pour termes $\pm 1$. De ce fait, $B_U[i]$ est une matrice de dimension $1$ de valeur $\pm 1$.

On suppose donc que $\mathcal{P}(n)$ est vrai pour $n \geq 2$. Montrons que $\mathcal{P}(n+1)$ est vrai. Soit $G$ un graphe à $n+1$ sommets et $U$ un ensemble de $n$ arêtes de $G$ formant un arbre couvrant. Soit $i$ un sommet de $G$. On considère $B_U[i]$. Soit $a \in S$ une arête de $U$ touchant $i$. Cette arête existe par définition d’arbre couvrant. Dans la colonne de $B_U[i]$ associé à $a$, on a donc un seul élément, ligne $j$, non nul et qui vaut $\pm 1$. On développe alors suivant cette colonne. On a alors :

\[\boxed{\det(B_U[i]) = \pm \det(B_U[i][j,a])}\]

Maintenant, on considère le graphe $G’=(S’,A’)$ dans lequel on a contracté l’arête $a$. C’est à dire, on supprime le sommet $j$ et pour toute arête $(j,k)$, on ajoute l’arête $(i,k)$. On note que le sous graphe $(S’,U’)$ qui correspond à la contraction de l’arête $a$ dans le graphe $(S,U)$, est également un arbre couvrant. De ce fait, on peut appliquer notre hypothèse de récurrence sur $G’$ pour obtenir $\det(B_U[i][j,a]) = \pm 1$. On a donc montré :

\[\boxed{\det(B_U[i]) = \pm 1}\]

$6.$ Soit $i$ un sommet de $G$. On a prouvé que $L[i,i] = B[i]B[i]^{T}$.

Appliquons la formule de Binet-Cauchy sur $\det(B[i]B[i]^{T})$. On note, $T$ l’ensemble des sous-ensembles de taille $n-1$ de $A$ formant un arbre couvrant, et $\bar{T}$ ceux de taille $n-1$ qui contiennent un cycle. On obtient alors :

\begin{align*}
\det(L[i,i]) & = \det(B[i]B[i]^{T}) \\
& = \sum\limits_{\substack{U \subset \{1,\,\ldots,\,m\} \\ |U| = n-1}} \det(B_U[i])\det(B_U[i]^{T}) \\
& = \sum\limits_{\substack{U \subset \{1,\,\ldots,\,m\} \\ |U| = n-1}} \det(B_U[i])^{2} \\
& = \sum\limits_{U \in T} \det(B_U[i])^{2} + \sum\limits_{U \in \bar{T}} \det(B_U[i])^{2} \\
\det(L[i,i]) & = \sum\limits_{U \in T} 1 + \sum\limits_{U \in \bar{T}} 0
\end{align*}

Cela nous permet donc de conclure :

\[\boxed{\det(L[i,i]) = \tau(G)}\]

Codage de Gray

Exercice

Le but du codage de Gray est de représenter les entiers de telle sorte qu’un seul bit soit modifié à chaque incrémentation. Pour $n$ un entier strictement positif, on définit la fonction $\Gamma_n$ de $\{\;0,\;\ldots,\;2^{n}-1\;\}$ dans $\{\;0,\;1\;\}^{n}$, qui à un entier associe son codage de Gray sur $n$ bits. On définit de même la fonction $B_n$ de $\{\;0,\;\ldots,\;2^{n}-1\;\}$ dans $\{\;0,\;1\;\}^{n}$ qui à un entier associe son écriture binaire sur $n$ bits.

On définit récursivement $\Gamma_n$ : $\Gamma_1(0) = 0$, $\Gamma_1(1) = 1$ et $\forall n \geq 2,\;\forall k \lt 2^{n}$ :

\[\Gamma_n(k) = \begin{cases} 0\Gamma_{n-1}(k) \text{ si $k \lt 2^{n-1}$ } \\ 1\Gamma_{n-1}(2^{n}-k-1) \text{ sinon }\end{cases}\]

$1.$a) Donner la table des valeurs de $\Gamma_3$.

b) Prouver que pour tout entier $n$ et pour tout entier $k \lt 2^{n} – 1$, les représentations $\Gamma_n(k)$ et $\Gamma_n(k+1)$ ne diffèrent que d’un seul bit.

On note cependant que cette définition ne nous permet pas de passer rapidement d’un entier en binaire à sa représentation en codage de Gray.

Soit $n \geq 1$ et $k \lt 2^{n}$. On considère la fonction $\Phi_n$ de $\{\;0,\;\ldots,\;2^{n}-1\;\}$ dans $\{\;0,\;1\;\}^{n}$ définie par :

\[\Phi_n(k) = B_n(k) \oplus B_n\left(\left\lfloor \frac{k}{2}\right\rfloor\right) \]

où l’opérateur $\oplus$ correspond au XOR bit à bit.

$2.$ Prouver que la fonction $\Phi_n$ est bijective.

$3.$ Soit $0 \leq r \lt 2^{n}$. Prouver la relation :

\[B_{n+1}(2^n+r) \oplus B_{n+1}(2^n-r-1) = \underbrace{11\ldots1}_{n+1 \text{ fois}}\]

$4.$ Déduire que pour tout $n$ et tout $k \lt 2^{n}$, on a $\Gamma_n(k) = \Phi_n(k)$.

$5.$ Donner une méthode directe pour passer de $\Gamma_n(k)$ à $B_n(k)$ et de $B_n(k)$ à $\Gamma_n(k)$.

Maintenant que nous pouvons aisément représenter les entiers par un codage de Gray, il nous reste à savoir comment incrémenter les entiers sans repasser par le codage binaire. Pour ce faire on présente la méthode suivante : soit $k \lt 2^{n}-1$. On connaît $\Gamma_n(k)$ et on cherche $\Gamma_n(k+1)$. Si le nombre de $1$ dans $\Gamma_n(k)$ est pair, alors on inverse le bit le plus à droite. Sinon, on inverse le bit à gauche du bit à $1$ le plus à droite.

$6.$ Prouver la correction de cette méthode.

Correction

$1.$ a) Calculons $\Gamma_3$.

\[\begin{matrix}\Gamma_1(0) = 0 \\ \Gamma_1(1) = 1\end{matrix} \Rightarrow \begin{matrix}\Gamma_2(0) = 00 \\ \Gamma_2(1) = 01 \\ \Gamma_2(2) = 11 \\ \Gamma_2(3) = 10 \end{matrix} \Rightarrow \begin{matrix}\Gamma_3(0) = 000 \\ \Gamma_3(1) = 001 \\ \Gamma_3(2) = 011 \\ \Gamma_3(3) = 010 \\ \Gamma_3(4) = 110 \\ \Gamma_3(5) = 111 \\ \Gamma_3(6) = 101 \\ \Gamma_3(7) = 100\end{matrix}\]

b) Prouvons par récurrence sur $n\geq1$ que pour tout $k \lt 2^{n}-1$, $\Gamma_n(k)$ et $\Gamma_n(k+1)$ ne diffèrent que d’un seul bit.

La table des valeurs de $\Gamma_1$ ci-dessus nous permet de vérifier le cas $1$. On suppose maintenant la propriété vraie au rang $n$, montrons qu’elle le reste au rang $n+1$.

Soit $k \lt 2^{n+1}-1$.

Si $k \lt 2^{n}-1$ : on a par hypothèse de récurrence que $\Gamma_n(k)$ et $\Gamma_n(k+1)$ ne diffèrent que d’un seul bit. Or :

\[\Gamma_{n+1}(k) = 0\Gamma_{n}(k) \text{ et } \Gamma_{n+1}(k+1) = 0\Gamma_{n}(k+1)\]

Ainsi $\Gamma_{n+1}(k)$ et $\Gamma_{n+1}(k)$ ne diffèrent que d’un seul bit.

Si $2^{n}-1 \lt k \lt 2^{n+1}-1$ : on a $\Gamma_{n+1}(k) = 1\Gamma_{n}(2^{n+1}-k)$ et $\Gamma_{n+1}(k+1) = 1\Gamma_{n}(2^{n+1}-k-1)$. Or, par hypothèse de récurrence, $\Gamma_{n}(2^{n+1}-k)$ et $\Gamma_{n}(2^{n+1}-k-1)$ ne diffèrent que d’un seul bit, et donc $\Gamma_{n+1}(k)$ et $\Gamma_{n+1}(k+1)$ aussi.

Enfin, si $k = 2^{n+1}-1$ : on a $\Gamma_{n+1}(k) = 0\Gamma_{n}(k)$ et $\Gamma_{n+1}(k+1) = 1\Gamma_{n}(k)$. Ces deux mots ne diffèrent que sur le premier bit, donc $\Gamma_{n+1}(k)$ et $\Gamma_{n+1}(k+1)$ ne diffèrent que d’un unique bit.

Cela prouve la propriété au rang $n+1$ et achève la récurrence.

$2.$ On note $B_n(k) = b_1 b_2 \ldots b_n$. On a alors $\displaystyle B_n\left(\left\lfloor \frac{k}{2}\right\rfloor\right) = 0 b_1 b_2 \ldots b_{n-1}$. De ce fait, en écrivant $\Phi_n(k) = a_1 a_2 \ldots a_n$ on a les relations suivantes :v

\begin{align*}
a_1 & = b_1 \\
a_2 & = b_1 \oplus b_2 \\
a_3 & = b_2 \oplus b_3 \\
\cdots & = \cdots \\
a_n & = b_{n-1} \oplus b_n
\end{align*}

On considère la fonction $F_n$ de $\{0,\;1\}^{n}$ dans $\{0,\;2^{n}\}$ définie par $F_n(a_1 a_2 \ldots a_n) = u$ où $u$ a pour représentation binaire $u_1 u_2 \ldots u_n$ avec

\begin{align*}
u_1 & = a_1 \\
u_2 & = a_1 \oplus a_2 \\
u_3 & = a_1 \oplus a_2 \oplus a_3 \\
\vdots & = \vdots \\
u_n & = a_1 \oplus a_2 \oplus \ldots \oplus a_n
\end{align*}

On note que $\displaystyle F_n\left(\Phi_n(k)\right) = k$. De ce fait $\boxed{\Phi_n \text{ est bijective. }}$

$3.$ Cette relation signifie simplement que tous les bits de la représentation en binaire de $2^{n}+r$ et $2^{n}-r-1$ sont distincts. Pour le prouver, on procède par récurrence forte sur $(n,r)$. Soit $n \in \mathbb{N}$ et $r \lt 2^{n}$. On note $\mathcal{H}(n,r) = $ « Tous les bits de la représentation en binaire sur $n+1$ bits de $2^{n}+r$ et $2^{n}-r-1$ sont distincts ».

On vérifie à la main pour $n=0$ et $n=1$.

Pour tout $n$, on a :

\[B_n(2^n) = 1\underbrace{00\ldots0}_{n \text{ fois }} \text{ et } B_n(2^n-1) = 0\underbrace{11\ldots1}_{n \text{ fois }}\]

Ce qui prouve $\mathcal{H}(n,0)$.

Soit $n \geq 1$ et $2^{n}-1 > r \geq 0$. On suppose $\mathcal{H}(m,k)$ vrai pour tout $m \lt n$, $k \lt 2^{m}$ et $\mathcal{H}(n, l)$ vrai pour $0 \leq l \leq r$. Prouvons $\mathcal{H}(n,r+1)$.

On note $B_{n+1}(2^{n}+r) = b_1 b_2 \ldots b_{n+1}$. Par hypothèse de récurrence on a :

\[B_{n+1}(2^{n}-r-1) = \overline{b_1} \overline{b_2} \ldots \overline{b_{n+1}}\]

où $\bar{b_i}$ est le bit inverse de $b_i$.

Si $b_{n+1} = 0$ : on a alors $B_{n+1}(2^{n}+r+1) = b_1 b_2 \ldots b_{n}1$ et $B_{n+1}(2^{n}-r-2) = \overline{b_1} \overline{b_2} \ldots \overline{b_{n}}0$. Donc les représentations binaires de $2^{n}+r+1$ et $2^{n}-r-2$ sur $n+1$ bits sont bien distinctes bit à bit.

Si $b_{n+1}=1$ : on a $r$ impair.

Soit $\displaystyle k = \frac{r+1}{2}$. On a alors $2(2^{n-1} + k ) = 2^{n} + r + 1$. On rappel que pour représenter le double d’un entier en binaire, il suffit d’ajouter un $0$ à la fin, ce qui nous donne donc :

\[B_{n+1}\left(2^{n}+r+1\right) = B_{n}\left(\frac{2^{n}+r-1}{2}+1\right)0\]

De même $\displaystyle B_{n+1}(2^{n}-r-2) = B_{n}\left(2^{n-1}-k-1\right)1$.

Or, par hypothèse de récurrence, $B_{n}\left(2^{n-1}-k-1\right) = \overline{B_{n}\left(2^{n-1}+k\right)}$.

Il en résulte que $\displaystyle \boxed{B_{n+1}\left(2^{n}+r+1\right) = \overline{B_{n+1}\left(2^{n}-r-2\right)}}$. Cela prouve donc ${\mathcal{H}(n,r+1)}$ et achève notre récurrence.

$4.$ Pour ce faire, il nous suffit de montrer que $\Gamma_1 = \Phi_1$, ce qui est immédiat ; puis que la récurrence suivante est satisfaite pour $n\geq2$ :

\[\Phi_{n}(k) = \begin{cases} 0\Phi_{n-1}(k) \text{ si $k \lt 2^{n-1}$ } \\ 1\Phi_{n-1}(2^{n}-k-1) \text{ sinon }\end{cases}\]

Si $k \lt 2^{n-1}$ on a bien $\Phi_{n}(k) = 0\Phi_{n-1}(k)$.

Si $k \geq 2^{n-1}$ on pose $r = k-2^{n-1}$. On a alors $k = 2^{n-1}+r$ et $2^{n}-k-1 = 2^{n-1}-r-1$. On écrit $B_{n}(k) = b_1 b_2 \ldots b_n$. La question précédente nous donne $B_{n}(2^{n-1}-r-1) = \overline{b_1} \overline{b_2} \ldots \overline{b_n}$. On note de plus que $b_1 = 1$. Ainsi :

\[\Phi_n(k) = 1(b_1 \oplus b_2)\ldots(b_{n-1}\oplus b_n) = 1u\]

Avec $u$ un mot binaire sur $n-1$ bits.

Et de plus :

\begin{align*}
\Phi_n(2^{n-1}-r-1) & = 0(\overline{b_1} \oplus \overline{b_2})\ldots(\overline{b_{n-1}}\oplus \overline{b_n}) \\
& = 0(b_1 \oplus b_2)\ldots(b_{n-1}\oplus b_n) \\
\Phi_n(2^{n-1}-r-1) & = 0u
\end{align*}

Donc $\displaystyle \boxed{\Phi_{n-1}\left(2^{n-1}-r-1\right) = u}$ et $\Phi$ satisfait notre relation de récurrence.

On a donc bien prouvé que pour tout $n$ et pour tout $k \lt 2^{n}$ :

\[\boxed{\Gamma_n(k) = \Phi_n(k)}\]

$5.$ Pour passer de $\Gamma_n(k)$ à $B_n(k)$ on utilise la représentation binaire de la fonction $F$ définie plus haut. Autrement dit, pour un mot $a_1 a_2 \ldots a_n$ codage de Gray d’un nombre, la représentation en binaire sur $n$ bits de ce nombre est $b_1 b_2 \ldots b_n$ avec :

\begin{align*}
b_1 & = a_1 \\
b_2 & = a_1 \oplus a_2 \\
b_3 & = a_1 \oplus a_2 \oplus a_3 \\
\cdots & = \cdots \\
b_n & = a_1 \oplus a_2 \oplus \ldots \oplus a_n
\end{align*}

Pour passer d’un codage binaire $b_1 b_2 \ldots b_n$ à un codage de Gray $a_1 a_2 \ldots a_n$ on pose :

\begin{align*}
a_1 & = b_1 \\
a_2 & = b_1 \oplus b_2 \\
a_3 & = b_2 \oplus b_3 \\
\cdots & = \cdots \\
a_n & = b_{n-1} \oplus b_n
\end{align*}

On note que ces deux opérations peuvent être chacune réalisées avec $n-1$ portes XOR.

$6.$ On pose $|u|_1$ le nombre de $1$ dans le mot $u$.

Encore une fois, on va procéder par récurrence sur $n$, la taille de notre représentation. Montrons que pour les représentations de taille $n$ notre méthode effectue bien l’incrémentation sur les entiers représentés avec le codage de Gray.

Le cas $n=1$ se vérifie aisément.

On suppose la propriété vraie au rang $n$, prouvons qu’elle le reste au rang $n+1$. Soit $k$ un entier positif inférieur strictement à $2^{n+1}-1$. Si $k$ est inférieur strictement à $2^{n}-1$ notre méthode fonctionne par hypothèse de récurrence, et on peut calculer le codage de Gray de $k+1$. Sinon, si $k = 2^{n}-1$, on a $\Gamma_{n}(k) = 10\ldots0$. Et par notre définition, $\Gamma_{n+1}(k) = 010\ldots0$ et $\Gamma_{n+1}(k+1) = 110\ldots0$. Or $\Gamma_{n+1}(k)$ possède un nombre impair de $1$. Notre méthode fonctionne donc bien.

Enfin, si $k \geq 2^n$ on considère $2^{n+1}-k-1$ qui est inférieur à $2^n$.

Comme on modifie un bit à chaque incrémentation, on change également la parité du nombre de $1$ dans notre codage. Il en résulte que $|\Gamma_{n+1}(k)|_1$ est de même parité que $k$. Il en résulte que $|\Gamma_{n+1}(k)|_1$ est de même parité que $|\Gamma_{n+1}(2^{n+1}-k-2)|_1$.

Si $k$ est pair, $2^{n+1}-k-2$ est également pair et on a montré précédemment que pour passer de $\Gamma_{n+1}(2^{n+1}-k-2)$ à $\Gamma_{n+1}(2^{n+1}-k-1)$ il suffisait de changer le bit le plus à droite. Donc, pour passer de $\Gamma_{n+1}(k+1)$ à $\Gamma_{n+1}(k)$, il faut changer le bit le plus à droite. Autrement dit, on doit bien changer le dernier bit pour passer de $\Gamma_{n+1}(k)$ à $\Gamma_{n+1}(k+1)$.

Le cas impair se résout de même.

On a donc prouver le cas $n+1$, ce qui achève la récurrence.

On a donc bien une méthode simple pour implémenter l’incrémentation avec le codage de Gray.