La mitad de cualquier $2n$ pero no $2n+2$

Question

Dejemos que $n$ sea un número entero positivo. ¿Cuál es la longitud de la secuencia más larga posible de $0$ y $1$ de tal manera que entre cualquier $2n$ números consecutivos, exactamente la mitad son $0$ pero entre cualquier $2n+2$ consecutivo, esto no es cierto?

Es posible tener una secuencia de longitud $3n$ : $11\dots100\dots011\dots1$ . Además, después de la primera $2n$ números el resto son fijos: el $(2n+i)$ debe ser el mismo que el número $i$ el número.

Answer 1

Supongamos que el $2n$ los bits son $b_1b_2\ldots b_{2n}$ , $n$ de ellos siendo $0$ y el otro $n$ ser $1$ . Supongamos que ampliamos esto a $3n+1$ bits:

$$b_1b_2\ldots b_{2n}b_{2n+1}\ldots b_{3n}b_{3n+1}=b_1b_2\ldots b_{2n}b_1\ldots b_nb_{n+1}$$

Debe haber una $k$ tal que $1\le k<2n$ y $b_k\ne b_{k+1}$ . Consideremos ahora la cadena $\sigma$ de longitud $2n+2$ empezando por $b_k$ : el $2n$ bits de $b_{k+1}$ a través de $b_{k+2n}=b_k$ tiene $n$ ceros y $n$ unos, y los bits adicionales son $b_k$ y $b_{k+1+2n}=b_{k+1}$ que son desiguales, por lo que $\sigma$ tiene $n+1$ ceros y $n+1$ los. Así, $3n$ es el máximo posible.

Answer 2

Empezamos con cualquier cadena $S = a_1a_2\dots a_{2n}$ de $n$ ceros y $n$ los.

Entonces debemos tener $a_k = a_{2n+k}$ . Además, debemos tener $a_{2n+1} = a_{2n+2}$ o bien la primera $2n+2$ las letras tienen la misma proporción.

Entonces también debemos tener $a_{2n+2} = a_{2n+3}$ por la misma lógica, ya que la subcadena $a_2 a_3 \dots a_{2n+1}$ tiene una proporción igual de ceros y unos. En particular, debemos tener $a_{2n+1}=a_{2n+2}=\dots$ . El mayor tiempo que podemos tener ambos $a_k = a_{2n+k}$ y esta condición es si el primer $n$ las cartas son $1$ (o $0$ ) y el siguiente $n$ son $0$ (o $1$ ) y el último $n$ son $1$ (o $0$ ) de nuevo. Por lo tanto, $3n$ es la secuencia más larga.