{"id":1750,"date":"2020-09-05T07:45:40","date_gmt":"2020-09-05T07:45:40","guid":{"rendered":"https:\/\/blogs.ua.es\/dimates\/?p=1750"},"modified":"2020-10-17T15:47:28","modified_gmt":"2020-10-17T15:47:28","slug":"solucion-a-sucesion-recursiva-2","status":"publish","type":"post","link":"https:\/\/blogs.ua.es\/dimates\/2020\/09\/05\/solucion-a-sucesion-recursiva-2\/","title":{"rendered":"Soluci\u00f3n a sucesi\u00f3n recursiva"},"content":{"rendered":"
Problema 2 de la fase nacional de la 56 Olimpiada Matem\u00e1tica Espa\u00f1ola (2020)\r\nSe dirige a una edad de: 16-17 a\u00f1os<\/pre>\n
Consideramos la sucesi\u00f3n de n\u00fameros enteros f(n), con n mayor o igual que 1, definida por las siguientes condiciones:<\/p>\n
f(1) = 1.<\/p>\n
Si n es par, f(n) = f(n\/2).<\/p>\n
Si n es impar y f(n \u2013 1) es impar, entonces f(n) = f(n \u2013 1) \u2013 1.<\/p>\n
Si n es impar y f(n \u2013 1) es par, entonces f(n) = f(n \u2013 1) + 1.<\/p>\n
a) Calcula f(22020<\/sup> \u2013 1).<\/p>\n
b) Demuestra que la sucesi\u00f3n no es peri\u00f3dica, es decir, que no existen enteros positivos t y n0<\/sub> que cumplan que si n es mayor que n0<\/sub>, entonces f(n + t) = f(n).
\n\"\"
\nSoluci\u00f3n:
\n
\nEste es un problema en el que es muy importante generalizar con rigor, para lo cual vamos a estudiar los primeros elementos de la sucesi\u00f3n.<\/p>\n
Tambi\u00e9n es \u00fatil haber tenido un contacto previo con los n\u00fameros binarios, ya que la importancia de la paridad en la definici\u00f3n de la sucesi\u00f3n sugiere que van a tener una gran importancia.<\/p>\n
Los primeros elementos formar\u00edan la cadena siguiente:<\/p>\n
1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0, 1, 0, 0, 1, 0, 1, 1, 0, …<\/p>\n
Aparentemente no hay ninguna regularidad, pero si los relacionamos con su expresi\u00f3n binaria, podemos observar un hecho curioso.<\/p>\n
Voy a construir una sucesi\u00f3n muy parecida, a la que llamar\u00e9 la sucesi\u00f3n g, pero en lugar de restar 1 a f(n \u2013 1), le voy a sumar 1.<\/p>\n
Y voy a representar cada t\u00e9rmino de la sucesi\u00f3n junto a su posici\u00f3n, y la representaci\u00f3n en n\u00fameros binarios de esa posici\u00f3n.<\/p>\n
1 \u2013 1 \u2013 1
\n2 \u2013 10 \u2013 1 (como 1)
\n3 \u2013 11 \u2013 2 (2 + 1)
\n4 \u2013 100 \u2013 1 (como 2)
\n5 \u2013 101 \u2013 2 (1 + 1)
\n6 \u2013 110 \u2013 2 (como el 3)
\n7 \u2013 111 \u2013 3 (2 + 1)
\n8 \u2013 1000 \u2013 1 (como el 4)
\n9 \u2013 1001 \u2013 2 (1 + 2)
\n10 \u2013 1010 \u2013 1 (como el 5)<\/p>\n
Es evidente que la sucesi\u00f3n se parece mucho, s\u00f3lo que en este caso, a diferencia de f, g tiene valores mayores. Est\u00e1 claro que f no crece, porque la \u00fanica manera de aumentar es sumando a un valor anterior, pero si ese valor es 1, en f restamos, y volvemos a 0.<\/p>\n
Y en f tampoco bajamos de cero, porque si el valor es 0, es par, luego sumamos.<\/p>\n
B\u00e1sicamente, la f es como la g en el sentido de que si g es par, f vale 0, y si g es impar, f vale 1. La sucesi\u00f3n f es la llamada paridad de g.<\/p>\n
Pues bien, si os dais cuenta, g representa el n\u00famero de cifras 1 en la representaci\u00f3n binaria.<\/p>\n
Claramente, si n es par, su cantidad de cifras 1 es la misma que la de n\/2, ya que multiplicar por 2 equivale a a\u00f1adir un 0 como \u00faltima cifra.<\/p>\n
Y si es impar, tiene un 1 m\u00e1s que el n\u00famero anterior, ya que un “0” del final del n\u00famero lo cambiamos por un “1”.<\/p>\n
Lo que quiero decir es que f s\u00f3lo puede valer 0 o 1, y consiste en que vale 0 si la cantidad de 1 de la representaci\u00f3n en binario de un n\u00famero tiene una cantidad par de 1, y 1 si la representaci\u00f3n en binario de un n\u00famero tiene una cantidad impar de 1 entonces vale 1.<\/p>\n
Podemos demostrarlo con los argumentos dados antes, por recursividad, tal y como est\u00e1 bien definida la funci\u00f3n.<\/p>\n
Observando esto, est\u00e1 claro que f(22020<\/sup> \u2013 1) vale 0, ya que es un n\u00famero que est\u00e1 formado por 2020 unos.<\/p>\n
Una forma directa de demostrarlo puede ser probando por inducci\u00f3n que 2n<\/sup> \u2013 1 vale 0 si n es par y 1 si n es impar. Como siempre es impar, se basa en el n\u00famero anterior, que ser\u00e1 2n<\/sup> \u2013 2 = 2(2n \u2013 1<\/sup> \u2013 1), que por hip\u00f3tesis de inducci\u00f3n ya tiene la propiedad buscada.<\/p>\n
Ver que no es peri\u00f3dica es bastante m\u00e1s complicado. Si hemos dado con la analog\u00eda de que el valor de f depende del n\u00famero de cifras en formato binario, podemos observar que cuando pasamos de una potencia a otra de 2, vuelve a repetir la misma secuencia, pero invertida.<\/p>\n
Por ejemplo, 1, 1, 0, 1, 0, 0, 1, 1 son los 8 primeros, y los de 9 a 15 son 0, 0, 1, 0, 1, 1, 0. Sin embargo, las potencias de 2, tanto 8 como 16, siempre valen 1. Con lo que las secuencias se van haciendo cada vez m\u00e1s largas.<\/p>\n
Para probar que no es peri\u00f3dica (como casi siempre que queremos ver que algo no sucede) lo mejor suele ser proceder por reducci\u00f3n al absurdo, es decir, suponer que s\u00ed lo es y llegar a una contradicci\u00f3n.<\/p>\n
Supongamos que s\u00ed es peri\u00f3dica, por lo que existe un valor n0<\/sub> y un valor t, como dice el enunciado, de forma que f(n + t) = f(n) para cada n mayor que n0<\/sub>.<\/p>\n
Para llegar a un absurdo sin mucha dificultad, podemos pensar en los d\u00edgitos en binario de t. Necesitamos tomar una n que podamos manejar con claridad. Puesto que tenemos que negar esta propiedad, trataremos de llegar a una situaci\u00f3n que no pueda darse esta igualdad.<\/p>\n
Imaginemos que t es un n\u00famero binario, como por ejemplo 1 100 111. En este caso, tiene 5 cifras 1, con lo que f(t) = 1. Pero ese no significa mucho para nosotros. Sin embargo, si tomamos el valor 1 000 000, sabemos que al sumarlo a t obtendremos 10 100 111, es decir, obtendremos la misma cantidad de unos, es decir, que f(n + t) = 1. Y si tomamos el valor 11 000 000, al sumarlo obtendremos el valor para n + t (en binario) de 100 100 111, es decir, que volveremos a tener el mismo valor para la cantidad de cifras 1 que t. La diferencia entre 1 000 000 y 11 000 000 es que mientras que f en el primero da 1, f en el segundo da 0, y en ambos casos f(n + t) deber\u00eda ser f(n), luego es imposible.<\/p>\n
Ahora bien, \u00bfc\u00f3mo nos aseguramos que eso no pasa hasta un cierto valor suficientemente grande?, pues tomamos el valor n0<\/sub> y usamos una potencia suficientemente grande. Imagina que nos dicen que n0<\/sub> fuese 101 110 001. Pues usamos como candidatos a n los n\u00fameros 1 001 000 000 (cuyo valor de f es 0) y 1 011 000 000, que tiene un valor de f de 1. en ambos casos, al sumar t nos da la misma cantidad de 1 en binario (1 m\u00e1s que t), y por lo tanto el valor de f(n + t) deber\u00eda ser el mismo, lo que es imposible.<\/p>\n
\u00bfC\u00f3mo se puede hacer de manera formal?<\/p>\n
Habr\u00eda que demostrar que si 2p<\/sup> es mayor que un cierto valor x, f(2p<\/sup> + x) = 1 \u2013 f(x). Es f\u00e1cil de ver si aplicamos la hip\u00f3tesis de inducci\u00f3n y desglosamos los casos en que x es par o impar. Eso quiere decir que si sumamos potencias suficientemente grandes a un valor, f cambia su valor al opuesto (de 1 a 0 y de 0 a 1).<\/p>\n
Adem\u00e1s, si tenemos el valor p que cumple que 2p<\/sup> <= t < 2p + 1<\/sup> (es decir, la \u00faltima cifra binaria de p), se tiene que f(t) = f(2p<\/sup> + t). Probar esto es m\u00e1s complicado, salvo que se conozca muy bien el sistema binario.<\/p>\n
Tratemos de probarlo por inducci\u00f3n sobre t. Est\u00e1 claro que para t = 1 se cumple (el valor correspondiente de p es 0). Supongamos que es cierto hasta un cierto valor t \u2013 1 y tratemos de ver que es cierto para t. Habr\u00e1 que diferenciar dos casos, aquel en el que tienen el mismo p y el que tienen diferente p. Si tienen el mismo p, puesto que se define f por recursi\u00f3n es muy sencillo apoyarnos en la hip\u00f3tesis de inducci\u00f3n. Si no tienen el mismo valor de p, es porque coincide que t es exactamente 2p + 1<\/sup> , y entonces tenemos que f(t) = 1, y f(2p + 1<\/sup> + t) = f(2p + 2<\/sup>) = 1.<\/p>\n
Una vez que hemos averiguado estas propiedades con sumas de potencias grandes de 2 y t, elegimos un valor de p de forma que 2p<\/sup> <= t < 2p + 1<\/sup> y un valor de q que al menos sea tres unidades mayor que p y que 2q<\/sup> sea tambi\u00e9n mayor que n0<\/sub>. A partir de ah\u00ed y las propiedades que hemos trabajado, concluiremos que f(2q<\/sup> + 2p<\/sup>) es diferente de f(2q<\/sup> + 2p + 1<\/sup> + 2p<\/sup>), pero que f(2q<\/sup> + 2p<\/sup> + t) = f(2q<\/sup> + 2p + 1<\/sup> + 2p<\/sup> + t), por la elecci\u00f3n de p, y los dos posibles candidatos para n son mayores que n0<\/sub>.<\/p>\n
Como veis, no es un trabajo sencillo, y eso sin contar la presi\u00f3n de tiempo que supone el concurso (aproximadamente una hora por problema).<\/p>\n","protected":false},"excerpt":{"rendered":"
Problema 2 de la fase nacional de la 56 Olimpiada Matem\u00e1tica Espa\u00f1ola (2020) Se dirige a una edad de: 16-17 a\u00f1os Consideramos la sucesi\u00f3n de n\u00fameros enteros f(n), con n mayor o igual que 1, definida por las siguientes condiciones: f(1) = 1. Si n es par, f(n) = f(n\/2). Si n es impar y […]<\/p>\n","protected":false},"author":4267,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[2242021,1738,3303],"tags":[],"class_list":["post-1750","post","type-post","status-publish","format-standard","hentry","category-olimpiada-matematica-espanola","category-olimpiadas","category-soluciones"],"_links":{"self":[{"href":"https:\/\/blogs.ua.es\/dimates\/wp-json\/wp\/v2\/posts\/1750","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=1750"}],"version-history":[{"count":4,"href":"https:\/\/blogs.ua.es\/dimates\/wp-json\/wp\/v2\/posts\/1750\/revisions"}],"predecessor-version":[{"id":1806,"href":"https:\/\/blogs.ua.es\/dimates\/wp-json\/wp\/v2\/posts\/1750\/revisions\/1806"}],"wp:attachment":[{"href":"https:\/\/blogs.ua.es\/dimates\/wp-json\/wp\/v2\/media?parent=1750"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blogs.ua.es\/dimates\/wp-json\/wp\/v2\/categories?post=1750"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blogs.ua.es\/dimates\/wp-json\/wp\/v2\/tags?post=1750"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}