Mathematics 357 – Combinatorics Comments on Discussion 2 – Gray Codes February 15, 2005

C. The special property of the reflected n-digit Gray codes is that the codes for successive integers 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(!))

E) 1) Think of generating 2-digit Gray codes by starting at some corner of the square (the “2-cube”)

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 · 2 = 8 possible Gray code orders:

00, 01, 11, 10 00, 10, 11, 01
01, 11, 10, 00 01, 00, 10, 11
11, 10, 00, 01 11, 01, 00, 10
10, 00, 01, 11 10, 11, 01, 00

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 · 3 · 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:

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:

The total number of different 3-digit Gray codes is therefore:

8 · 3 · 2 · (2 + 1) = 144.