"Anti-Gray codes" that maximize the number of bits that change at each step

Question

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].)

Answer 1

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$.