Números pares e impares en el triángulo de Pascal-Triángulo de Sierpinski

Question

Nota del moderador: En el momento en que se publicó esta pregunta, era parte de un concurso en curso. La fecha límite relevante ya ha pasado.

Recientemente aprendí que cuando el triángulo de Pascal se reduce a paridad (es decir, los términos pares se representan como 0, los términos impares se representan como 1), el resultado es una figura que se asemeja al triángulo de Sierpinski en su patrón. Esto me pareció un resultado muy fascinante. Luego comencé a notar algunas secuencias, como secuencias particulares de ceros y unos que aparecen en varias filas.

Una observación que hice es que como el triángulo de Pascal es simétrico por medio de $\binom{n}{m}= \binom{n}{n-m}$, el reverso de cualquier secuencia de 0s y 1s que aparezca en esta versión del triángulo de Pascal también aparecerá. Al observar varias secuencias, las secuencias más cortas que no parecen aparecer son $1101$ y su reverso, $1011$. Intenté entonces probar dos cosas. Primero, quería probar que estas secuencias nunca aparecerían en el 'triángulo de Pascal de paridad'. Puedo ver intuitivamente por qué nunca aparecerían: si dividimos el triángulo de Sierpinski en etapas de sí mismo, vemos que la secuencia $101$ solo aparece en la fila central de la segunda etapa del fractal, y dado que la $n$-ésima etapa del fractal solo aparece como parte de la $n+1$-ésima etapa del fractal, esta secuencia siempre será seguida por el centro de ceros de otra etapa del fractal. De manera similar, cualquier secuencia $100...11$ puede aparecer, pero $1011,100011, 1000000011$, y así sucesivamente con el número de ceros siendo de la forma $2^n-1$ no pueden aparecer. Como dije, intuitivamente esto se debe a que $2^n-1$ ceros encerrados por dos unos aparecen en lugares donde uno de los dos unos está en el borde del fractal y el otro en el borde del triángulo central de ceros en alguna etapa del fractal. Para ejemplos de esto sucediendo, ver la fila inferior del diagrama, la tercera fila del diagrama, la quinta fila del diagrama, la novena fila del diagrama. ¿Alguien puede formalizar este argumento en una prueba completa y general de mi afirmación?

De manera similar, para cualquier tamaño de secuencia, ¿cómo podemos describir de manera más explícita todas las secuencias que aparecen en este triángulo de Pascal de paridad o, más fácilmente, que no aparecen en él? Y para cualquier tamaño de secuencia, ¿cómo podemos enumerar las secuencias que aparecen?

---

Si alguien pudiera dar una prueba y explicación más directa y explícita para las relaciones módulo 2 que menciona Micah (ya sea haciéndolo explícito en términos del teorema de Lucas o no) y por qué las reglas pueden determinar si una cadena está en el triángulo de Pascal módulo 2 de la forma en que lo hacen, ¡sería fantástico! No estoy seguro de entender de dónde vienen, por más interesantes que sean.

Answer 1

Todo lo siguiente se cumple módulo 2 (puedes pensar en ellos como un caso especial del teorema de Lucas, o simplemente probarlos directamente):

$$ {2a \choose 2b} \equiv {a \choose b}, \mbox{ y } {2a \choose 2b+1} \equiv 0\\ {2a+1 \choose 2b} \equiv {2a+1 \choose 2b+1} \equiv {a \choose b} \, . $$

Usando estos, puedes verificar recursivamente si alguna secuencia de bits dada $B=(b_1,b_2,\dots,b_k)$ podría ocurrir:

1. Para que $B$ ocurra en una fila par del triángulo, cada otro bit en $B$ debe ser $0$: es decir, $B=(0,b_2,0,b_4,\dots)$ o $B=(b_1,0,b_3,0,\dots)$. Tal $B$ ocurrirá en alguna fila par si la secuencia acortada $(b_2,b_4,\dots)$ o $(b_1,b_3,\dots)$ ocurre en alguna fila del triángulo.
2. Para que $B$ ocurra en una fila impar del triángulo, los bits en $B$ deben ser iguales en pares adyacentes: es decir, $B=(b_1, b_1, b_3, b_3, \dots)$, o $B=(b_1, b_2, b_2, b_4, b_4, \dots)$. Tal $B$ ocurrirá en alguna fila impar si la secuencia acortada $(b_1,b_3,b_5,\dots)$ o $(b_1,b_2, b_4, b_6,\dots)$ ocurre en alguna fila del triángulo.

Cada aplicación de una de estas reglas aproximadamente reducirá a la mitad la longitud de $B$; si ninguna regla puede aplicarse en ningún paso, eliminamos $B$ de consideración. Por lo tanto, si no eliminas $B$ de consideración, terminarás con la cadena trivial $1$ (que se envía a sí misma mediante ambas reglas, y claramente aparece en el triángulo).

Aplicando este algoritmo, podemos ver que tu $1101$ falla inmediatamente; no consiste ni de repeticiones ni de algo rellenado con ceros. Los otros ejemplos específicos sobre los que preguntas fallarán por razones similares. Cualquier secuencia con dos $1$ adyacentes no puede tener la regla 1. aplicada: eso significa que ya es imposible que cada otro bit sea un $0$. Además, cualquier secuencia con una racha de longitud impar de unos o ceros no puede tener la regla 2. aplicada, a menos que la racha comience o termine la secuencia; esto hace imposible emparejar los bits entre sí. Dado que tus secuencias terminan con dos $1$s, y tienen una racha de $2^n-1$ ceros en el medio, ninguna regla se les puede aplicar, por lo que no pueden estar en el triángulo.

Por otro lado, algo como $101000001$ pasa, a través de la secuencia de transformaciones $$ 101000001 \to^1 11001 \to^2 101 \to^1 11 \to^2 1 \, . $$

Si deseas enumerar todas las secuencias que aparecen en algún lugar, puedes aplicar estas dos reglas en reversa. Para una secuencia dada $B=(b_1,b_2,\dots,b_k)$, ¿cómo podría haber sido producida a partir de las reglas 1. y 2.?

1. $B$ podría haber sido producida a partir de la regla 1. por cualquiera de cuatro cadenas de bits: $(0, b_1, 0, b_2, \dots, 0, b_k, 0)$, $(0, b_1, 0, b_2, \dots, 0, b_k)$, $(b_1, 0, b_2, \dots, 0, b_k, 0)$, o $(b_1, 0, b_2, \dots, 0, b_k)$.

2. $B$ también podría haber sido producida a partir de la regla 2. por cualquiera de cuatro cadenas de bits: $(b_1, b_1, b_2, b_2, \dots, b_k, b_k)$, $(b_1, b_2, b_2, \dots, b_k, b_k)$, $(b_1, b_1, b_2, b_2, \dots,b_{k-1}, b_{k-1}, b_k)$, o $(b_1, b_2, b_2, \dots, b_{k-1}, b_{k-1}, b_k)$.

En ambos casos, hay una cadena más larga que puede ser producida (la primera enumerada), y tres otras cadenas que pueden obtenerse de la cadena más larga al eliminar su primer o último elemento, o ambos.

Por ejemplo, si empezamos con la cadena $1011$, podemos aplicar la regla 1. en reversa para obtener las cadenas $010001010$, $10001010$, $01000101$, y $1000101$. Podemos aplicar la regla 2. en reversa para obtener las cadenas $11001111$, $1001111$, $1100111$, y $100111$.

Sabemos que, para cualquier cadena que aparezca en el triángulo, podemos aplicar repetidamente las reglas 1. y 2. hasta que se obtenga la cadena $1$. Por lo tanto, debemos poder obtener todas las cadenas posibles aplicando repetidamente las versiones en reversa de las reglas 1. y 2. a la cadena $1$. Además, cada regla en reversa va desde una cadena de longitud $k$ hasta una cadena de longitud de al menos $2k-2$. Entonces, si deseamos encontrar todas las cadenas de longitud $k$, solo tendremos que aplicar el algoritmo hasta que las cadenas más cortas que se producen en cualquier etapa dada sean de longitud al menos $k$, y esto tomará aproximadamente $\log_2 k$ pasos.

Para ser precisos, si empezamos con una cadena de longitud $3$, podemos llegar a una cadena de longitud de hasta $2^n+2$ en $n$ pasos. Nuestro algoritmo comienza a ser un poco más complicado para cadenas más cortas que eso, pero puedes enumerar todas las posibilidades y ver que cada cadena de longitud $3$ es obtenible a partir de la cadena $1$ en a lo sumo $2$ pasos. Entonces, cualquier cadena de longitud de hasta $2^n+2$ puede obtenerse en a lo sumo $n+2$ pasos, lo que significa que cualquier cadena de longitud $k$ puede obtenerse en a lo sumo $\left\lceil\log_2(k-2)+2\right\rceil$ pasos.

Esto ya nos da un algoritmo bastante bueno para enumerar todas las cadenas posibles. Pero podemos mejorar. La implicación de todo lo anterior es que cualquier secuencia proviene de un $1$ flotando en alguna parte del triángulo. Pero no importa qué $1$ usemos como punto de partida, terminaremos con el mismo conjunto de cadenas de bits (siempre que adoptemos la convención estándar de que ${a \choose b}=0$ cuando $b<0$ o $b>a$; de lo contrario, algunas de las secuencias que producimos podrían salirse de los límites).

Por lo tanto, podríamos imaginar que estamos empezando con el $1$ en la parte superior del triángulo, en la fila $0$. Según el argumento original del teorema de Lucas, cada paso nos llevará, como máximo, de la fila $n$ del triángulo a la fila $2n+1$. Entonces, después de $t$ pasos, estaremos, como máximo, en la fila $2^t-1$. Dado que $\left\lceil\log_2(k-2)+2\right\rceil$ pasos son suficientes para producir todas las cadenas de longitud $k$, vemos que cada cadena de longitud $k$ que ocurra, ocurrirá antes de la fila $$ 2^\left\lceil\log_2(k-2)+2\right\rceil-1<8k \, , $$ para dar un límite superior burdo que probablemente se pueda mejorar.

En resumen, cada cadena de bits de longitud $k$ que aparezca en la versión módulo 2 del triángulo de Pascal ocurrirá en alguna parte de las primeras $8k$ filas. Por lo tanto, puedes enumerarlas todas simplemente calculando las primeras $8k$ filas del triángulo de Pascal y observando todas las subcadenas de $k$ elementos del resultado (recordando colocar ceros suficientes a la izquierda y a la derecha del triángulo). Creo que esta es una forma mucho mejor de hacer las cosas que mi otro algoritmo (que básicamente se reducía a calcular bits del triángulo de Pascal de todos modos...)