Anti-"Gris códigos" maximizar el número de bits que cambian a cada paso

Question

Deje $N$ ser un entero no negativo y deje $S$ ser algunos pedidos de la $2^N$ diferentes $N$-tuplas de dígitos binarios. Podemos mirar el número de bits que cambian de cada elemento a la siguiente, y agregar esto para cada elemento y su sucesor:

$$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 $s$, 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$$

Mi pregunta es:

¿Cuál es el correspondiente valor máximo $$M(N) = \max_{\text{all }S} T(S)?$$

La pequeña de los casos de $N\le3$ son fácilmente apreciables a ser 0, 1, 5, 18. Yo no veo nada evidente en OEIS acerca de esto.

Una secuencia $S$ contiene $2^N-1$ transiciones entre los elementos, y es tentador suponer que al $N>0$, la mitad de estos (redondeado hacia arriba) puede cambiar todos los $N$ bits y la otra mitad (redondeando hacia abajo) puede cambiar todo pero un poco. Por ejemplo, cuando se $N=3$ 'anti-Gris" de la secuencia que hace es:

    000
    111
    100
    011
    110
    001
    010
    101

Si esto puede ser hecho por todos los $N$, $$\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$. Es cierto en general?

(He resuelto este problema antes de terminar de escribir la pregunta, pero estoy publicando todos modos por los debates anteriores [1][2][3].)

Answer 1

El conjetural máximo $$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$.

Answer 2

Me gustaría reclamar y demostrar los siguientes:

Reclamo: "Es posible construir Anti-Gris códigos de longitud 'n'such que los elementos consecutivos en la secuencia difieren en exactamente n-k bits que para todo k >= 1"

Prueba:

Yo intente demostrar lo anterior, usando inducción sobre k'.

Como una base inductiva paso, me gustaría demostrar que hay una anti-gris secuencia de longitud n que se diferencian por exactamente 'n-1' bits.

Muestro la construcción de una secuencia utilizando Gris códigos de longitud 'n'. Se entiende que el Gris de los códigos puede ser construido para cualquier 'n' tal que los bits se diferencian por exactamente 1 bit. Para la construcción de un Anti-Gris de la secuencia de salida de este Gris secuencia de código, "negar" cada "término alternativo" en el Gris de la secuencia de código. Vamos a considerar los términos '2t' y '2t-1' en esta nueva secuencia. Antes, eran parte de un código Gray de la secuencia, y por lo tanto difieren en exactamente 1-bit. Ya hemos invertido todos los bits en '2t' (ex), 2t y 2t-1 ahora difieren en exactamente n-1 bits. El mismo argumento vale para el 2t y 2t+1. Esta construcción es eficiente, y tarda exactamente log(N) bits para la representación.

Inducción Hipótesis: Podemos suponer que la afirmación es verdadera para todos los 'k' < K. Por Hipótesis de Inducción, existe un Anti-Graty secuencia: a1, a2, a3, ..., aN tal que consecutivo términos difieren exactamente por 'n-k bits. Para la construcción de una secuencia que se diferencian en 'n-(k+1)' bits, sólo tenemos que añadir una de las principales '0' o un '1' para cada término de esta secuencia: 0a1, 0a2, 0a3, ... 0aN. Esta nueva secuencia tiene ahora la longitud de 'n+1' y el consecutivo de los elementos difieren en un bit menos. Por lo tanto, por inducción, la afirmación es verdadera para todos los 'k'>=1 y la prueba está completa.

Saludos!