{"id":974,"date":"2019-01-12T10:54:54","date_gmt":"2019-01-12T10:54:54","guid":{"rendered":"https:\/\/blogs.ua.es\/dimates\/?p=974"},"modified":"2019-01-12T19:35:20","modified_gmt":"2019-01-12T19:35:20","slug":"solucion-a-triangulo-de-pascal-binario","status":"publish","type":"post","link":"https:\/\/blogs.ua.es\/dimates\/2019\/01\/12\/solucion-a-triangulo-de-pascal-binario\/","title":{"rendered":"Soluci\u00f3n a tri\u00e1ngulo de Pascal binario"},"content":{"rendered":"
Regalo estacional de los organizadores de la edici\u00f3n 2019 de la Olimpiada Internacional\r\nSe dirige a una edad de: 16-17 a\u00f1os<\/pre>\n
Una entrada es una cadena de ceros y unos.<\/p>\n
A partir de ella, escribimos una fila de unos y ceros usando las reglas del tri\u00e1ngulo de Pascal, donde cada uno de los n\u00fameros es suma de los dos situados en diagonal por encima suyo.<\/p>\n
Trabajamos \u201cm\u00f3dulo 2\u201d, es decir, 1 + 1 = 0.<\/p>\n
Repetimos el proceso hasta que formamos un tri\u00e1ngulo de n\u00fameros.<\/p>\n
Por ejemplo, si la entrada es 1 0 1 1 1, el tri\u00e1ngulo ser\u00eda el siguiente:<\/p>\n
1   0   1   1   1\r\n  1   1   0   0\r\n    0   1   0\r\n      1   1\r\n        0<\/pre>\n
La salida de este procedimiento es la cadena de unos y ceros que se puede leer en el lado de este tri\u00e1ngulo desde el extremo inferior hasta el extremo superior derecho, en ese orden. En nuestro ejemplo es 0 1 0 0 1.<\/p>\n
Si decidimos empezar con una entrada de longitud n, hay 2n<\/sup> posibles cadenas de entrada.<\/p>\n
\u00bfCu\u00e1ntas de esas cadenas tienen la propiedad de que son las mismas que su cadena de salida correspondiente?<\/p>\n
No son necesarios c\u00e1lculos complejos. Use s\u00f3lo ideas hermosas.
\n\"\"
\nSoluci\u00f3n:
\n
\nVoy a empezar por una soluci\u00f3n que obtuve a base de pelearme con el problema. Sin embargo, hay una soluci\u00f3n oficial, que realmente es muy curiosa (y hermosa) que cito al final.<\/p>\n
Como siempre, empezamos a tratar con ejemplos, para generalizar a partir de ellos.<\/p>\n
Los tri\u00e1ngulos para n = 1 no tienen mucho inter\u00e9s. Pero, evidentemente, los dos posibles tienen esta propiedad, puesto que s\u00f3lo hay un n\u00famero en ambos lados (en los tres, de hecho) y es el mismo.<\/p>\n
Los de n = 2, ser\u00edan 4 tri\u00e1ngulos posibles. De ellos, dos (correspondientes a la entrada 10 y 00) tienen la propiedad buscada y los otros dos no. Vamos a prestar atenci\u00f3n a estos tri\u00e1ngulos.<\/p>\n
Los que si tienen la propiedad buscada:<\/p>\n
0   0\r\n  0<\/pre>\n
1   0\r\n  1<\/pre>\n
Los que no la tienen<\/p>\n
0   1\r\n  1<\/pre>\n
1   1\r\n  0<\/pre>\n
Observamos una cosa en todos los tri\u00e1ngulos que s\u00ed tienen la propiedad que buscamos, y es que los tri\u00e1ngulos en este caso son totalmente sim\u00e9tricos respecto a la mediatriz de su lado izquierdo. Llamaremos a dicha propiedad simetr\u00eda. Luego demostraremos lo que hemos afirmado por mera observaci\u00f3n.<\/p>\n
Pasemos a estudiar los de n = 3. Hay 4, el doble que en el caso n = 2.<\/p>\n
0   0   0\r\n  0   0\r\n    0<\/pre>\n
1   0   0\r\n  1   0\r\n    1<\/pre>\n
0   1   0\r\n  1   1\r\n    0<\/pre>\n
1   1   0\r\n  0   1\r\n    1<\/pre>\n
Por \u00faltimo, voy a mencionar los \u00fanicos 4 tri\u00e1ngulos n = 4 que tienen simetr\u00eda.<\/p>\n
0   0   0   0\r\n  0   0   0\r\n    0   0\r\n      0<\/pre>\n
1   0   0   0\r\n  1   0   0\r\n    1   0\r\n      1<\/pre>\n
0   1   1   0\r\n  1   0   1\r\n    1   1\r\n      0<\/pre>\n
1   1   1   0\r\n  0   0   1\r\n    0   1\r\n      1<\/pre>\n
Para poder encontrar la relaci\u00f3n 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\u00eda.<\/p>\n
Observaci\u00f3n 1: Si un tri\u00e1ngulo tiene simetr\u00eda, al suprimir el \u00faltimo n\u00famero de la izquierda de cada fila obtenemos un tri\u00e1ngulo con simetr\u00eda.<\/p>\n
Es evidente que sucede esto, ya que el valor de los n\u00fameros que quedan depende \u00fanicamente de los n\u00fameros que hay en la entrada, y si se cumple con la entrada larga, tambi\u00e9n se cumplir\u00e1 con la corta.<\/p>\n
Es decir, que para un valor determinado de n habr\u00e1, a lo sumo, el doble que para el anterior.<\/p>\n
Observaci\u00f3n 2: si el valor de n es par, y tenemos una entrada que produce un tri\u00e1ngulo con simetr\u00eda, entonces toda entrada formada por un 0 o un 1 a la izquierda de ese n\u00famero producir\u00e1 un tri\u00e1ngulo con simetr\u00eda, y \u00e9ste ser\u00e1 totalmente sim\u00e9trico respecto a la mediatriz del lado izquierdo.<\/p>\n
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\u00ed.<\/p>\n
Al a\u00f1adir un 0 o un 1 a la izquierda de la entrada, lo \u00fanico que cambia en el tri\u00e1ngulo es el \u00faltimo elemento de cada fila.<\/p>\n
Observamos que hay simetr\u00eda en el tri\u00e1ngulo de entrada n, de forma que si n = 2k, a\u00f1adiremos 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\u00e1 el siguiente elemento usando el segundo elemento de la fila k  + 1, que por propiedad de simetr\u00eda, ser\u00e1 el mismo que el de la fila k. Si es un 0, eso dejar\u00e1 el n\u00famero igual, pero ser\u00e1 lo mismo que sucedi\u00f3 al pasar de la fila k a la k + 1, por lo que el primer n\u00famero de la fila k + 2 ser\u00e1 el mismo de la fila k. De la misma manera, si es un 1, cambiar\u00e1 el n\u00famero de la fila k + 2 respecto al primero de la k + 1, pero ser\u00e1 lo mismo que sucedi\u00f3 al pasar de la fila k a la k + 1, por lo que de nuevo se tratar\u00e1 del mismo elemento en la fila k + 2 que en la k + 1.<\/p>\n
De esta forma, repitiendo el razonamiento, toda la nueva fila de primeros elementos ser\u00e1 sim\u00e9trica, con lo que el tri\u00e1ngulo entero ser\u00e1 sim\u00e9trico respecto a la bisectriz del lado izquierdo, y en particular la salida ser\u00e1 id\u00e9ntica a la entrada.<\/p>\n
Observaci\u00f3n 3: Si n es par, y a\u00f1adimos un 0 a la izquierda, obtenemos un primer elemento diferente en cada fila que si a\u00f1adimos un 1.<\/p>\n
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.<\/p>\n
Ahora vienen las observaciones m\u00e1s complicadas.<\/p>\n
Observaci\u00f3n 4: Si n es impar y una entrada que genera un tri\u00e1ngulo con simetr\u00eda, y el \u00faltimo n\u00famero a la izquierda de la fila central del tri\u00e1ngulo es un 0, entonces toda entrada formada por un 0 o un 1 a la izquierda de ese n\u00famero producir\u00e1 un tri\u00e1ngulo con simetr\u00eda, y \u00e9ste ser\u00e1 totalmente sim\u00e9trico respecto a la mediatriz del lado izquierdo.<\/p>\n
Observa que eso quiere decir que toda entrada derivada de una entrada que tenga esta extra\u00f1a propiedad, a\u00f1adiendo un cero o un uno a la izquierda, ser\u00e1 del mismo tipo (y, evidentemente, par).<\/p>\n
Hemos visto que sucede en el caso n = 1 (si s\u00f3lo hay un 0). Pero podemos observarlo en el caso n = 3, observa que los tri\u00e1ngulos de las entradas 000 y 110 tienen esta propiedad, y podemos construir tri\u00e1ngulos sim\u00e9tricos con 0000 y 1000 y tambi\u00e9n con 0110 y con 1110.<\/p>\n
\u00bfPor qu\u00e9 sucede esto?<\/p>\n
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\u00ed, interact\u00faa 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\u00eda del tri\u00e1ngulo que hemos supuesto, el primero de la k + 3 coincide con el primero de la k, y as\u00ed sucede respectivamente con toda la cadena, incluyendo el primer elemento de la nueva fila k + 2, que coincidir\u00e1 con el primero de la primera fila. Por lo tanto, el tri\u00e1ngulo ser\u00e1 totalmente sim\u00e9trico respecto a la mediatriz del lado izquierdo, y tendr\u00e1 simetr\u00eda.<\/p>\n
Observaci\u00f3n 5: Si n es impar y una entrada que genera un tri\u00e1ngulo con simetr\u00eda, y el \u00faltimo n\u00famero a la izquierda de la fila central del tri\u00e1ngulo es un 1, entonces toda entrada formada por un 0 o un 1 a la izquierda de ese n\u00famero producir\u00e1 un tri\u00e1ngulo que no tendr\u00e1 simetr\u00eda.<\/p>\n
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\u00ed, interact\u00faa 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\u00eda del tri\u00e1ngulo que hemos supuesto, el primero de la k + 3 es el contrario que el primero de la k, y as\u00ed sucede respectivamente con toda la cadena, incluyendo el primer elemento de la nueva fila k + 2, que ser\u00e1 el contrario que el primero de la primera fila. Por lo tanto, el ultimo lado del tri\u00e1ngulo ser\u00e1 totalmente antisim\u00e9trico respecto a la mediatriz del lado izquierdo, el \u00faltimo n\u00famero no coincidir\u00e1 con el primero.<\/p>\n
Bueno, pues con estas 5 observaciones ya podemos razonar.<\/p>\n
Si n es par, n = 2k, entonces el n\u00famero de cadenas que tienen esta propiedad es exactamente 2k<\/sup>.<\/p>\n
Si n es impar, n = 2k + 1, entonces el n\u00famero de cadenas que tienen esta propiedad es exactamente 2k + 1<\/sup>.<\/p>\n
Podemos demostrarlo por inducci\u00f3n. Seg\u00fan 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).<\/p>\n
Supongamos que es cierto hasta un determinado valor de n.<\/p>\n
Si n es par, tendremos entonces que n = 2k, y habr\u00e1 2k<\/sup> cadenas que formar\u00e1n tri\u00e1ngulos con esta propiedad.<\/p>\n
Cualquier cadena, por la Observaci\u00f3n 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\u00b72k<\/sup> = 2k + 1<\/sup> cadenas que tienen esta propiedad, pero por la Observaci\u00f3n 2, podemos construir exactamente 2k + 1<\/sup> cadenas con esta propiedad, as\u00ed que el valor buscado para n = 2 k + 1 es 2k + 1<\/sup>.<\/p>\n
Seg\u00fan hemos visto en la Observaci\u00f3n 3, la mitad de ellas tendr\u00e1n un 1 como primer elemento de la fila central, y la otra mitad, un cero (puesto que seg\u00fan hayamos empezado con un 0 o con un 1 ser\u00e1n todos los primeros n\u00fameros diferentes).<\/p>\n
Si n es impar, entonces n = 2k + 1, y habr\u00e1 2k + 1<\/sup> cadenas que formar\u00e1n tri\u00e1ngulos con esta propiedad. Adem\u00e1s, seg\u00fan hemos visto, la mitad tendr\u00e1 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\u00e1n exactamente 2k<\/sup>, podemos construir el doble de entradas, seg\u00fan hemos visto en la observaci\u00f3n 4, el doble de entradas de longitud n + 1 que tienen simetr\u00eda, es decir, 2k + 1<\/sup>, y de las que tienen un 1 no podremos obtener ninguna (seg\u00fan la observaci\u00f3n 5). Puesto que toda entrada de tama\u00f1o 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\u00e1 exactamente 2k + 1<\/sup> entradas con esa propiedad, como quer\u00edamos demostrar.<\/p>\n
La soluci\u00f3n oficial se basa en la simetr\u00eda, pero utiliza un argumento realmente hermoso. Si giramos 60 grados el tri\u00e1ngulo, obtenemos un tri\u00e1ngulo sim\u00e9trico, y las reglas de formaci\u00f3n son exactamente las mismas (f\u00edjate en que esto sucede debido a las peculiares propiedades de la suma con “m\u00f3dulo 2”). Para que en un tri\u00e1ngulo el lado izquierdo y el derecho sean exactamente iguales, la entrada ahora (que en el tri\u00e1ngulo original era la cadena que se ve\u00eda a la izquierda, a la que no le hab\u00edamos prestado pr\u00e1cticamente atenci\u00f3n) debe ser tambi\u00e9n sim\u00e9trica. Cualquier falta de simetr\u00eda provoca una diferencia entre los dos lados. Por tanto, s\u00f3lo hay que contar cu\u00e1ntas entradas son capic\u00faas (es decir, palindr\u00f3micas, o sim\u00e9tricas). Y coincide el n\u00famero con lo que hab\u00eda observado anteriormente.<\/p>\n","protected":false},"excerpt":{"rendered":"
Regalo estacional de los organizadores de la edici\u00f3n 2019 de la Olimpiada Internacional Se dirige a una edad de: 16-17 a\u00f1os 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\u00e1ngulo de Pascal, donde cada uno de los n\u00fameros es […]<\/p>\n","protected":false},"author":4267,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[2242017,1738,2849,3303],"tags":[],"class_list":["post-974","post","type-post","status-publish","format-standard","hentry","category-imo","category-olimpiadas","category-problemas","category-soluciones"],"_links":{"self":[{"href":"https:\/\/blogs.ua.es\/dimates\/wp-json\/wp\/v2\/posts\/974","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/blogs.ua.es\/dimates\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/blogs.ua.es\/dimates\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/blogs.ua.es\/dimates\/wp-json\/wp\/v2\/users\/4267"}],"replies":[{"embeddable":true,"href":"https:\/\/blogs.ua.es\/dimates\/wp-json\/wp\/v2\/comments?post=974"}],"version-history":[{"count":7,"href":"https:\/\/blogs.ua.es\/dimates\/wp-json\/wp\/v2\/posts\/974\/revisions"}],"predecessor-version":[{"id":981,"href":"https:\/\/blogs.ua.es\/dimates\/wp-json\/wp\/v2\/posts\/974\/revisions\/981"}],"wp:attachment":[{"href":"https:\/\/blogs.ua.es\/dimates\/wp-json\/wp\/v2\/media?parent=974"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blogs.ua.es\/dimates\/wp-json\/wp\/v2\/categories?post=974"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blogs.ua.es\/dimates\/wp-json\/wp\/v2\/tags?post=974"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}