Regalo estacional de los organizadores de la edición 2019 de la Olimpiada Internacional Se dirige a una edad de: 16-17 años
Una entrada es una cadena de ceros y unos.
A partir de ella, escribimos una fila de unos y ceros usando las reglas del triángulo de Pascal, donde cada uno de los números es suma de los dos situados en diagonal por encima suyo.
Trabajamos “módulo 2”, es decir, 1 + 1 = 0.
Repetimos el proceso hasta que formamos un triángulo de números.
Por ejemplo, si la entrada es 1 0 1 1 1, el triángulo sería el siguiente:
1 0 1 1 1
1 1 0 0
0 1 0
1 1
0
La salida de este procedimiento es la cadena de unos y ceros que se puede leer en el lado de este triángulo desde el extremo inferior hasta el extremo superior derecho, en ese orden. En nuestro ejemplo es 0 1 0 0 1.
Si decidimos empezar con una entrada de longitud n, hay 2n posibles cadenas de entrada.
¿Cuántas de esas cadenas tienen la propiedad de que son las mismas que su cadena de salida correspondiente?
No son necesarios cálculos complejos. Use sólo ideas hermosas.
Solución:
Voy a empezar por una solución que obtuve a base de pelearme con el problema. Sin embargo, hay una solución oficial, que realmente es muy curiosa (y hermosa) que cito al final.
Como siempre, empezamos a tratar con ejemplos, para generalizar a partir de ellos.
Los triángulos para n = 1 no tienen mucho interés. Pero, evidentemente, los dos posibles tienen esta propiedad, puesto que sólo hay un número en ambos lados (en los tres, de hecho) y es el mismo.
Los de n = 2, serían 4 triángulos posibles. De ellos, dos (correspondientes a la entrada 10 y 00) tienen la propiedad buscada y los otros dos no. Vamos a prestar atención a estos triángulos.
Los que si tienen la propiedad buscada:
0 0 0
1 0 1
Los que no la tienen
0 1 1
1 1 0
Observamos una cosa en todos los triángulos que sí tienen la propiedad que buscamos, y es que los triángulos en este caso son totalmente simétricos respecto a la mediatriz de su lado izquierdo. Llamaremos a dicha propiedad simetría. Luego demostraremos lo que hemos afirmado por mera observación.
Pasemos a estudiar los de n = 3. Hay 4, el doble que en el caso n = 2.
0 0 0
0 0
0
1 0 0
1 0
1
0 1 0
1 1
0
1 1 0
0 1
1
Por último, voy a mencionar los únicos 4 triángulos n = 4 que tienen simetría.
0 0 0 0
0 0 0
0 0
0
1 0 0 0
1 0 0
1 0
1
0 1 1 0
1 0 1
1 1
0
1 1 1 0
0 0 1
0 1
1
Para poder encontrar la relación clave, me he visto obligado a estudiar todos los de n = 6, y he llegado a algunos de los de n = 8, aunque pronto he aprendido a descartar los que no tienen simetría.
Observación 1: Si un triángulo tiene simetría, al suprimir el último número de la izquierda de cada fila obtenemos un triángulo con simetría.
Es evidente que sucede esto, ya que el valor de los números que quedan depende únicamente de los números que hay en la entrada, y si se cumple con la entrada larga, también se cumplirá con la corta.
Es decir, que para un valor determinado de n habrá, a lo sumo, el doble que para el anterior.
Observación 2: si el valor de n es par, y tenemos una entrada que produce un triángulo con simetría, entonces toda entrada formada por un 0 o un 1 a la izquierda de ese número producirá un triángulo con simetría, y éste será totalmente simétrico respecto a la mediatriz del lado izquierdo.
Hemos observado que pasa para el valor de n = 2. Supongamos que es cierto para un valor cualquiera de n (par) y demostremos que sucede así.
Al añadir un 0 o un 1 a la izquierda de la entrada, lo único que cambia en el triángulo es el último elemento de cada fila.
Observamos que hay simetría en el triángulo de entrada n, de forma que si n = 2k, añadiremos a las primeras k + 1 filas un elemento nuevo calculado a partir del primero, interactuando con los k segundos elementos de la fila. En la fila k + 2, se calculará el siguiente elemento usando el segundo elemento de la fila k + 1, que por propiedad de simetría, será el mismo que el de la fila k. Si es un 0, eso dejará el número igual, pero será lo mismo que sucedió al pasar de la fila k a la k + 1, por lo que el primer número de la fila k + 2 será el mismo de la fila k. De la misma manera, si es un 1, cambiará el número de la fila k + 2 respecto al primero de la k + 1, pero será lo mismo que sucedió al pasar de la fila k a la k + 1, por lo que de nuevo se tratará del mismo elemento en la fila k + 2 que en la k + 1.
De esta forma, repitiendo el razonamiento, toda la nueva fila de primeros elementos será simétrica, con lo que el triángulo entero será simétrico respecto a la bisectriz del lado izquierdo, y en particular la salida será idéntica a la entrada.
Observación 3: Si n es par, y añadimos un 0 a la izquierda, obtenemos un primer elemento diferente en cada fila que si añadimos un 1.
Por la forma de operar, es evidente, ya que 0 + 1 = 1 + 0, mientras que 0 + 0 = 1 + 1. De esta forma, al cambiar la primera cifra, cambiaremos todas las primeras cifras.
Ahora vienen las observaciones más complicadas.
Observación 4: Si n es impar y una entrada que genera un triángulo con simetría, y el último número a la izquierda de la fila central del triángulo es un 0, entonces toda entrada formada por un 0 o un 1 a la izquierda de ese número producirá un triángulo con simetría, y éste será totalmente simétrico respecto a la mediatriz del lado izquierdo.
Observa que eso quiere decir que toda entrada derivada de una entrada que tenga esta extraña propiedad, añadiendo un cero o un uno a la izquierda, será del mismo tipo (y, evidentemente, par).
Hemos visto que sucede en el caso n = 1 (si sólo hay un 0). Pero podemos observarlo en el caso n = 3, observa que los triángulos de las entradas 000 y 110 tienen esta propiedad, y podemos construir triángulos simétricos con 0000 y 1000 y también con 0110 y con 1110.
¿Por qué sucede esto?
Supongamos que n = 2k + 1, el segundo elemento de la fila k + 1 es un cero. Pongamos un cero o un 1, se forma una cadena de primeros elementos hasta la fila k + 1 interactuando con los segundos elementos. Puesto que el segundo elemento de la fila k + 1 es 0, el primero de la fila k + 2 es igual que el de la fila k + 1. A partir de ahí, interactúa con el segundo elemento de la fila k + 2 para conseguir el primero de la k + 3. Como este segundo elemento es el mismo que el de la fila k, por la simetría del triángulo que hemos supuesto, el primero de la k + 3 coincide con el primero de la k, y así sucede respectivamente con toda la cadena, incluyendo el primer elemento de la nueva fila k + 2, que coincidirá con el primero de la primera fila. Por lo tanto, el triángulo será totalmente simétrico respecto a la mediatriz del lado izquierdo, y tendrá simetría.
Observación 5: Si n es impar y una entrada que genera un triángulo con simetría, y el último número a la izquierda de la fila central del triángulo es un 1, entonces toda entrada formada por un 0 o un 1 a la izquierda de ese número producirá un triángulo que no tendrá simetría.
El razonamiento es muy similar. Supongamos que n = 2k + 1, el segundo elemento de la fila k + 1 es un uno. Pongamos un cero o un 1, se forma una cadena de primeros elementos hasta la fila k + 1 interactuando con los segundos elementos. Puesto que el segundo elemento de la fila k + 1 es 1, el primero de la fila k + 2 es contrario al de la fila k + 1. A partir de ahí, interactúa con el segundo elemento de la fila k + 2 para conseguir el primero de la k + 3. Como este segundo elemento es el mismo que el de la fila k, por la simetría del triángulo que hemos supuesto, el primero de la k + 3 es el contrario que el primero de la k, y así sucede respectivamente con toda la cadena, incluyendo el primer elemento de la nueva fila k + 2, que será el contrario que el primero de la primera fila. Por lo tanto, el ultimo lado del triángulo será totalmente antisimétrico respecto a la mediatriz del lado izquierdo, el último número no coincidirá con el primero.
Bueno, pues con estas 5 observaciones ya podemos razonar.
Si n es par, n = 2k, entonces el número de cadenas que tienen esta propiedad es exactamente 2k.
Si n es impar, n = 2k + 1, entonces el número de cadenas que tienen esta propiedad es exactamente 2k + 1.
Podemos demostrarlo por inducción. Según hemos visto, se cumple para los casos n = 1, 2, 3 y 4, es decir, para los valores de k 1 y 2 (n par) y 0 y 1 (n impar).
Supongamos que es cierto hasta un determinado valor de n.
Si n es par, tendremos entonces que n = 2k, y habrá 2k cadenas que formarán triángulos con esta propiedad.
Cualquier cadena, por la Observación 1, de n + 1 elementos, contiene una subcadena a la derecha de n elementos que tiene esta propiedad, por lo que a lo sumo hay 2·2k = 2k + 1 cadenas que tienen esta propiedad, pero por la Observación 2, podemos construir exactamente 2k + 1 cadenas con esta propiedad, así que el valor buscado para n = 2 k + 1 es 2k + 1.
Según hemos visto en la Observación 3, la mitad de ellas tendrán un 1 como primer elemento de la fila central, y la otra mitad, un cero (puesto que según hayamos empezado con un 0 o con un 1 serán todos los primeros números diferentes).
Si n es impar, entonces n = 2k + 1, y habrá 2k + 1 cadenas que formarán triángulos con esta propiedad. Además, según hemos visto, la mitad tendrá un 1 como primer elemento de la fila k + 1, y la otra mitad un cero. A partir de las que tienen un cero, que serán exactamente 2k, podemos construir el doble de entradas, según hemos visto en la observación 4, el doble de entradas de longitud n + 1 que tienen simetría, es decir, 2k + 1, y de las que tienen un 1 no podremos obtener ninguna (según la observación 5). Puesto que toda entrada de tamaño n + 1 con la propiedad tiene n elementos a la derecha que forman una entrada con la propiedad, para n + 1 = 2 k + 2 = 2 (k + 1) habrá exactamente 2k + 1 entradas con esa propiedad, como queríamos demostrar.
La solución oficial se basa en la simetría, pero utiliza un argumento realmente hermoso. Si giramos 60 grados el triángulo, obtenemos un triángulo simétrico, y las reglas de formación son exactamente las mismas (fíjate en que esto sucede debido a las peculiares propiedades de la suma con “módulo 2”). Para que en un triángulo el lado izquierdo y el derecho sean exactamente iguales, la entrada ahora (que en el triángulo original era la cadena que se veía a la izquierda, a la que no le habíamos prestado prácticamente atención) debe ser también simétrica. Cualquier falta de simetría provoca una diferencia entre los dos lados. Por tanto, sólo hay que contar cuántas entradas son capicúas (es decir, palindrómicas, o simétricas). Y coincide el número con lo que había observado anteriormente.