Deje $(a_{n})_{n \ge 1}$ ser una secuencia de números enteros tales que para todos los $n \ge 2$:
$0\le a_{n-1}+\frac{1-\sqrt{5}}{2}a_{n}+a_{n+1} <1$.
Demostrar que la secuencia de $(a_{n})$ es periódica.
Esta pregunta se la hicieron en el Miklos Schweitzer Competencia de 2005, problema 2 (en húngaro).
Desde $(a_{n})$ se entero de ello se sigue que $a_{n+1}=\left\lceil \frac{-1+\sqrt{5}}{2}a_{n}-a_{n-1} \right\rceil$ es periódica.
El debate relativo a esta pregunta se puede encontrar en Mathlinks, y, al parecer, podemos optar $a_{1}$ e $a_{2}$ hacer este período tan grande como queramos.
Se agradece cualquier ayuda, gracias.
Me gustaría aclarar algunos puntos acerca de este problema:1) Existe un límite de la función ($\lceil x \rceil$) en la secuencia recursiva que hace que sea mucho más difícil. El período no es 5, como afirman algunas respuestas.
2) Miklos Schweitzer no es un convencionales de la competencia. Este concurso para estudiantes de pregrado es único. El concurso dura 10 días con 10-12 problemas, que son muy difíciles y, básicamente, de nivel de investigación. Además, cualquier literatura puede ser utilizado.
3) Un ejemplo de Miklos Schweitzer problema puede ser encontrada aquí en MO. De hecho fue una muy buena pregunta con una mejor solución. No estoy seguro de que el Arte de Resolver el Problema, sería mejor.
Lo siento por las molestias causadas y espero que esta pregunta no se cierra.
Respuestas
¿Demasiados anuncios?
Esta no es una solución, sino un terreno sugiere que la recursividad tiene la estructura geométrica de un plano de quasicrystal con los cinco simetría de un mosaico de Penrose:
(fuente: harvard.edu)
Es obtenido por la conexión de cada punto entero $(x,y)$ a su imagen, girado por 72 grados con respecto a la forma cuadrática invariante bajo la recursividad lineal $(x,y) \mapsto (y, \frac{-1+\sqrt{5}}{2} y - x)$ [sin techo funciones, cuya eliminación hace que este mapa exacto 72-grado de rotación]. El centro es el punto verde; otros puntos obtener círculos cuyos tamaños mantener un seguimiento de cuántas veces mod 5 han sido girado; las órbitas de $(5,0)$ e $(13,0)$ están en azul y rojo respectivamente. (El Mathlinks discusión sugiere que a partir de los números de Fibonacci los rendimientos a largo órbitas.) Para ver una imagen más grande http://math.harvard.edu/~elkies/mo229714.pdf .
Otra visualización, similar a Noam, junto con una modificación de un comentario por David, podría conducir a una solución de la cuestión: Definir $T:\mathbb Z^2\to\mathbb Z^2$ por $T(a_1,a_2)=(a_6,a_7)$. Es fácil ver que $T(v)-v$ es de $\{-1,0,1\}^2$ (y distinta de $(1,-1)$ e $(-1,1)$) para todos los $v\in\mathbb Z^2$. Deje $F_i$ ser $i$-ésimo número de Fibonacci. A continuación, todos los puntos de la frontera del triángulo $\Delta_{2i+1}$ con vértices $(z,-z)$, $(-z,z)$, $(-z,-z)$ con $z=F_{2i+1}-1$ parecen ser fijado en virtud de los $T$. Así que, por el otro comentario sobre el paso de las longitudes de $T$, $\Delta_{2i+1}$ es invariante bajo $T$. Del mismo modo, los triángulos $\Delta_{2i}$ con vértices $(z,-z)$, $(-z,z)$, $(z,z)$ donde $z=F_{2i}$ parece que tienen la propiedad de que cada punto de la frontera es fijo, o aún permanece en la frontera.
Trabajo fuera de estas observaciones, parece ser un poco técnico. Set $\omega=\frac{\sqrt{5}-1}{2}$. La identidad de $\omega F_i=F_{i-1}-(-\omega)^i$, junto con la mala racional aproximadamente de $\omega$, implica por ejemplo, $\lceil(\omega(\pm F_i+k)\rceil=\pm F_{i-1}+\lceil\omega k\rceil$ para cada entero $k$ con $|k|<F_i$. Eso es algo que sería necesaria.
El siguiente dibuja las líneas que conectan $v$ con $T(v)$ (y nada si $v=T(v)$) y los triángulos $\Delta_j$.
Definir los números de Fibonacci por $f_0 = 0$, $f_1 = 1$, $f_{n+1} = f_n + f_{n-1}$, y el cociente de oro por $\phi = \frac{\sqrt{5}+1}{2}$. Entonces es fácil comprobar que $f_n = \frac{\phi^n - (\tfrac{-1}{\phi})^n}{\sqrt{5}}$ e $(\phi-1)f_n = f_{n-1}-(\tfrac{-1}{\phi})^n$.
Vamos a demostrar que si cinco términos en una fila están todos a menos de $f_{2k}$ para algunos $k > 1$, entonces todos los $a_n$ son de menos de o igual a $f_{2k}.$
Supongamos que $a_{n-1}, a_n$ son positivos. Como es bien sabido, podemos encontrar conjuntos de $I,J \subset \{2,3,4,...\}$ con $I \cap (I+1) = J\cap (J+1) = \emptyset$, de tal manera que $a_n = \sum_{i\in I} f_i$ e $a_{n-1} = \sum_{j\in J} f_j$. Poner $x = \sum_{i\in I} (\tfrac{-1}{\phi})^i$ e $y = \sum_{j\in J} (\tfrac{-1}{\phi})^j$. Mediante la suma de una serie geométrica, es fácil mostrar que tenemos $\frac{-1}{\phi^2} < x,y < \frac{1}{\phi}$. Expresan $a_{n+1}, ..., a_{n+5}$ en términos de $x$ e $y$, obtenemos
$a_{n+1} = \sum_{i\in I}f_{i-1} - \sum_{j\in J} f_j + \alpha,\ \ \alpha = \lceil -x\rceil,$
$a_{n+2} = -\sum_{i\in I}f_{i-1} - \sum_{j\in J} f_{j-1} + \beta,\ \ \beta = \lceil\phi x + y + (\phi-1)\alpha\rceil,$
$a_{n+3} = -\sum_{i\in I}f_i + \sum_{j\in J} f_{j-1} + \gamma,\ \ \gamma = \lceil-\phi x-\phi y + (\phi-1)\beta - \alpha\rceil,$
$a_{n+4} = \sum_{j\in J} f_j + \delta = a_{n-1} + \delta,\ \ \delta = \lceil x+\phi y + (\phi-1)\gamma - \beta\rceil,$
$a_{n+5} = \sum_{i\in I}f_i + \epsilon = a_n + \epsilon,\ \ \epsilon = \lceil -y + (\phi-1)\delta - \gamma\rceil.$
Tenga en cuenta que si por el contrario nos había $a_n$ positiva y $a_{n-1}$ negativo, a continuación, en la escritura de $a_{n-1} = -\sum_{j\in J} f_j$ e $y = -\sum_{j\in J} (\frac{-1}{\phi})^j$, aún así obtener un $a_{n+4} = a_{n-1} + \delta$ e $a_{n+5} = a_n + \epsilon$, con $\alpha, \beta, \gamma, \delta, \epsilon$ se define como la anterior. Tenga en cuenta que en este caso, tenemos las desigualdades $\frac{-1}{\phi} < y < \frac{1}{\phi^2}$.
Reclamo: siempre Tenemos $\delta, \epsilon \in \{-1,0,1\}$. Además, si $0 < x < \frac{1}{\phi^2}$ y, o bien $\frac{-1}{\phi^2} \le y \le \frac{1}{\phi} - \frac{x}{\phi}$ o $\frac{-1}{\phi} < y \le \frac{-1}{\phi^2} - \frac{x}{\phi}$,, a continuación, $\delta \ge 0$ e $\epsilon \le 0$.
Prueba de Siniestro: Para la primera parte, tenga en cuenta que
$a_n - a_{n+5} = (a_n - \frac{a_{n+1}}{\phi} + a_{n+2}) + \frac{1}{\phi}(a_{n+1} - \frac{a_{n+2}}{\phi} + a_{n+3}) - \frac{1}{\phi}(a_{n+2} - \frac{a_{n+3}}{\phi} + a_{n+4}) - (a_{n+3} - \frac{a_{n+4}}{\phi} + a_{n+5}),$
que se entre $-1-\frac{1}{\phi}$ e $1+\frac{1}{\phi}$ por supuesto. Por lo tanto $|\epsilon| = |a_{n+5}-a_n| \le 1$ (ya que es un número entero).
Ahora supongamos que $0 < x < \frac{1}{\phi^2}$ y, o bien $\frac{-1}{\phi^2} \le y \le \frac{1}{\phi} - \frac{x}{\phi}$ o $\frac{-1}{\phi} < y \le \frac{-1}{\phi^2} - \frac{x}{\phi}$. A continuación, vemos enseguida $\alpha = 0$, y de
$-1 < y \le \phi x + y \le \frac{1}{\phi} + \phi x - \frac{x}{\phi} = \frac{1}{\phi} + x < 1$,
vemos que
$\beta = \lceil\phi x + y\rceil = \begin{cases} 1 & \phi x + y > 0,\\ 0 & \phi x + y \le 0. \end{cases}$
A partir de esto, junto con la
$\gamma = \lceil -\phi x - \phi y + \frac{\beta}{\phi}\rceil = \lceil -(\phi x + y) + \frac{\beta-y}{\phi}\rceil$
y $y > \frac{-1}{\phi}$ nos puede mostrar fácilmente
$1 \ge \gamma \ge \begin{cases} 1 & y \le 0\\ 0 & y > 0.\end{cases}$
Que $\delta = \lceil x + \phi y + \frac{\gamma}{\phi} - \beta\rceil$ al menos $0$ sigue de
$x + \phi y + \frac{\gamma}{\phi} - \beta = (\frac{\phi x + y}{\phi} - \beta) + (y + \frac{\gamma}{\phi}) > -1 + 0.$
Por último, debemos mostrar que $\epsilon =\lceil -y + \frac{\delta}{\phi} - \gamma\rceil$ es en la mayoría de las $0$. Nos hemos dividido en tres casos. Primer caso:
$\gamma = 0\implies y>0\implies \beta = 1\implies \delta = 0\implies \epsilon = \lceil -y \rceil = 0.$
Segundo caso:
$\gamma = 1\ \&\ y \ge \frac{-1}{\phi^2} \implies \epsilon \le \lceil \frac{1}{\phi^2} + \frac{1}{\phi} - 1\rceil = 0.$
Tercer caso:
$\gamma = 1\ \&\ y \le \frac{-1}{\phi^2} - \frac{x}{\phi} \implies \delta \le \lceil \frac{-1}{\phi} + \frac{1}{\phi} - \beta\rceil = 0 \implies \epsilon \le \lceil \frac{1}{\phi} - 1\rceil = 0.$
Corolario: Si $a_n = f_{2k}$ e $-f_{2k+2} \le a_{n-1} < f_{2k+3}-1$,, a continuación,$a_{n+5} \le a_n$.
Prueba: sólo Tenemos que comprobar que la reclamación se aplica. Tenemos $x = (\tfrac{-1}{\phi})^{2k} = \frac{1}{\phi^{2k}}$, tan sólo tenemos que comprobar que cualquiera de las $\frac{-1}{\phi^2} \le y \le \frac{1}{\phi} - \frac{1}{\phi^{2k+1}}$ o $y \le \frac{-1}{\phi^2} - \frac{1}{\phi^{2k+1}}.$
Supongamos primero que $a_{n-1} \ge 0$. Luego de $a_{n-1} < f_{2k+3} - 1 = \sum_{j=1}^{k+1} f_{2j}$, podemos ver que $y \le \sum_{j=1}^k \frac{1}{\phi^{2j}} = \frac{1}{\phi} - \frac{1}{\phi^{2k+1}}.$
Ahora supongamos que $a_{n-1} < 0$. Tenga en cuenta que en este caso automáticamente hemos $y \le \frac{1}{\phi^2} \le \frac{1}{\phi} - \frac{1}{\phi^{2k+1}}.$ Escritura $a_{n-1} = -\sum_{j\in J} f_j$ para algunos $J \subseteq \{2,3,...\}$ con $J\cap (J+1) = \emptyset.$ Si $2 \not\in J$,, a continuación,$y > -\frac{1}{\phi^4}-\frac{1}{\phi^6} -\cdots = -\frac{1}{\phi^3} > -\frac{1}{\phi^2}$. Si $J = \{2\}$ o si $2\in J$ y el segundo elemento más pequeño de $J$ es impar, entonces tenemos $y \ge -\frac{1}{\phi^2}$ así. Ahora supongamos que $2\in J$ y el siguiente elemento más pequeño de $J$ es $2l$. Desde $a_{n-1} \ge -f_{2k+2}$, debemos tener $l \le k$, por lo que
$y < \frac{-1}{\phi^2} - \frac{1}{\phi^{2l}} + \frac{1}{\phi^{2l+3}} + \frac{1}{\phi^{2l+5}} + \cdots = \frac{-1}{\phi^2} - \frac{1}{\phi^{2l+1}} \le \frac{-1}{\phi^2} - \frac{1}{\phi^{2k+1}}.$
Para terminar: tenga en cuenta que si $a_n = f_{2k}$ e $a_{n-1}, a_{n+1} \le f_{2k}$,, a continuación,$a_{n-1} + a_{n+1} = f_{2k-1}$, lo $-f_{2k-2} \le a_{n-1} \le f_{2k},$ y podemos aplicar el Corolario a ver que $a_{n+5} \le f_{2k}.$ Del curso, si $a_n < f_{2k}$ entonces tenemos $a_{n+5} \le a_n+1 \le f_{2k}$ (por la Demanda) así.
Esto es realmente más de un comentario extendido, pero sería desagradable para escribir en ese formato. Estoy comentando en la sugerencia de Peter Mueller, para argumentar que el límite de los triángulos construye va al límite.
Aunque no tengo una respuesta completa, aquí es un plausible de la línea de ataque, la cual se aclara el papel de los números de Fibonacci.
Permítanme definir $\epsilon_n=a_{n-1}-wa_n+a_{n+1}$ a ser los "términos de error" de la recursividad. Entonces tenemos $$ a_2-a_7 = \epsilon_3+w\epsilon_4-w\epsilon_5-\epsilon_6. $$ Me gustaría mostrar (entre otras cosas) que si $a_2=F_{2i+1}-1$ e $-a_2\leq a_1\leq a_2$ entonces $a_2-a_7\geq 0$. Para esto, considere la posibilidad de $$\epsilon_3+w\epsilon_4=a_2+w(a_4+a_5).$$ Este se encuentra en $a_2+ w\mathbb Z$.
La naturaleza de la $a_2=F_{2i+1}-1$ (creo) de tal manera que la parte fraccionaria de $a_2/w$ está cerca de a $1$. De hecho, no es posible lograr mayor parte fraccionaria con pequeños números enteros positivos. Como consecuencia, desde $\epsilon_3+w\epsilon_4$ es positivo, va a ser más grande que la de $w$ o, al menos, muy cerca de la $w$.
Cuando se combina esto con $-w e_5-e_6$ cuales son en la mayoría de las $-w$ e $-1$, pero no puede estar demasiado cerca de ellos, vemos que, en general, tenemos $a_2-a_7>-1$, como se desee.
El diablo está en los detalles, por supuesto. Debemos ser específicos en cuanto a cómo cerrar $\epsilon_5,\epsilon_6$ podría ser a $1$: aquí es donde el obligado en $a_1$ debe venir en. Parece tedioso, pero factible. Hay otras desigualdades para comprobar, pero supongo que ideas similares podría hacer el trabajo.
