{"id":843,"date":"2018-10-13T09:22:31","date_gmt":"2018-10-13T09:22:31","guid":{"rendered":"https:\/\/blogs.ua.es\/dimates\/?p=843"},"modified":"2018-10-14T06:43:45","modified_gmt":"2018-10-14T06:43:45","slug":"solucion-a-sucesion-periodica-y-recursiva","status":"publish","type":"post","link":"https:\/\/blogs.ua.es\/dimates\/2018\/10\/13\/solucion-a-sucesion-periodica-y-recursiva\/","title":{"rendered":"Soluci\u00f3n a sucesi\u00f3n peri\u00f3dica y recursiva"},"content":{"rendered":"
Problema 2 de la Olimpiada Internacional (2018)\r\nSe dirige a una edad de: 17-19 a\u00f1os<\/pre>\n
Hallar todos los enteros n mayores o iguales a 3 para los que existen n\u00fameros reales a\u2081<\/sub>, a\u2082<\/sub>, \u2026, an + 2<\/sub> tales que ai<\/sub>\u00b7ai + 1<\/sub> + 1 = ai + 2<\/sub> para i = 1, 2, \u2026, n, y an + 1<\/sub> = a\u2081<\/sub>, y an + 2<\/sub> = a\u2082<\/sub>.
\n\"\"
\nSoluci\u00f3n:
\n
\nEste problema ya es bastante m\u00e1s dif\u00edcil. Resolver los dos f\u00e1ciles y \u00e9ste supuso entrar en la puntuaci\u00f3n de las medallas, ya que suponen en total 21 puntos (16 \u2013 24 puntos, medalla de bronce en este a\u00f1o).<\/p>\n
Construir un ejemplo por tanteo no es f\u00e1cil. Juguemos en principio con la sucesi\u00f3n m\u00ednima, de cinco elementos, pero en la que los dos \u00faltimos coinciden con los dos primeros. Se tratar\u00eda de s\u00f3lo tres n\u00fameros, a, b, c, a, b. Adem\u00e1s, debe darse que a\u00b7b + 1 = c, b\u00b7c + 1 = a y c\u00b7a + 1 = b, y tenemos un sistema no lineal de tres ecuaciones con tres inc\u00f3gnitas. Tratemos de resolverlo.<\/p>\n
Un primer paso ser\u00eda sustituir la c, que ya est\u00e1 despejada en la primera ecuaci\u00f3n, en las otras dos. Eso nos deja dos ecuaciones muy similares con a y b. Una ser\u00e1 b(a\u00b7b + 1) + 1 = a y la otra, a(a\u00b7b + 1) + 1 = b.<\/p>\n
Ocup\u00e1ndonos de la primera ecuaci\u00f3n, tenemos que, al quitar par\u00e9ntesis, a\u00b7b\u00b2 + b + 1 = a. Es una ecuaci\u00f3n de primer grado en a y segundo en b, es decir, que deber\u00edamos intentar despejar a. Si dejamos los t\u00e9rminos sin a en un lado y los que s\u00ed tienen a en el otro, queda b + 1 = a(1 \u2013 b\u00b2) (aqu\u00ed he sacado factor com\u00fan la a).<\/p>\n
Vamos a plantearnos esta igualdad. Si queremos acabar de despejar, b no puede valer 1 ni puede valer \u20131, ya que a quedar\u00eda multiplicado por 0. Sin embargo, b = \u20131 podr\u00eda ser soluci\u00f3n, mientras que b = 1 no.<\/p>\n
Puede que haya m\u00e1s soluciones (de hecho, podr\u00edamos despejar a en otros casos y buscarlas, aunque no lleva a ning\u00fan sitio \u00fatil), pero ya tenemos el principio de una. Vale, b puede valer \u20131, y la otra ecuaci\u00f3n, en ese caso, queda a(a\u00b7(\u20131) + 1) + 1 = \u20131, es decir, a(1 \u2013 a) = \u20132, que es una ecuaci\u00f3n de segundo grado, a \u2013 a\u00b2 = \u20132, o 0 = a\u00b2 \u2013 a \u2013 2. Aplicando la conocida ecuaci\u00f3n de segundo grado, tenemos que a puede valer 2 o \u20131.<\/p>\n
Y, claro, c se puede calcular a partir de a y b. Eso quiere decir dos soluciones: \u20131, \u20131, 2, \u20131, \u20131 y tambi\u00e9n 2, \u20131, \u20131, 2, \u20131 (si hubi\u00e9semos supuesto que b no vale \u20131, y despejamos a, con mucho trabajo, habr\u00edamos llegado a la \u00fanica tercera soluci\u00f3n, que es que b vale 2 y, curiosamente, a y c valen \u20131, con lo que en realidad se trata de la misma soluci\u00f3n).<\/p>\n
Es decir, que para n = 3 s\u00f3lo hay una posibilidad, y empezar por un sitio o por otro, ya que la sucesi\u00f3n es peri\u00f3dica, es decir, a partir del valor n vuelve a empezar. Como s\u00f3lo tenemos que estudiar si para ese valor de n existe o no tal sucesi\u00f3n, sabemos ya que para 3 s\u00ed.<\/p>\n
Aunque no es f\u00e1cil caer en la cuenta, con estos mismos n\u00fameros vale para cualquier m\u00faltiplo de 3. Por ejemplo, para n = 6 tendr\u00edamos la sucesi\u00f3n \u20131, \u20131, 2, \u20131, \u20131, 2, \u20131, \u20131, que cumple la condici\u00f3n tambi\u00e9n. Y repitiendo esta terna de valores, existir\u00eda la sucesi\u00f3n para cualquier n m\u00faltiplo de 3.<\/p>\n
Ya s\u00f3lo queda averiguar si los valores que no sean m\u00faltiplos de 3 es posible o no construir una sucesi\u00f3n de este tipo, pero eso necesita hacer otro tipo de esfuerzo.<\/p>\n
Desde luego, intentar buscar una soluci\u00f3n para n = 4 es muy dif\u00edcil de plantear con una estrategia similar, as\u00ed que vamos a estudiar qu\u00e9 pasa con los signos.<\/p>\n
Si a lo largo de la sucesi\u00f3n tenemos dos t\u00e9rminos consecutivos positivos (o no negativos), por construcci\u00f3n, el siguiente ser\u00e1 mayor o igual que 1, y el siguiente a ese, mayor que 1 y que el anterior, y cada t\u00e9rmino ser\u00e1 positivo y mayor que el que precede a su anterior. De esta forma, es imposible que ninguno de ellos pueda volver a repetir la secuencia, ya que en ning\u00fan momento se reducir\u00e1 su valor.<\/p>\n
Es evidente que no pueden darse tres negativos seguidos, por la regla de los signos.<\/p>\n
Veamos ahora que si hay dos negativos consecutivos, entonces se vuelve a dar una secuencia positivo \u2013 negativo \u2013 negativo. Imagina que no sea as\u00ed, tenemos cinco n\u00fameros positivos de forma que la sucesi\u00f3n \u2013a, \u2013b, c, \u2013d, e cumple la regla de recursividad. Como c = ab + 1, tenemos que c > 1. Pero como e = 1 \u2013 cd, entonces e < 1, y claramente e  \u2013cd, y 1 \u2013 de, que ser\u00eda el siguiente elemento de la sucesi\u00f3n, ser\u00eda mayor que 1 \u2013 cd = e, que es positivo. Eso implica dos n\u00fameros positivos, que ya hemos visto que es imposible.<\/p>\n
Veamos que tampoco puede darse el caso de que haya una alternancia permanente negativo \u2013 positivo \u2013 negativo \u2013 positivo. Si esto sucede, entonces no puede volverse a repetir, porque los t\u00e9rminos negativos son cada vez m\u00e1s grandes, por lo que no podr\u00eda ser peri\u00f3dica (y adem\u00e1s, acabar\u00edan por ser positivos). Vamos a demostrarlo. Supongamos que la sucesi\u00f3n es de la forma \u2013x1<\/sub>, x2<\/sub>, \u2013x3<\/sub>, x4<\/sub>, \u2026, con todos los valores xi<\/sub> positivos y cumple la regla de recursividad. En cualquier n\u00famero par xk<\/sub> = \u2013xk \u2013 1<\/sub>\u00b7xk – 2<\/sub> + 1, y eso significa que claramente es menor que 1, y si xk<\/sub> < 1, xk<\/sub>\u00b7xk – 1<\/sub> < xk – 1<\/sub>, y \u2013xk<\/sub>\u00b7xk – 1<\/sub> > \u2013xk – 1<\/sub>, pero entonces \u2013xk + 1<\/sub> = \u2013xk<\/sub>\u00b7xk \u2013 1<\/sub> + 1 > \u2013xk – 1<\/sub> + 1 > \u2013xk \u2013 1<\/sub>, que es el anterior negativo.<\/p>\n
Por lo tanto, la \u00fanica posibilidad es que la sucesi\u00f3n tenga un ritmo positivo \u2013 negativo \u2013 negativo permanente, con lo que el n\u00famero de elementos n deber\u00eda ser m\u00faltiplo de 3, como el que hemos visto. Y, puesto que ya hemos visto un ejemplo, seguro que existen.<\/p>\n
Hay una demostraci\u00f3n muy original que no utiliza muchos recursos, pero es muy imaginativa.<\/p>\n
Primero, hay que ver que la sucesi\u00f3n -1, -1, 2 cumple las reglas, como hemos visto.<\/p>\n
Cada uno de los elementos debe cumplir ai<\/sub>\u00b7ai + 1<\/sub> + 1 = ai + 2<\/sub>, y eso supone, multiplicando por ai + 2<\/sub> que ai<\/sub>\u00b7ai + 1<\/sub>\u00b7ai + 2<\/sub> + ai + 2<\/sub> = (ai + 2<\/sub>)\u00b2. Tambi\u00e9n, obteniendo el t\u00e9rmino siguiente y multiplicando por ai<\/sub>, ai<\/sub>\u00b7ai + 1<\/sub>\u00b7ai + 2<\/sub> + ai<\/sub> = ai<\/sub>\u00b7ai + 3<\/sub>.<\/p>\n
Si sumamos todos los posibles valores de la sucesi\u00f3n desde el 1 hasta el n, tendremos que la suma de los cuadrados (que cada uno de ellos es igual al producto de tres consecutivos m\u00e1s uno de ellos) es igual a la suma de todos los productos de uno de ellos por el tercero a partir de \u00e9l (que tambi\u00e9n tiene una expresi\u00f3n id\u00e9ntica, ya que estamos sumando todos).<\/p>\n
Eso quiere decir que si sumamos todos los cuadrados de la resta (ai<\/sub> \u2013 ai + 3<\/sub>)\u00b2, tendremos la suma de todos los ai<\/sub>\u00b2 + (ai + 3<\/sub>)\u00b2 \u2013 2ai<\/sub>\u00b7ai + 3<\/sub>, pero como la suma de los cuadrados es igual que la suma de los productos que salen, todo eso debe dar cero.<\/p>\n
Pero como todos los cuadrados deben dar cero para que la suma sea cero, resulta que cada t\u00e9rmino es exactamente igual al que hay tres posiciones m\u00e1s adelante, luego n s\u00f3lo puede ser m\u00faltiplo de 3 (o ser una sucesi\u00f3n constante, cosa que es f\u00e1cil comprobar que no es posible).<\/p>\n
Para terminar, hay una demostraci\u00f3n algo m\u00e1s t\u00e9cnica, que exige un poco de conocimiento previo. Puesto que los participantes a estos niveles llevan mucha preparaci\u00f3n te\u00f3rica, voy a darla, pero es normal que no hayas o\u00eddo a\u00fan hablar del resultado intermedio que es necesario.<\/p>\n
La propiedad necesaria es la llamada desigualdad de la reordenaci\u00f3n (rearrangement inequality), que afirma lo siguiente: Si tenemos dos sucesiones ordenadas de n\u00fameros reales x1<\/sub> ≤ x2<\/sub> ≤ x3<\/sub> ≤ \u2026 ≤ xn<\/sub> y y1<\/sub> ≤ y2<\/sub> ≤ y3<\/sub> ≤ \u2026 ≤ yn<\/sub>, y tenemos una reordenaci\u00f3n de la primera sucesi\u00f3n (que ya no estar\u00e1 ordenada) z1<\/sub>, z2<\/sub>, z3<\/sub>, \u2026 zn<\/sub>, entonces el producto  x1<\/sub>\u00b7yn<\/sub> + x2<\/sub>\u00b7yn – 1<\/sub> + \u2026 + xn<\/sub>\u00b7y1<\/sub> ≤ z1<\/sub>\u00b7yn<\/sub> + z2<\/sub>\u00b7yn – 1<\/sub> + \u2026 + zn<\/sub>\u00b7y1<\/sub> ≤ x1<\/sub>\u00b7y1<\/sub> + x2<\/sub>\u00b7y2<\/sub> + \u2026 + xn<\/sub>\u00b7yn<\/sub>. Adem\u00e1s, la desigualdad es estricta salvo que la reordenaci\u00f3n no desordene las xi<\/sub> (entonces ser\u00e1 igual que la primera suma) o que invierta totalmente el orden (que ser\u00e1 igual a la \u00faltima suma).<\/p>\n
Si lo piensas bien, es un resultado muy curioso y potente. Si tienes curiosidad del motivo de su funcionamiento, se puede demostrar por inducci\u00f3n sobre el n\u00famero de elementos.<\/p>\n
Bueno, vamos a ver c\u00f3mo se aplica a nuestro caso.<\/p>\n
Una vez que hemos visto que la suma de todos los cuadrados es igual que la suma de todos los productos de un t\u00e9rmino por el que hay tres puestos m\u00e1s adelante, como hemos visto en la demostraci\u00f3n anterior, resulta que tenemos dos sucesiones (que son la misma, la nuestra ordenada), y como hemos visto, si comparamos la suma del producto de una reordenaci\u00f3n a la suma ordenada (que ser\u00edan los cuadrados, obviamente), siempre ser\u00eda menor, salvo que la reordenaci\u00f3n no alterase el orden en absoluto, es decir, que cada elemento sea igual que el que est\u00e1 tres posiciones m\u00e1s adelante. Y ya estar\u00eda.<\/p>\n","protected":false},"excerpt":{"rendered":"
Problema 2 de la Olimpiada Internacional (2018) Se dirige a una edad de: 17-19 a\u00f1os Hallar todos los enteros n mayores o iguales a 3 para los que existen n\u00fameros reales a\u2081, a\u2082, \u2026, an + 2 tales que ai\u00b7ai + 1 + 1 = ai + 2 para i = 1, 2, \u2026, n, […]<\/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-843","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\/843","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=843"}],"version-history":[{"count":5,"href":"https:\/\/blogs.ua.es\/dimates\/wp-json\/wp\/v2\/posts\/843\/revisions"}],"predecessor-version":[{"id":855,"href":"https:\/\/blogs.ua.es\/dimates\/wp-json\/wp\/v2\/posts\/843\/revisions\/855"}],"wp:attachment":[{"href":"https:\/\/blogs.ua.es\/dimates\/wp-json\/wp\/v2\/media?parent=843"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blogs.ua.es\/dimates\/wp-json\/wp\/v2\/categories?post=843"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blogs.ua.es\/dimates\/wp-json\/wp\/v2\/tags?post=843"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}