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:
Continue reading Solución a triángulo de Pascal binario
