annexePreuveGrayEquilibre.tex

   1 \theograyequilibre*
   2
   3
   4
   5
   6 \begin{proof}
   7 La preuve de ce théorème s'effectue par induction sur $\mathsf{N}$.
   8 On peut vérifier aisément que ce théorème est établi pour les
   9 deux plus petites valeurs paires et impaires, \textit{i.e.} pour
  10 $\mathsf{N}=3$ et $\mathsf{N}=4$.
  11
  12 Pour le cas initial où $\mathsf{N}=3$, \textit{i.e.} $\mathsf{N-2}=1$
  13 on a:  $S_1=1,1$, $l=2$,  $u_0 = \emptyset$  et $v=\emptyset$.
  14 Ainsi, l'algorithme produit
  15 $U= 1,2,1$, $V = 3$, $W= 2, 1, 1,3$ et  $W' = 1,2,1,3$.
  16 Finalement, $S_3=1,2,1,3,1,2,1,3$ qui vérifie le théorème.
  17
  18 Pour le cas initial où  $\mathsf{N}=4$, \textit{i.e.} $\mathsf{N-2}=2$
  19 on a:  $S_1=1,2,1,2$, $l=4$,
  20 $u_0,u_1,u_2 = \emptyset,\emptyset,\emptyset$ et $v=\emptyset$.
  21 Ainsi, l'algorithme produit
  22 $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 $.
  23 Finalement, $S_4 = 2,3,4,1,4,3,2,3,1,4,1,3,2,1,2,4$  et le code est
  24 totalement équilibré.
  25
  26 Pour le cas inductif, on définit tout d'abord quelques variables.
  27 Soit $c_{\mathsf{N}}$ (resp. $d_{\mathsf{N}}$) le nombre d'éléments dont le nombre
  28 de transitions est exactement $a_{\mathsf{N}}$ (resp $a_{\mathsf{N}} +2$).
  29 Ces deux variables sont caractérisées par le système:
  30
  31 \[
  32 \left\{
  33 \begin{array}{lcl}
  34 c_{\mathsf{N}} + d_{\mathsf{N}} & = & \mathsf{N} \\
  35 c_{\mathsf{N}}a_{\mathsf{N}} + d_{\mathsf{N}}(a_{\mathsf{N}}+2) & = & 2^{\mathsf{N}}
  36 \end{array}
  37 \right.
  38 \Leftrightarrow
  39 \left\{
  40 \begin{array}{lcl}
  41 d_{\mathsf{N}} & = & \dfrac{2^{\mathsf{N}} -\mathsf{N}.a_{\mathsf{N}}}{2} \\
  42 c_{\mathsf{N}} &= &\mathsf{N} -  d_{\mathsf{N}}
  43 \end{array}
  44 \right.
  45 \]
  46
  47 Puisque $a_{\mathsf{N}}$ est pair, $d_{\mathsf{N}}$ est un entier.
  48 Prouvons d'abord que $c_{\mathsf{N}}$ et  $d_{\mathsf{N}}$ sont des entiers
  49 positifs.
  50 Soit $q_{\mathsf{N}}$ et $r_{\mathsf{N}}$, définis respectivement
  51 comme étant le quotient et le reste dans la division euclidienne de
  52 $2^{\mathsf{N}}$ par $2\mathsf{N}$, \textit{i.e.}
  53 $2^{\mathsf{N}} = q_{\mathsf{N}}.2\mathsf{N} + r_{\mathsf{N}}$, avec $0 \le r_{\mathsf{N}} <2\mathsf{N}$.
  54 Tout d'abord, l'entier $r$ est pair puisque $r_{\mathsf{N}}$ est un multiple de 2:
  55 $ r_{\mathsf{N}}= 2^{\mathsf{N}} - q_{\mathsf{N}}.2\mathsf{N}= 2(2^{\mathsf{N}-1} - q_{\mathsf{N}}.\mathsf{N})$.
  56 Ensuite,  $a_{\mathsf{N}}$ vaut $\frac{2^{\mathsf{N}}-r_{\mathsf{N}}}{\mathsf{N}}$.
  57 Ainsi
  58 $d_{\mathsf{N}}$ vaut $r_{\mathsf{N}}/2$ est est donc un entier positif tel que
  59 $0 \le d_{\mathsf{N}} <\mathsf{N}$.
  60 La preuve pour  $c_{\mathsf{N}}$ est évidente.
  61
  62
  63 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
  64 $i$ dans la séquence $u_0, \dots, u_{l-2}$
  65 (resp. dans les séquences $s_{i_1}, \dots , s_{i_l}$ et $v$)
  66 à l'étape (\ref{item:nondet}) de l'algorithme.
  67
  68 En raison de la définition de $u'$ à l'étape~(\ref{item:u'}),
  69 $3.zi_{\mathsf{N}} + ti_{\mathsf{N}}$ est le nombre
  70  d'occurrences de $i$ dans la  séquence $U$.
  71 Il est évident que le nombre d'occurrences de $i$ dans la séquence $V$ est
  72 $2bi_{\mathsf{N}}$ en raison de l'étape (\ref{item:VW}).
  73 On a ainsi le système suivant:
  74 $$
  75 \left\{
  76 \begin{array}{lcl}
  77 3.zi_{\mathsf{N}} + ti_{\mathsf{N}} + 2.bi_{\mathsf{N}} + \textit{TC}_{\mathsf{N}-2}(i) &= &\textit{TC}_{\mathsf{N}}(i) \\
  78 zi_{\mathsf{N}} + ti_{\mathsf{N}}  + bi_{\mathsf{N}} & =& \textit{TC}_{\mathsf{N}-2}(i)
  79 \end{array}
  80 \right.
  81 \qquad
  82 \Leftrightarrow
  83 $$
  84
  85 \begin{equation}
  86 \left\{
  87 \begin{array}{lcl}
  88 zi_{\mathsf{N}} &= &
  89 \dfrac{\textit{TC}_{\mathsf{N}}(i) - 2.\textit{TC}_{\mathsf{N}-2}(i) - bi_{\mathsf{N}}}{2}\\
  90 ti_{\mathsf{N}} &= & \textit{TC}_{\mathsf{N}-2}(i)-zi_{\mathsf{N}}-bi_{\mathsf{N}}
  91 \end{array}
  92 \right.
  93 \label{eq:sys:zt1}
  94 \end{equation}
  95
  96 Dans ce système de 2 équations à trois inconnues, on pose $b_i=0$.
  97 Puisque $\textit{TC}_{\mathsf{N}}$ est pair (égal à $a_{\mathsf{N}}$
  98 ou à $a_{\mathsf{N}}+2$), l'inconnue  $zi_{\mathsf{N}}$ est donc un entier.
  99 Prouvons alors que le système résultant admet toujours
 100 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 à
 101   $\textit{TC}_{\mathsf{N}-2}(i)$.
 102 On remarque que cette contrainte est toujours établie si le système admet une solution. On a donc le système suivant:
 103
 104
 105
 106 \begin{equation}
 107 \left\{
 108 \begin{array}{lcl}
 109 zi_{\mathsf{N}} &= &
 110 \dfrac{\textit{TC}_{\mathsf{N}}(i) - 2.\textit{TC}_{\mathsf{N}-2}(i) }{2}\\
 111 ti_{\mathsf{N}} &= & \textit{TC}_{\mathsf{N}-2}(i)-zi_{\mathsf{N}}
 112 \end{array}
 113 \right.
 114 \label{eq:sys:zt2}
 115 \end{equation}
 116
 117 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:
 118
 119 \begin{eqnarray*}
 120 \textit{TC}_{3} & = & [2,2,4] \\
 121 \textit{TC}_{5} & = & [6,6,8,6,6] \\
 122 \textit{TC}_{7} & = & [18,18,20,18,18,18,18] \\
 123 \\
 124 \textit{TC}_{4} & = & [4,4,4,4] \\
 125 \textit{TC}_{6} & = & [10,10,10,10,12,12] \\
 126 \end{eqnarray*}
 127 Il n'est pas difficile de vérifier que dans chacun des cas précédents,
 128 le système  admet bien une solution.
 129
 130 Pour  $N  \ge 8$, on définit $\textit{TC}_{\mathsf{N}}(i)$ comme suit:
 131 \begin{equation}
 132 \textit{TC}_{\mathsf{N}}(i) = \left\{
 133 \begin{array}{l}
 134 a_{\mathsf{N}} \textrm{ si } 1 \le i \le c_{\mathsf{N}} \\
 135 a_{\mathsf{N}}+2 \textrm{ si } c_{\mathsf{N}} +1 \le i \le c_{\mathsf{N}} + d_{\mathsf{N}}
 136 \end{array}
 137 \right.
 138 \label{eq:TCN:def}
 139 \end{equation}
 140
 141
 142 On a ainsi
 143 \[
 144 \begin{array}{rcl}
 145 \textit{TC}_{\mathsf{N}}(i) - 2.\textit{TC}_{\mathsf{N}-2}(i)
 146 &\ge&
 147 a_{\mathsf{N}} - 2(a_{\mathsf{N}-2}+2) \\
 148 &\ge&
 149 \frac{2^{\mathsf{N}}-r_{\mathsf{N}}}{\mathsf{N}}
 150 -2 \left( \frac{2^{\mathsf{N-2}}-r_{\mathsf{N-2}}}{\mathsf{N-2}}+2\right)\\
 151 &\ge&
 152 \frac{2^{\mathsf{N}}-2N}{\mathsf{N}}
 153 -2 \left( \frac{2^{\mathsf{N-2}}}{\mathsf{N-2}}+2\right)\\
 154 &\ge&
 155 \frac{(\mathsf{N} -2).2^{\mathsf{N}}-2N.2^{\mathsf{N-2}}-6N(N-2)}{\mathsf{N.(N-2)}}\\
 156 \end{array}
 157 \]
 158
 159 Une simple étude de variation de la fonction $t:\R \rightarrow \R$ telle que
 160 $x \mapsto t(x) = (x -2).2^{x}-2x.2^{x-2}-6x(x-2)$ montre que
 161 sa dérivée est strictement  positive pour $x \ge 6$ et que $t(8)=224$.
 162 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.
 163 \end{proof}