\magnification=\magstep1
\centerline{Mathematics 357 -- Combinatorics}
\centerline{Comments on Discussion 2 -- Gray Codes}
\centerline{February 15, 2005}
\bigskip
\noindent
C.  The {\it special property} of the reflected $n$-digit Gray codes
is that the codes for successive integers {\it differ in only one
binary digit}.  This is equivalent to saying that the corresponding
path on the $n$-cube always follows edges, and never cuts
diagonally across a face.  We prove this assertion by induction on
$n = $ the number of binary digits.

The base case is $n = 1$.  The one-digit Gray codes are $0,1$
and the assertion is obvious(!)  So assume that the special
property is true for the $k$-digit Gray codes, namely that 
the codes for successive integers differ only in one digit.  
By the recursive construction, we get the first half of the 
list of $(k+1)$-digit codes by appending a zero at the start
of each of the $k$-digit codes.  Hence successive entries
in this portion of the $(k+1)$-digit list differ in only
one digit.  Similarly, the second half of the 
list of $(k+1)$-digit codes is obtained by appending a one 
at the start of each of the $k$-digit codes, and listing them
in reverse order.  Hence successive entries
in this portion of the $(k+1)$-digit list also differ in only
one digit.  Finally, the last number in the first half and 
the first number in the second half differ only in the first 
digit (which changes from a 0 to a 1).  Hence the $(k+1)$-digit
codes also have the special property, and we have proved
the result for all $n$ by induction.  (Note that the last step
here gives 
one reason for the ``reflection'' in the construction 
of the reflected Gray codes -- it makes
the two halves of the list ``link up'' properly so the
special property is true(!))  
\bigskip
\noindent
E) 1)  Think of generating 2-digit Gray codes
by starting at some corner of the square (the ``2-cube'')
\vglue 1.0truein
\noindent
and traversing edges to visit all 4 corners.
There are 4 possible starting points, and you can either go
clockwise or counterclockwise from each.  This gives $4\cdot 2 = 8$
possible Gray code orders:
$$\eqalign{00,01,11,10  \qquad  00,10,11,01\cr
01,11,10,00  \qquad  01,00,10,11\cr
11,10,00,01  \qquad  11,01,00,10\cr
10,00,01,11  \qquad  10,11,01,00\cr}$$
\bigskip
\noindent
2) (the extra credit part)  This is more subtle.  To 
count, we need to think of specifying all ways to 
construct paths along the edges of a cube that visit
all 8 corners (each exactly once).  As in the 
previous case, the path can start at any corner.
So there are 8 possible starting points.  From that
first point we can take any one of the 3 edges
containing that corner.  Then from the other end of that
edge, there are two possibilities, so there
are $8\cdot 3\cdot 2 = 48$ different ways to get
this far.  To draw pictures at
this point, say we started at $000$ in the ``standard''
3-cube below and took the edge to $100$ first, then 
the edge from $100$ to $110$.   (All 48 possibilities
are equivalent to this by rotations of the cube.)
From $110$, there are two choices of how to proceed:
we can go next to either $111$ or $010$. 

Say we go to $010$:
\vglue 1.0truein
\noindent
Then from there we can continue in exactly 2 different ways:
$$000,100,110,010,011,111,101,001$$ 
or 
$$000,100,110,010,011,001,101,111.$$

On the other hand if we went to $111$ next from $110$, then 
from there we can go to either $101$ or $011$.  In the first
case, continuing from $101$:
$$000,100,110,111,101,001,011,010$$
``works''.  But from 
$000,100,110,111$, the other possible next ``move'', to 
$011$, leads to an impasse.  We can't go ``down'' to the bottom
level from there since we're ``trapped'' if we do.  And
if we go to $001$, we get ``trapped'' on the top:
\vglue 1.0truein
\noindent
The total number of different 3-digit Gray codes is therefore:
$$8\cdot 3\cdot 2\cdot (2 + 1) = 144.$$

\bye
