khkhj

[16dcc.git] / hamilton.tex

diff --git a/hamilton.tex b/hamilton.tex
index 694bbcf82c301ab14b9a96a88f0552fdf2affb7f..f4dc64acc1ad5528c25446919d4b670dd891423f 100644 (file)
--- a/hamilton.tex
+++ b/hamilton.tex
@@ -133,24 +133,62 @@ the code is neither balanced nor totally balanced.
 \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$. 
 \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$. 

-Then, there exists a sequence $l$ in 
+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)$ 
 are $a_{\mathsf{N}}$ or $a_{\mathsf{N}}+2$ 
 for any $i$, $1 \le i \le \mathsf{N}$.
 step~(\ref{item:nondet}) of the \emph{Robinson-Cohn extension} algorithm
 such that all the transition counts $\textit{TC}_{\mathsf{N}}(i)$ 
 are $a_{\mathsf{N}}$ or $a_{\mathsf{N}}+2$ 
 for any $i$, $1 \le i \le \mathsf{N}$.

+\end{thrm}

 
 
 
 
 
 
 
 

-\end{thrm}
-
-

 
 

+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.} 
+$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$.
+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$ 
+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 
+$U= 1,3,2,3,4,1,4,3,2$, $V = 4$, $W= 3, 1, 2, 1,2, 4$, and $W' = 1, 3, 2, 1,2, 4 $.
+Finally, $S_4$ is 
+$
+2,3,4,1,4,3,2,3,1,4,1,3,2,1,2,4
+$ 
+such that $\textit{TC}_4(i) = 4$ and the theorem is established for 
+odd and even initial values.

 
 

-\begin{proof}

 
 

+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 
+ 
+$$
+\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 
+\qquad 
+\left\{
+\begin{array}{lcl}
+d_{\mathsf{N}} & = & \dfrac{2^{\mathsf{N} -n.a_{\mathsf{N}}}{2} \\
+c_{\mathsf{N}} = \mathsf{N} -  d_{\mathsf{N}}
+\end{array}
+\right.
+$$

 
 

+Since $a_{\mathsf{N}$ is even, $d_{\mathsf{N}}$ is defined.
+Both $c_{\mathsf{N}}$ and  $d_{\mathsf{N}}$ are obviously positves.

 
 

-\end{proof}

 
 \subsection{Toward a local uniform distribution of switches}
 
 \subsection{Toward a local uniform distribution of switches}