\theograyequilibre*




\begin{proof}
La preuve de ce théorème s'effectue par induction sur $\mathsf{N}$.
On peut vérifier aisément que ce théorème est établi pour les 
deux plus petites valeurs paires et impaires, \textit{i.e.} pour 
$\mathsf{N}=3$ et $\mathsf{N}=4$.

Pour le cas initial où $\mathsf{N}=3$, \textit{i.e.} $\mathsf{N-2}=1$ 
on a:  $S_1=1,1$, $l=2$,  $u_0 = \emptyset$  et $v=\emptyset$.
Ainsi, l'algorithme produit  
$U= 1,2,1$, $V = 3$, $W= 2, 1, 1,3$ et  $W' = 1,2,1,3$.
Finalement, $S_3=1,2,1,3,1,2,1,3$ qui vérifie le théorème.

Pour le cas initial où  $\mathsf{N}=4$, \textit{i.e.} $\mathsf{N-2}=2$ 
on a:  $S_1=1,2,1,2$, $l=4$, 
$u_0,u_1,u_2 = \emptyset,\emptyset,\emptyset$ et $v=\emptyset$.
Ainsi, l'algorithme produit  
$U= 1,3,2,3,4,1,4,3,2$, $V = 4$, $W= 3, 1, 2, 1,2, 4$ et  $W' = 1, 3, 2, 1,2, 4 $.
Finalement, $S_4 = 2,3,4,1,4,3,2,3,1,4,1,3,2,1,2,4$  et le code est 
totalement équilibré.

Pour le cas inductif, on définit tout d'abord quelques variables.
Soit $c_{\mathsf{N}}$ (resp. $d_{\mathsf{N}}$) le nombre d'éléments dont le nombre 
de transitions est exactement $a_{\mathsf{N}}$ (resp $a_{\mathsf{N}} +2$).
Ces deux variables sont caractérisées par le système:
 
\[
\left\{
\begin{array}{lcl}
c_{\mathsf{N}} + d_{\mathsf{N}} & = & \mathsf{N} \\
c_{\mathsf{N}}a_{\mathsf{N}} + d_{\mathsf{N}}(a_{\mathsf{N}}+2) & = & 2^{\mathsf{N}} 
\end{array}
\right.
\Leftrightarrow 
\left\{
\begin{array}{lcl}
d_{\mathsf{N}} & = & \dfrac{2^{\mathsf{N}} -\mathsf{N}.a_{\mathsf{N}}}{2} \\
c_{\mathsf{N}} &= &\mathsf{N} -  d_{\mathsf{N}}
\end{array}
\right.
\]

Puisque $a_{\mathsf{N}}$ est pair, $d_{\mathsf{N}}$ est un entier.
Prouvons d'abord que $c_{\mathsf{N}}$ et  $d_{\mathsf{N}}$ sont des entiers 
positifs.
Soit $q_{\mathsf{N}}$ et $r_{\mathsf{N}}$, définis respectivement  
comme étant le quotient et le reste dans la division euclidienne de 
$2^{\mathsf{N}}$ par $2\mathsf{N}$, \textit{i.e.} 
$2^{\mathsf{N}} = q_{\mathsf{N}}.2\mathsf{N} + r_{\mathsf{N}}$, avec $0 \le r_{\mathsf{N}} <2\mathsf{N}$.
Tout d'abord, l'entier $r$ est pair puisque $r_{\mathsf{N}}$ est un multiple de 2:
$ r_{\mathsf{N}}= 2^{\mathsf{N}} - q_{\mathsf{N}}.2\mathsf{N}= 2(2^{\mathsf{N}-1} - q_{\mathsf{N}}.\mathsf{N})$. 
Ensuite,  $a_{\mathsf{N}}$ vaut $\frac{2^{\mathsf{N}}-r_{\mathsf{N}}}{\mathsf{N}}$.
Ainsi
$d_{\mathsf{N}}$ vaut $r_{\mathsf{N}}/2$ est est donc un entier positif tel que  
$0 \le d_{\mathsf{N}} <\mathsf{N}$.
La preuve pour  $c_{\mathsf{N}}$ est évidente.


Pour chaque $i$, $1 \le i \le \mathsf{N}$, soit $zi_{\mathsf{N}}$ (resp. $ti_{\mathsf{N}}$ et  $bi_{\mathsf{N}}$) le nombre d'occurrences de l'élément 
$i$ dans la séquence $u_0, \dots, u_{l-2}$ 
(resp. dans les séquences $s_{i_1}, \dots , s_{i_l}$ et $v$)
à l'étape (\ref{item:nondet}) de l'algorithme.

En raison de la définition de $u'$ à l'étape~(\ref{item:u'}), 
$3.zi_{\mathsf{N}} + ti_{\mathsf{N}}$ est le nombre
 d'occurrences de $i$ dans la  séquence $U$.
Il est évident que le nombre d'occurrences de $i$ dans la séquence $V$ est 
$2bi_{\mathsf{N}}$ en raison de l'étape (\ref{item:VW}). 
On a ainsi le système suivant:
$$
\left\{
\begin{array}{lcl}
3.zi_{\mathsf{N}} + ti_{\mathsf{N}} + 2.bi_{\mathsf{N}} + \textit{TC}_{\mathsf{N}-2}(i) &= &\textit{TC}_{\mathsf{N}}(i) \\
zi_{\mathsf{N}} + ti_{\mathsf{N}}  + bi_{\mathsf{N}} & =& \textit{TC}_{\mathsf{N}-2}(i)
\end{array}
\right.
\qquad 
\Leftrightarrow 
$$

\begin{equation}
\left\{
\begin{array}{lcl}
zi_{\mathsf{N}} &= & 
\dfrac{\textit{TC}_{\mathsf{N}}(i) - 2.\textit{TC}_{\mathsf{N}-2}(i) - bi_{\mathsf{N}}}{2}\\
ti_{\mathsf{N}} &= & \textit{TC}_{\mathsf{N}-2}(i)-zi_{\mathsf{N}}-bi_{\mathsf{N}}
\end{array}
\right.
\label{eq:sys:zt1}
\end{equation}

Dans ce système de 2 équations à trois inconnues, on pose $b_i=0$. 
Puisque $\textit{TC}_{\mathsf{N}}$ est pair (égal à $a_{\mathsf{N}}$ 
ou à $a_{\mathsf{N}}+2$), l'inconnue  $zi_{\mathsf{N}}$ est donc un entier.
Prouvons alors que le système résultant admet toujours 
une solution positive pour $z_i$ et pour $t_i$ telle $0 \le z_i, t_i \le \textit{TC}_{\mathsf{N}-2}(i)$ et telle que leur somme est égale à 
  $\textit{TC}_{\mathsf{N}-2}(i)$. 
On remarque que cette contrainte est toujours établie si le système admet une solution. On a donc le système suivant:



\begin{equation}
\left\{
\begin{array}{lcl}
zi_{\mathsf{N}} &= & 
\dfrac{\textit{TC}_{\mathsf{N}}(i) - 2.\textit{TC}_{\mathsf{N}-2}(i) }{2}\\
ti_{\mathsf{N}} &= & \textit{TC}_{\mathsf{N}-2}(i)-zi_{\mathsf{N}}
\end{array}
\right.
\label{eq:sys:zt2}
\end{equation}

La définition de $\textit{TC}_{\mathsf{N}}(i)$ dépend de la valeur de $\mathsf{N}$. Pour $3 \le N \le 7$, on définit celles-ci comme suit:

\begin{eqnarray*}
\textit{TC}_{3} & = & [2,2,4] \\
\textit{TC}_{5} & = & [6,6,8,6,6] \\
\textit{TC}_{7} & = & [18,18,20,18,18,18,18] \\
\\
\textit{TC}_{4} & = & [4,4,4,4] \\
\textit{TC}_{6} & = & [10,10,10,10,12,12] \\
\end{eqnarray*}
Il n'est pas difficile de vérifier que dans chacun des cas précédents, 
le système  admet bien une solution.

Pour  $N  \ge 8$, on définit $\textit{TC}_{\mathsf{N}}(i)$ comme suit:
\begin{equation}
\textit{TC}_{\mathsf{N}}(i) = \left\{
\begin{array}{l} 
a_{\mathsf{N}} \textrm{ si } 1 \le i \le c_{\mathsf{N}} \\
a_{\mathsf{N}}+2 \textrm{ si } c_{\mathsf{N}} +1 \le i \le c_{\mathsf{N}} + d_{\mathsf{N}} 
\end{array}
\right.
\label{eq:TCN:def}
\end{equation}


On a ainsi
\[
\begin{array}{rcl} 
\textit{TC}_{\mathsf{N}}(i) - 2.\textit{TC}_{\mathsf{N}-2}(i) 
&\ge& 
a_{\mathsf{N}} - 2(a_{\mathsf{N}-2}+2) \\
&\ge& 
\frac{2^{\mathsf{N}}-r_{\mathsf{N}}}{\mathsf{N}}
-2 \left( \frac{2^{\mathsf{N-2}}-r_{\mathsf{N-2}}}{\mathsf{N-2}}+2\right)\\
&\ge& 
\frac{2^{\mathsf{N}}-2N}{\mathsf{N}}
-2 \left( \frac{2^{\mathsf{N-2}}}{\mathsf{N-2}}+2\right)\\
&\ge& 
\frac{(\mathsf{N} -2).2^{\mathsf{N}}-2N.2^{\mathsf{N-2}}-6N(N-2)}{\mathsf{N.(N-2)}}\\
\end{array}
\]

Une simple étude de variation de la fonction $t:\R \rightarrow \R$ telle que 
$x \mapsto t(x) = (x -2).2^{x}-2x.2^{x-2}-6x(x-2)$ montre que 
sa dérivée est strictement  positive pour $x \ge 6$ et que $t(8)=224$.
L'entier $\textit{TC}_{\mathsf{N}}(i) - 2.\textit{TC}_{\mathsf{N}-2}(i)$ est ainsi positif pour chaque  $\mathsf{N} \ge 8$, ce qui termine la preuve.
\end{proof}
