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

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

Solution 2:

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!