Unas sucesiones algo caóticas

El problema de esta semana trata de unas sucesiones muy curiosas. Vamos con él:

Para cada $\alpha\in \left [0,1 \right ]$ se considera la sucesión $S_{\alpha}$ definida por recurrencia del modo siguiente:

$\begin{matrix} x_0=\alpha \\ x_{n+1}=4x_n(1-x_n), n\ge 0 \end{matrix}$

Diremos que la sucesión $S_{\alpha}$ es periódica, con periodo $T\ge 1$ , si existe ${T}$ el menor natural verificando $x_T=x_0 \left (=\alpha \right )$ .

1) Demostrar que para cada $T\geq 1$ natural existe al menos un valor $\alpha \in \left [0,1 \right ]$ de modo que la sucesión $S_{\alpha}$ es periódica con periodo exacto igual a $T$ . En particular, existen infinitas sucesiones $S_{\alpha}$ que son periódicas.

2) Hallar la cantidad exacta de números $\alpha\in \left [0,1 \right ]$ cuyo periodo es exactamente $2008$ .

Espero vuestras respuestas.

Autor: ^DiAmOnD^ | Publicado el 25 de Marzo de 2008
Categorías: Juegos

22 comentarios

Sive | 25 de Marzo de 2008 | 17:44

La respuesta para la 2) es 2008

Pero es intuición nada más :P, esta tarde/noche le doy una pensadita.
Domingo HA | 25 de Marzo de 2008 | 18:23

No, Sive, es “bastante más”. Mejor analizar primero los casos pequeños de puntos periódicos de periodo 1, de periodo 2, …, y ver si ocurre algo…
Manuel | 25 de Marzo de 2008 | 18:28

Más intuciones.

Sospecho que los $\alpha$ periódicos tienen que ser racionales y, quizá, han de contener un término $4^{-T}$ .

Pero es sólo intuición…
Sive | 25 de Marzo de 2008 | 18:42

Ya tengo la solución, una maravillosa, pero internet es demasiado estrecha para contenerla, jeje…

Nada, esta noche lo pensaré, solo tengo una cota máxima, y además está pensada de cabeza… pero no ayuda demasiado (es que es $2^2007$ o $2^2008$ , no he tenido tiempo de ser más preciso).
Sive | 25 de Marzo de 2008 | 18:44

Quise poner $2^{2007}$ o $2^{2008}$
Asier | 25 de Marzo de 2008 | 18:54

Sin pretender dar una demostración rigurosa, mi idea es que es fácil ver que la función $f(x) = 4x - 4x^2$ es contínua y está acotada en [0,1] para valores en el rango [0,1], con lo cual siempre nos vamos a mover en ese intervalo. Para T = 1 tenemos una ecuación de segundo grado cuyas soluciones son 0 y 3/4, y en cada iteración en orden del polinomio se duplica, con lo cual para 2008 tendríamos, como ha indicado Sive, $2^{2008}$ soluciones.
Sive | 25 de Marzo de 2008 | 19:00

Ese fue mi razonamiento Asier, pero es una cota a la alza, el valor real es menor. Como mínimo hay que restar las soluciones de 1004, 502…
Sive | 25 de Marzo de 2008 | 19:02

Rectifico: las de 1004 solo
Javier | 25 de Marzo de 2008 | 19:10

Yo sospecho que son $2^{2008}-2^{1004}-2^8+2$ , pero no lo puedo demostrar de momento.
Domingo HA | 25 de Marzo de 2008 | 19:52

Sive, Asier, Javier, las intuiciones van bien encaminadas (sobre todo la opción final de Sive y sobre todo la de Javier), pero la respuesta aún no se puede dar como correcta. El razonamiento de Asier puede ser interesante, aunque ha dejado algún detalle en el camino…
Sive | 25 de Marzo de 2008 | 20:55

Tal vez, Javier, lo que te falte por considerar es la posibilidad que me llevo a mi a pensar que podían ser muchas menos de las que, a primera vista, parecen.

¿Podría haber números iniciales que, sin dar lugar a sucesiones periódicas acaben desembocando en una y se muestren como soluciones irreales de la ecuación?

Es una de las ideas en las que pienso trabajar esta noche si nadie con la solución.
fede | 25 de Marzo de 2008 | 21:55

A mi me salen de momento 14 más que a Javier.
Creo que la transformación x =(sen y)^2 es útil para el caso…
Asier | 25 de Marzo de 2008 | 22:04

Creo que cada vez que aumentamos T en 1 hay que descartar las soluciones del anterior, por lo tanto me animo a dar la cifra de $2^{2007}$ .
Domingo H.A. | 25 de Marzo de 2008 | 22:07

sí señor, fede, efectivamente la solución al apartado 2) consiste en 14 puntos más que los que indicó Javier.
Asier | 26 de Marzo de 2008 | 1:25

¿Podríais explicar cómo habeis obtenido tal valor?
fede | 26 de Marzo de 2008 | 1:55

Si f(x) = 4x(1-x), y f(f(x) = f^2(x), etc, resulta que f^k(x) = x tiene 2^k soluciones reales entre 0 y 1 (esto es lo principal que hay que demostrar).

Como estamos considerando los ciclos que no tienen x entre f(x) y f^k(x) hay que restar los puntos que dan ciclos cuya longitud es divisor de k. Estos son las soluciones para k=1004 - soluciones para k=8 + soluciones para k=4 (porque las hemos restado 2 veces)
fede | 26 de Marzo de 2008 | 1:59

Los dos ultimos signos al revés…
Masao | 26 de Marzo de 2008 | 3:07

Dada $g:[a,b]\rightarrow[0,1]$ una funcion estrictamente creciente con $g(a)=0$ i $g(b)=1$ , sea $c\in (a,b)$ el punto que satisface $g(c)=1/2$ . Entonces $h(x) = 4g(x)(1-g(x))\in[0,1]$ satisface: $h(a)=0$ , $h(c)=1$ , $h(b)=0$ . Ademas $h:[a,c]\rightarrow[0,1]$ i $h:[c,b]\rightarrow[0,1]$ satisfacen las mismas propiedades que $g$ (weno, la segunda es decreciente i tal..)

En otras palabras $f_0(x) = x$ empiexa en 0 i va a 1 al incrementar x de 0 a 1. $f_1(x) = 4x(1-x)$ empiza en 0, va a 1 (en $x=1/2$ ), i vuelve a 0. $f_2(x) = 4f_1(x)(1-f_1(x))$ empieza en 0, va a 1, vuelva a 0 (en $x=1/2$ ), luego a 1 i a 0 otra vez. Generalizando, $f_n(x)$ va de 0 a 1 $2^{n-1}$ veces i de 1 a 0 $2^{n-1}$ veces.

Al resolver $f_{2008}(x)=x$ encontramos 1 solucion por cada viaje de 0 a 1 i de 1 a 0. En total $a(2008) = 2^{2008}$ soluciones.

(Ahora viene lo chulo http://en.wikipedia.org/wiki/Moebius_inversion_formula)
Como queremos periodo exactamente 2008, $b(2008)$ , hay que descartar las que tienen periodo 1, 2, 4, 8, 251, 2*251, 4*251.

Como $a(n) = 2^{n} = \sum_{d|n}{b(n)}$ entonces $b(n) = \sum_{d|n}{\mu(d)a(n/d)} =\sum_{d|n}{\mu(d)2^{n/d}}$

En nuestro caso $b(2008) = 2^{2008} - 2^{1004} -2^8 + 2^4$
Domingo H.A. | 26 de Marzo de 2008 | 13:32

Muy buena, fede y masao, esa es la idea y la solución. Masao, muy interesante la inversión según Möbius. Yo hice mis cálculos estudiando los casos de periodo $T=p,p^2,p^3, pq, p^2q, p^3q$ , con $p,q$ primos.

La cosa efectivamente estaba en ver que la función $f(x)=4x(1-x)$ geométricamente lo que hace es estirar el intervalo [0,1] (a doble distancia) y doblarlo sobre sí mismo. Entonces, en la enésima iteración de la sucesión realmente estamos haciendo $2^{n-1}$ bucles a la gráfica de $y=f(x)$ que cortarán exactamente en $2^n$ puntos (2 puntos por bucle) a la gráfica de $y=x$ . Y esto nos da los puntos que tienen un periodo que divide a $n$ , y por tanto hay que descontar los periodos relativos a los divisores de $n$ .

Otra cosa, hemos dicho que los puntos periódicos de la recurrencia son infinitos (dentro de [0,1]). La cosa es bastante más fuerte. Y es que los puntos periódicos realmente son densos en el intervalo, es decir, siempre entre dos puntos que dan lugar a sucesiones periódicas podremos encontrar otro en medio que también de lugar a periodicidad. Este hecho es, a priori, sorprendente. Salvo un conjunto de medida nula, todos los valores iniciales de la recurrencia son periódicos!

No sé si se han fijado en que el factor 4 multiplicativo juega un papel importante. Continuará…
fede | 27 de Marzo de 2008 | 10:39

No estoy familiarizado con la teoría de la medida, pero la idea que tenía es que un conjunto numerable tiene medida 0. Como el conjunto de los puntos periódicos es numerable, tiene medida 0, ¿ Es así ? Entonces casi ningún punto del intervalo sería periódico…
Domingo H.A. | 27 de Marzo de 2008 | 11:33

tienes razón fede, he dado otro patinazo (pido perdón por ello), pero lo de la densidad sí es cierto.
fede | 2 de Abril de 2008 | 14:01

También podemos obtener una fórmula explícita para $f_k(x)$ :

Haciendo $x=sen^2z$ , tenemos que $z= arcsen\sqrt{x}$ .
Entonces $f_1(x) = 4x(1-x) = 4sen^2z\ cos^2z = sen^2\ 2z = sen^2 \ 2\ arcsen \sqrt{x}$
y $f_2(x) = sen^2 \ 2\ arcsen \sqrt{sen^2 \ 2\ arcsen \sqrt{x}} = sen^2 \ 2^2\ arcsen \sqrt{x}$ .
La inducción es clara, $f_k(x) = sen^2 \ 2^k\ arcsen \sqrt{x}.$

Cuando x va de 0 a 1, $\sqrt{x}$ va monótonamente de 0 a 1, $arcsen \sqrt{x}$ de 0 a $\pi/2$ , y $2^k\ arcsen \sqrt{x}$ de 0 a $2^{k-1}\pi$ , entonces $f_k(x)$ se moverá de 0 a 1 y de 1 a 0 $2^{k-1}$ veces (y monótonamente cada una de ellas), lo que da el resultado anterior.