]> AND Private Git Repository - 16dcc.git/blobdiff - hamilton.tex
Logo AND Algorithmique Numérique Distribuée

Private GIT Repository
ajout de fichiers
[16dcc.git] / hamilton.tex
index 4cbbc90677bc5b4abdef456f73493362b6d1231f..a48fc6254648226359a098a9f4d7e8101dbb0ce2 100644 (file)
@@ -1,13 +1,13 @@
 Many approaches have been developed to solve the problem of building
 Many approaches have been developed to solve the problem of building
-a Gray code in a $\mathsf{N}$ cube~\cite{Robinson:1981:CS,DBLP:journals/combinatorics/BhatS96,ZanSup04,Bykov2016}, according to properties 
+a Gray code in a $\mathsf{N}$-cube~\cite{Robinson:1981:CS,DBLP:journals/combinatorics/BhatS96,ZanSup04,Bykov2016}, according to properties 
 the produced code has to verify.
 For instance,~\cite{DBLP:journals/combinatorics/BhatS96,ZanSup04} focus on
 balanced Gray codes. In the transition sequence of these codes, 
 the number of transitions of each element must differ
 at most by 2.
 the produced code has to verify.
 For instance,~\cite{DBLP:journals/combinatorics/BhatS96,ZanSup04} focus on
 balanced Gray codes. In the transition sequence of these codes, 
 the number of transitions of each element must differ
 at most by 2.
-This uniformity is a global property on the cycle, \textit{i.e.}
+This uniformity is a global property on the cycle, \textit{i.e.},
 a property that is established while traversing the whole cycle.
 a property that is established while traversing the whole cycle.
-On the opposite side, when the objective is to follow a subpart 
+On the other hand, when the objective is to follow a subpart 
 of the Gray code and to switch each element approximately the 
 same amount of times,
 local properties are wished.
 of the Gray code and to switch each element approximately the 
 same amount of times,
 local properties are wished.
@@ -15,15 +15,17 @@ For instance, the locally balanced property is studied in~\cite{Bykov2016}
 and an algorithm that establishes locally balanced Gray codes is given.
  
 The current context is to provide a function 
 and an algorithm that establishes locally balanced Gray codes is given.
  
 The current context is to provide a function 
-$f:\Bool^{\mathsf{N}} \rightarrow \Bool^{\mathsf{N}}$ by removing a Hamiltonian 
-cycle in the $\mathsf{N}$ cube. Such a function is going to be iterated
-$b$ time to produce a pseudo random number, \textit{i.e.} a vertex in the 
-$\mathsf{N}$ cube.
+$f:\Bool^{\mathsf{N}} \rightarrow \Bool^{\mathsf{N}}$ by removing an Hamiltonian 
+cycle in the $\mathsf{N}$-cube. Such a function is going to be iterated
+$b$ times to produce a pseudorandom number,
+\textit{i.e.}, a vertex in the 
+$\mathsf{N}$-cube.
 Obviously, the number of iterations $b$ has to be sufficiently large 
 to provide a uniform output distribution.
 Obviously, the number of iterations $b$ has to be sufficiently large 
 to provide a uniform output distribution.
-To reduced the number of iterations, the provided Gray code
-should ideally possess the both balanced and locally balanced properties.
-However, none of the two algorithms is compatible with the second one:
+To reduce the number of iterations, it can be claimed
+that the provided Gray code
+should ideally possess both balanced and locally balanced properties.
+However, both algorithms are incompatible with the second one:
 balanced Gray codes that are generated by state of the art works~\cite{ZanSup04,DBLP:journals/combinatorics/BhatS96} are not locally balanced. Conversely,
 locally balanced Gray codes yielded by Igor Bykov approach~\cite{Bykov2016}
 are not globally balanced.
 balanced Gray codes that are generated by state of the art works~\cite{ZanSup04,DBLP:journals/combinatorics/BhatS96} are not locally balanced. Conversely,
 locally balanced Gray codes yielded by Igor Bykov approach~\cite{Bykov2016}
 are not globally balanced.
@@ -35,62 +37,62 @@ the number of switches of each element is as uniform as possible.
 \subsection{Analysis of the Robinson-Cohn extension algorithm}
 As far as we know three works, 
 namely~\cite{Robinson:1981:CS},~\cite{DBLP:journals/combinatorics/BhatS96}, 
 \subsection{Analysis of the Robinson-Cohn extension algorithm}
 As far as we know three works, 
 namely~\cite{Robinson:1981:CS},~\cite{DBLP:journals/combinatorics/BhatS96}, 
-and~\cite{ZanSup04} have adressed the probem of providing an approach
+and~\cite{ZanSup04} have addressed the problem of providing an approach
 to produce balanced gray code.
 The authors of~\cite{Robinson:1981:CS} introduced an inductive approach
 to produce balanced gray code.
 The authors of~\cite{Robinson:1981:CS} introduced an inductive approach
-aiming at producing balanced Gray codes, provided the user gives 
+aiming at producing balanced Gray codes, assuming the user gives 
 a special subsequence of the transition sequence at each induction step.
 a special subsequence of the transition sequence at each induction step.
-This work have been strengthened in~\cite{DBLP:journals/combinatorics/BhatS96}
-where the authors have explicitely shown how to construct such a subsequence.
+This work has been strengthened in~\cite{DBLP:journals/combinatorics/BhatS96}
+where the authors have explicitly shown how to build such a subsequence.
 Finally the authors of~\cite{ZanSup04} have presented 
 the \emph{Robinson-Cohn extension} 
 Finally the authors of~\cite{ZanSup04} have presented 
 the \emph{Robinson-Cohn extension} 
-algorithm. There rigourous presentation of this one 
-have mainly allowed them to prove two properties.
+algorithm. Their rigorous presentation of this algorithm
+has mainly allowed them to prove two properties.
 The former states that if 
 $\mathsf{N}$ is a 2-power, a balanced Gray code is always totally balanced.
 The latter states that for every $\mathsf{N}$ there 
 The former states that if 
 $\mathsf{N}$ is a 2-power, a balanced Gray code is always totally balanced.
 The latter states that for every $\mathsf{N}$ there 
-exists a Gray code such that all transition count numbers are 
+exists a Gray code such that all transition count numbers 
 are 2-powers whose exponents are either equal
 or differ from each other by 1.
 However, the authors do not prove that the approach allows to build 
 are 2-powers whose exponents are either equal
 or differ from each other by 1.
 However, the authors do not prove that the approach allows to build 
-(totally balanced) Gray code. 
+(totally balanced) Gray codes
 What follows shows that this fact is established and first recalls the approach.
 
 
 Let be given a $\mathsf{N}-2$-bit Gray code whose transition sequence is
 $S_{\mathsf{N}-2}$. What follows is the 
  \emph{Robinson-Cohn extension} method~\cite{ZanSup04}
 What follows shows that this fact is established and first recalls the approach.
 
 
 Let be given a $\mathsf{N}-2$-bit Gray code whose transition sequence is
 $S_{\mathsf{N}-2}$. What follows is the 
  \emph{Robinson-Cohn extension} method~\cite{ZanSup04}
-which produces a $n$-bits Gray code.
+which produces a $\mathsf{N}$-bits Gray code.
 
 \begin{enumerate}
 \item \label{item:nondet}Let $l$ be an even positive integer. Find 
 $u_1, u_2, \dots , u_{l-2}, v$ (maybe empty) subsequences of $S_{\mathsf{N}-2}$ 
 such that $S_{\mathsf{N}-2}$ is the concatenation of 
 $$
 
 \begin{enumerate}
 \item \label{item:nondet}Let $l$ be an even positive integer. Find 
 $u_1, u_2, \dots , u_{l-2}, v$ (maybe empty) subsequences of $S_{\mathsf{N}-2}$ 
 such that $S_{\mathsf{N}-2}$ is the concatenation of 
 $$
-s_{i_1}, u_0, s_{i_2}, u_1, s_{i_3}, u_2, . . . , s_{i_l-1}, u_{l-2}, s_{i_l}, v
+s_{i_1}, u_0, s_{i_2}, u_1, s_{i_3}, u_2, \dots , s_{i_l-1}, u_{l-2}, s_{i_l}, v
 $$
 where $i_1 = 1$, $i_2 = 2$, and $u_0 = \emptyset$ (the empty sequence).
 $$
 where $i_1 = 1$, $i_2 = 2$, and $u_0 = \emptyset$ (the empty sequence).
-\item Replace in $S_{\mathsf{N}-2}$ the sequences $u_0, u_1, u_2, \ldots, u_{l-2}$ 
+\item\label{item:u'}Replace in $S_{\mathsf{N}-2}$ the sequences $u_0, u_1, u_2, \ldots, u_{l-2}$ 
   by 
   $\mathsf{N} - 1,  u'(u_1,\mathsf{N} - 1, \mathsf{N}) , u'(u_2,\mathsf{N}, \mathsf{N} - 1), u'(u_3,\mathsf{N} - 1,\mathsf{N}), \dots, u'(u_{l-2},\mathsf{N}, \mathsf{N} - 1)$
   respectively, where $u'(u,x,y)$ is the sequence $u,x,u^R,y,u$ such that 
   $u^R$ is $u$ in reversed order. 
   The obtained sequence is further denoted as $U$.
   by 
   $\mathsf{N} - 1,  u'(u_1,\mathsf{N} - 1, \mathsf{N}) , u'(u_2,\mathsf{N}, \mathsf{N} - 1), u'(u_3,\mathsf{N} - 1,\mathsf{N}), \dots, u'(u_{l-2},\mathsf{N}, \mathsf{N} - 1)$
   respectively, where $u'(u,x,y)$ is the sequence $u,x,u^R,y,u$ such that 
   $u^R$ is $u$ in reversed order. 
   The obtained sequence is further denoted as $U$.
-\item Construct the sequences $V=v^R,\mathsf{N},v$, $W=\mathsf{N}-1,S_{\mathsf{N}-2},\mathsf{N}$, and let $W'$ be $W$ where the first 
+\item\label{item:VW} Construct the sequences $V=v^R,\mathsf{N},v$, $W=\mathsf{N}-1,S_{\mathsf{N}-2},\mathsf{N}$, and let $W'$ be $W$ where the first 
 two elements have been exchanged.
 \item The transition sequence $S_{\mathsf{N}}$ is thus the concatenation $U^R, V, W'$.
 \end{enumerate} 
 
 It has been proven in~\cite{ZanSup04} that 
 two elements have been exchanged.
 \item The transition sequence $S_{\mathsf{N}}$ is thus the concatenation $U^R, V, W'$.
 \end{enumerate} 
 
 It has been proven in~\cite{ZanSup04} that 
-$S_{\mathsf{N}}$ is transition sequence of a cyclic $\mathsf{N}$-bits Gray code 
+$S_{\mathsf{N}}$ is the transition sequence of a cyclic $\mathsf{N}$-bits Gray code 
 if $S_{\mathsf{N}-2}$ is. 
 if $S_{\mathsf{N}-2}$ is. 
-However, the step~(\ref{item:nondet}) is not a constructive 
-step that precises how to select the subsequences which ensures that 
+However, step~(\ref{item:nondet}) is not a constructive 
+step that precises how to select the subsequences which ensure that 
 yielded Gray code is balanced.
 yielded Gray code is balanced.
-Next section shows how to choose the sequence $l$ to have the balancy property.
+Following sections show how to choose the sequence $l$ to have the balance property.
 
 \subsection{Balanced Codes}
 
 \subsection{Balanced Codes}
-Let us first recall how to formalize the balancy property of a Gray code.
+Let us first recall how to formalize the balance property of a Gray code.
 Let  $L = w_1, w_2, \dots, w_{2^\mathsf{N}}$ be the sequence 
 of a $\mathsf{N}$-bits cyclic Gray code. 
 The  transition sequence 
 Let  $L = w_1, w_2, \dots, w_{2^\mathsf{N}}$ be the sequence 
 of a $\mathsf{N}$-bits cyclic Gray code. 
 The  transition sequence 
@@ -111,28 +113,26 @@ $|\textit{TC}_{\mathsf{N}}(i) - \textit{TC}_{\mathsf{N}}(j)| \le  2$.
 
    
 \begin{xpl}
 
    
 \begin{xpl}
-Let $L^*=000,100,101,001,011,111,110,010$ be the Gray code that corresponds to 
+Let $L^*=000,100,101,001,011,111,$ $110,010$ be the Gray code that corresponds to 
 the Hamiltonian cycle that has been removed in $f^*$.
 Its transition sequence is $S=3,1,3,2,3,1,3,2$ and its transition count function is 
 $\textit{TC}_3(1)= \textit{TC}_3(2)=2$ and  $\textit{TC}_3(3)=4$. Such a Gray code is balanced. 
 
 the Hamiltonian cycle that has been removed in $f^*$.
 Its transition sequence is $S=3,1,3,2,3,1,3,2$ and its transition count function is 
 $\textit{TC}_3(1)= \textit{TC}_3(2)=2$ and  $\textit{TC}_3(3)=4$. Such a Gray code is balanced. 
 
-Let now  
-$L^4=0000, 0010, 0110, 1110, 1111, 0111, 0011, 0001, 0101,$
-$0100, 1100, 1101, 1001, 1011, 1010, 1000$
-be a cyclic Gray code. Since $S=2,3,4,1,4,3,2,3,1,4,1,3,2,1,2,4$ $\textit{TC}_4$ is equal to 4 everywhere, this code
+Let  $L^4$ $=0000,0010,0110,1110,1111,0111,0011,0001,0101,0100,1100,1101,1001,1011,1010,1000$
+be a cyclic Gray code. Since $S=2,3,4,1,4,$ $3,2,3,1,4,1,3,2,1,2,4$, $\textit{TC}_4$ is equal to 4 everywhere, this code
 is thus totally balanced.
 
 On the contrary, for the standard $4$-bits Gray code  
 is thus totally balanced.
 
 On the contrary, for the standard $4$-bits Gray code  
-$L^{\textit{st}}=0000,0001,0011,0010,0110,0111,0101,0100,1100,$
-$1101,1111,1110,1010,1011,1001,1000$,
+$L^{\textit{st}}=0000,0001,0011, 
+0010,0110,0111,0101,0100,$ \newline $1100,1101,1111,1110,1010,1011,1001,1000$,
 we have $\textit{TC}_4(1)=8$ $\textit{TC}_4(2)=4$ $\textit{TC}_4(3)=\textit{TC}_4(4)=2$ and
 the code is neither balanced nor totally balanced.
 \end{xpl}
 
 
 \begin{thrm}\label{prop:balanced}
 we have $\textit{TC}_4(1)=8$ $\textit{TC}_4(2)=4$ $\textit{TC}_4(3)=\textit{TC}_4(4)=2$ and
 the code is neither balanced nor totally balanced.
 \end{xpl}
 
 
 \begin{thrm}\label{prop:balanced}
-Let $\mathsf{N}$ in $\Nats$, and $a_{\mathsf{N}}$ be defined by
-$a_{\mathsf{N}}= 2 \lfloor \dfrac{2^{\mathsf{N}}}{2\mathsf{N}} \rfloor$. 
+Let $\mathsf{N}$ in $\Nats^*$, and $a_{\mathsf{N}}$ be defined by
+$a_{\mathsf{N}}= 2 \left\lfloor \dfrac{2^{\mathsf{N}}}{2\mathsf{N}} \right\rfloor$. 
 There exists then a sequence $l$ in 
 step~(\ref{item:nondet}) of the \emph{Robinson-Cohn extension} algorithm
 such that all the transition counts $\textit{TC}_{\mathsf{N}}(i)$ 
 There exists then a sequence $l$ in 
 step~(\ref{item:nondet}) of the \emph{Robinson-Cohn extension} algorithm
 such that all the transition counts $\textit{TC}_{\mathsf{N}}(i)$ 
@@ -144,14 +144,14 @@ for any $i$, $1 \le i \le \mathsf{N}$.
 
 
 
 
 
 
-The proof is done by induction on $\mathsf{N}$. Let us imadialty verify 
-that it is established for both odd and even smallest values, \textit{i.e.} 
+The proof is done by induction on $\mathsf{N}$. Let us immediately verify 
+that it is established for both odd and even smallest values, \textit{i.e.}, 
 $3$ and $4$.
 $3$ and $4$.
-For the initial case where $\mathsf{N}=3$, \textit{i.e.} $\mathsf{N-2}=1$ we successively have:  $S_1=1,1$, $l=2$,  $u_0 = \emptyset$, and $v=\emptyset$.
+For the initial case where $\mathsf{N}=3$, \textit{i.e.}, $\mathsf{N-2}=1$ we successively have:  $S_1=1,1$, $l=2$,  $u_0 = \emptyset$, and $v=\emptyset$.
 Thus again the algorithm successively produces 
 $U= 1,2,1$, $V = 3$, $W= 2, 1, 1,3$, and $W' = 1,2,1,3$.
 Finally, $S_3$ is $1,2,1,3,1,2,1,3$ which obviously verifies the theorem.    
 Thus again the algorithm successively produces 
 $U= 1,2,1$, $V = 3$, $W= 2, 1, 1,3$, and $W' = 1,2,1,3$.
 Finally, $S_3$ is $1,2,1,3,1,2,1,3$ which obviously verifies the theorem.    
- For the initial case where $\mathsf{N}=4$, \textit{i.e.} $\mathsf{N-2}=2$ 
+ For the initial case where $\mathsf{N}=4$, \textit{i.e.}, $\mathsf{N-2}=2$ 
 we successively have:  $S_1=1,2,1,2$, $l=4$, 
 $u_0,u_1,u_2 = \emptyset,\emptyset,\emptyset$, and $v=\emptyset$.
 Thus again the algorithm successively produces 
 we successively have:  $S_1=1,2,1,2$, $l=4$, 
 $u_0,u_1,u_2 = \emptyset,\emptyset,\emptyset$, and $v=\emptyset$.
 Thus again the algorithm successively produces 
@@ -166,33 +166,168 @@ odd and even initial values.
 
 For the inductive case, let us first define some variables.
 Let $c_{\mathsf{N}}$ (resp. $d_{\mathsf{N}}$) be the number of elements 
 
 For the inductive case, let us first define some variables.
 Let $c_{\mathsf{N}}$ (resp. $d_{\mathsf{N}}$) be the number of elements 
-whose transistion count is exactly $a_{\mathsf{N}}$ (resp $a_{\mathsf{N}} +2$).
-These two variables are defined by the system 
+whose transition count is exactly $a_{\mathsf{N}}$ (resp $a_{\mathsf{N}} +2$).
+Both of these variables are defined by the system 
  
  
-$$
+\[
 \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.
 \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.
-\qquad 
 \Leftrightarrow 
 \Leftrightarrow 
-\qquad 
 \left\{
 \begin{array}{lcl}
 \left\{
 \begin{array}{lcl}
-d_{\mathsf{N}} & = & \dfrac{2^{\mathsf{N}} -n.a_{\mathsf{N}}}{2} \\
+d_{\mathsf{N}} & = & \dfrac{2^{\mathsf{N}} -\mathsf{N}.a_{\mathsf{N}}}{2} \\
 c_{\mathsf{N}} &= &\mathsf{N} -  d_{\mathsf{N}}
 \end{array}
 \right.
 c_{\mathsf{N}} &= &\mathsf{N} -  d_{\mathsf{N}}
 \end{array}
 \right.
+\]
+
+Since $a_{\mathsf{N}}$ is even, $d_{\mathsf{N}}$ is an integer.
+Let us first prove that both $c_{\mathsf{N}}$ and  $d_{\mathsf{N}}$ are positive
+integers.
+Let $q_{\mathsf{N}}$ and $r_{\mathsf{N}}$, respectively, be  
+the quotient and the remainder in the Euclidean division
+of $2^{\mathsf{N}}$ by $2\mathsf{N}$, \textit{i.e.}, 
+$2^{\mathsf{N}} = q_{\mathsf{N}}.2\mathsf{N} + r_{\mathsf{N}}$, with $0 \le r_{\mathsf{N}} <2\mathsf{N}$.
+First of all, the integer $r$ is even since $r_{\mathsf{N}} = 2^{\mathsf{N}} - q_{\mathsf{N}}.2\mathsf{N}= 2(2^{\mathsf{N}-1} - q_{\mathsf{N}}.\mathsf{N})$. 
+Next,  $a_{\mathsf{N}}$ is $\frac{2^{\mathsf{N}}-r_{\mathsf{N}}}{\mathsf{N}}$. Consequently 
+$d_{\mathsf{N}}$ is $r_{\mathsf{N}}/2$ and is thus a positive integer s.t. 
+$0 \le d_{\mathsf{N}} <\mathsf{N}$.
+The proof for $c_{\mathsf{N}}$ is obvious.
+
+
+For any $i$, $1 \le i \le \mathsf{N}$, let $zi_{\mathsf{N}}$ (resp. $ti_{\mathsf{N}}$ and $bi_{\mathsf{N}}$) 
+be the occurrence number of element $i$ in the sequence $u_0, \dots, u_{l-2}$ 
+(resp. in the sequences $s_{i_1}, \dots , s_{i_l}$ and $v$)
+in step (\ref{item:nondet}) of the algorithm.
+
+Due to the definition of $u'$ in step~(\ref{item:u'}), 
+$3.zi_{\mathsf{N}} + ti_{\mathsf{N}}$ is the
+ number of element $i$ in the sequence $U$.
+It is clear that the number of element $i$ in the sequence $V$ is 
+$2bi_{\mathsf{N}}$ due to step (\ref{item:VW}). 
+We thus have the following system:
+$$
+\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 
 $$
 
 $$
 
-Since $a_{\mathsf{N}$ is even, $d_{\mathsf{N}}$ is defined.
-Both $c_{\mathsf{N}}$ and  $d_{\mathsf{N}}$ are obviously positves.
+\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}
+
+In this set of 2 equations with 3 unknown variables, let $b_i$ be set with 0.
+In this case, since $\textit{TC}_{\mathsf{N}}$ is even (equal to $a_{\mathsf{N}}$ 
+or to $a_{\mathsf{N}}+2$), the variable  $zi_{\mathsf{N}}$ is thus an integer.
+Let us now prove that the resulting system has always positive integer 
+solutions $z_i$, $t_i$, $0 \le z_i, t_i \le \textit{TC}_{\mathsf{N}-2}(i)$ 
+and s.t. their sum is equal to $\textit{TC}_{\mathsf{N}-2}(i)$. 
+This latter constraint is obviously established if the system has a solution.
+We thus have the following system.
+
+
+
+\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}
+
+The definition of $\textit{TC}_{\mathsf{N}}(i)$ depends on the value of $\mathsf{N}$.
+When $3 \le N \le 7$, values are defined as follows:
+\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*}
+It is not difficult to check that all these instanciations verify the aforementioned constraints. 
+
+When  $N  \ge 8$, $\textit{TC}_{\mathsf{N}}(i)$ is defined as follows:
+\begin{equation}
+\textit{TC}_{\mathsf{N}}(i) = \left\{
+\begin{array}{l} 
+a_{\mathsf{N}} \textrm{ if } 1 \le i \le c_{\mathsf{N}} \\
+a_{\mathsf{N}}+2 \textrm{ if } c_{\mathsf{N}} +1 \le i \le c_{\mathsf{N}} + d_{\mathsf{N}} 
+\end{array}
+\right.
+\label{eq:TCN:def}
+\end{equation}
+
+
+We thus  have
+\[
+\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}
+\]
+
+A simple variation study of the function $t:\R \rightarrow \R$ such that 
+$x \mapsto t(x) = (x -2).2^{x}-2x.2^{x-2}-6x(x-2)$ shows that 
+its derivative is strictly positive if $x \ge 6$ and $t(8)=224$.
+The integer $\textit{TC}_{\mathsf{N}}(i) - 2.\textit{TC}_{\mathsf{N}-2}(i)$ is thus positive 
+for any $\mathsf{N} \ge 8$ and the proof is established.
+
+
+% \begin{table}[ht]
+% $$
+% \begin{array}{|l|l|l|l|l|l|}
+% \hline
+% \mathsf{N}     & 3 & 4 & 5 & 6  & 7\\
+% \hline
+% a_{\mathsf{N}} & 2 & 4 & 6 & 10 & 18\\
+% \hline
+% \end{array}
+% $$
+% \label{tab:an}
+% \caption{First values of  $a_{\mathsf{N}}$}
+% \end{table}
 
 
+For each element $i$, we are then left to choose $zi_{\mathsf{N}}$ positions 
+among $\textit{TC}_{\mathsf{N}}(i)$, which leads to 
+${\textit{TC}_{\mathsf{N}}(i) \choose zi_{\mathsf{N}} }$ possibilities.
+Notice that all such choices lead to an Hamiltonian path.
 
 
 
 
 
 
 
 
 
 
-\subsection{Toward a local uniform distribution of switches}
+%%% Local Variables:
+%%% mode: latex
+%%% TeX-master: "main"
+%%% ispell-dictionary: "american"
+%%% mode: flyspell
+%%% End: