"Anti-Gray codes" that maximize the number of bits that change at each step Let $N$ be a non-negative integer and let $S$ be some ordering of the $2^N$ distinct $N$-tuples of binary digits.  We can look at the number of bits that change from each element to the next, and add this up for each element and its successor:
$$T(S) = \sum_{i=1}^{2^N} H(S_{i-1}, S_i)$$
where $H(x,y)$ is the Hamming distance between tuples $x$ and $y$, the number of positions in which they differ.  It's well known that this quantity $T(S)$ is minimized for certain  sequences ("Gray codes") in which each element of $S$ differs from its successor in exactly one bit.  So we have
$$m(N) = \min_{\text{all }S} T(S) = 2^N - 1$$
My question is:

What is the corresponding maximum value $$M(N) = \max_{\text{all }S} T(S)?$$

Small cases for $N\le3$ are easily seen to be 0, 1, 5, 18.  I did not see anything evident in OEIS about this.
A sequence $S$ contains $2^N-1$ transitions between elements, and it's tempting to conjecture that when $N>0$, half of these (rounded up) can change all $N$ bits and the other half (rounded down) can change all but one bit.  For example, when $N=3$ an "anti-Gray" sequence which does this is:
    000
    111
    100
    011
    110
    001
    010
    101

If this can be done for all $N$, then $$\begin{align}M(N) & = N\cdot2^{N-1} + (N-1)\cdot(2^{N-1}-1) \\& = N2^N - 2^{N-1}-N+1;
\end{align}$$ certainly this is true for $N\le 3$.  Is it true in general?
(I solved this problem before I finished writing  up the question, but I am posting it anyway per earlier discussions [1][2][3].)
 A: I would like to claim and prove the following:
Claim: 
"It is possible to construct Anti-Gray codes of length 'n'such that the consecutive elements in the sequence differ by exactly 'n-k' bits for all k >= 1"   
Proof:
I try to prove the above using induction on 'k'.
As a base inductive step, I would prove there is an anti-gray sequence of length 'n' which differ by exactly 'n-1' bits.
I show a construction of such a sequence using Gray codes of length 'n'. It is understood that Gray codes can be constructed for any 'n' such that the bits differ by exactly 1 bit. To construct an Anti-Gray sequence out of this Gray code sequence, we would "negate" every "alternate term" in the Gray code sequence. Let us consider terms '2t' and '2t-1' in this new sequence. Before, they were part of a Gray code sequence, and thus differed in exactly 1-bit. Since we have reversed all bits in '2t' (for ex), 2t and 2t-1 now differ in exactly 'n-1' bits. The same argument holds true for 2t and 2t+1. This construction is efficient, and takes exactly log(N) bits for representation.
Induction Hypothesis:
We assume the claim is true for all 'k' < K.
By Induction Hypothesis, there exists an Anti-Graty sequence:
   a1, a2, a3, ..., aN 
such that consequtive terms differ exactly by 'n-k' bits.
To construct a sequence which would differ in 'n-(k+1)' bits, we simply add a leading '0' or a '1' to every term in this sequence:
   0a1, 0a2, 0a3, ... 0aN.
This new sequence has now length 'n+1' and the consecutive elements differ by one less bit.
Hence by induction, the claim is true for all 'k'>=1 and the proof is complete.
Cheers!
A: The conjectured maximum $$M(N) = N\cdot2^{N-1} + (N-1)(2^{N-1}-1)$$ can be achieved for all positive $N$. I will demonstrate an example.  Suppose we want an anti-Gray sequence for $N=4$.  Then first construct a Gray sequence for $N-1$; for example:
    000
    001
    011
    010
    110
    111
    101
    100

append a 0 to each element of this sequence; the result is a Gray sequence on half of the $N=4$ space:
    0000
    0001
    0011
    0010
    0110
    0111
    0101
    0100

After each of these 8 items, insert the complementary item:
    0000
    1111
    0001
    1110
    0011
    1100
    0010
    1101
    0110
    1001
    0111
    1000
    0101
    1010
    0100
    1011

The result clearly includes each of the $2^4$ required items exactly once; half  the items are followed by their complements, from which they differ in every bit, and the other items are followed by items from which they differ in all but one bit. The construction obviously works for all positive $N$.
