Estoy pensando en este problema. ¿Podemos construir una secuencia infinita con $3$ números para que no existan partes repetidas en él? No debe haber subsecuencia con $2k$ números para que sus partes izquierda y derecha sean iguales. Esta es una secuencia de este tipo $1 0 1 2 0 2 1 0 2 0 1 0 2 1 0 1 2 0 2 1 $ . La pregunta es si podemos dar un algoritmo para que continúe hasta el infinito. Está claro que no podemos hacerlo si sólo hay $2$ números.
Respuestas
¿Demasiados anuncios?
Existe un resultado de Thue (1906) para construir explícitamente tales secuencias no repetitivas de cualquier longitud. Partiendo de cualquier secuencia inicial no repetitiva, por ejemplo la única $(1),$ uno reemplaza repetidamente (simultáneamente) cada ocurrencia de $1,2,3$ en la secuencia en una etapa determinada como sigue: $$1 \to 12312, \\ 2 \to 131232, \\ 3 \to 1323132.$$ Según el artículo aquí Se puede demostrar que la construcción de Thue produce una secuencia no repetitiva a partir de cualquier otra dada, es decir, en cada etapa la siguiente es no repetitiva siempre que la anterior lo sea.
Parece que (al menos a partir de la cadena inicial $(1),$ ) los continuos reemplazos hacen que la parte inicial de la cuerda empiece a asentarse, pero no he pensado mucho en "demostrar" eso. [En realidad, ahora no creo que pueda demostrarlo, puede que no sea cierto] El artículo enlazado trata de un enfoque diferente para producir estas secuencias, y sólo se refiere al resultado de Thue en la primera o segunda página.
Bogdan Enescu
Puntos
64
Se puede encontrar una prueba inductiva en http://goo.gl/OSzV1O (problema 124,b).
ArtW
Puntos
58
Aquí hay una construcción más simétrica, con pruebas:
Inductivamente, construiremos las palabras ternarias $W_{13^k}$ según las siguientes reglas: primero, coloreamos $W_1$ con $0$ . Dado $W_{13^k}$ , sustituimos cada letra $i\in\{0,1,2\}$ por la palabra $A_i$ , donde $$\begin{array}{cc} A_0&=0121021201210\\ A_1&=1202102012021\\ A_2&=2010210120102 \end{array}$$ Al inflar de esta manera obtenemos la palabra ternaria $W_{13^{k+1}}$ . La afirmación es que en cada etapa, este $W_{13^k}$ no tiene partes repetidas.
Para demostrar la afirmación, supongamos que tenemos el contraejemplo $WW\subset W_{13^k}$ , donde $W$ es una palabra. Podemos elegir $k$ para ser mínimo. Esto implica que $13$ no divide $|W|$ : en caso contrario, la secuencia de $A_i$ que cubren $WW$ es repetitivo. Esto implica que hemos encontrado un contraejemplo en $W_{13^{k-1}}$ contradiciendo la minimidad de $k$ .
Consideramos ahora dos casos.
Caso 1. Supongamos que hay algún $A_i$ tal que $A_i\subset W$ . Tenga en cuenta que si $U=abcbacbcabcba$ para $\{a,b,c\}=\{0,1,2\}$ tal que $U\subset A_jA_k$ (donde $j,k$ son números distintos en $\{0,1,2\}$ ), entonces $U=A_j$ o $U=A_k$ (véase el ejemplo siguiente para una ilustración). Por lo tanto, si consideramos la subpalabra en la segunda aparición de $W$ que corresponde al $A_i$ debe coincidir con otra palabra $A_j$ . Pero esto implica $13$ divide $|W|$ que ya hemos discutido.
ejemplo: búsqueda de subpalabras $abcbacbcabcba$ en $A_0A_1$ : \begin{array}{ccccccccccccccccccccccccccc} &0&1&2&1&0&2&1&2&0&1&2&1&0&1&2&0&2&1&0&2&0&1&2&0&2&1\\ & & & & &a&b&c&b&a&c&b&c&a&b&c&b&a& & & & & & & & & %\\ %& & & & & & & &a&b&c&b&a&c&b&c&a&b&c&b&a& & & & & \end{array}
Caso 2. Supongamos que $A_i\not\subset W$ para todos $i$ o, por el contrario $|W|\le 24$ . Para completar la prueba de la afirmación, basta con mostrar que todas las subpalabras pares de longitud hasta 48 de alguna $A_{i_1}A_{i_2}A_{i_3}A_{i_4}A_{i_5}$ son no repetitivos. Este es un problema finito y podemos comprobar estas posibilidades restantes (menos de 30000). $\square$
Definiciones usadas:
- Una palabra es una secuencia no vacía de símbolos.
- Si tenemos dos palabras $W,U$ denotamos $WU$ como la concatenación de las dos palabras.
- $W\subset U$ o $W$ es una subpalabra de $U$ si podemos encontrar una secuencia de símbolos consecutivos en $U$ es decir $W$ .
- Una palabra $U$ es repetitivo si contiene una subpalabra $WW$ donde $W$ es una palabra.
