Infinitos puntos en una línea (Concurso de Matemáticas)

Question

Hoy en día, América Central y el Caribe Olimpiada matemática se celebró en El Salvador.

El Problema 6, fue como sigue:

Deje $k$ ser un número entero mayor que $1$. Inicialmente, Tita la rana sentada en el punto k en el número de línea. En un solo movimiento, si Tita se encuentra en el punto de $n$, luego salta hasta el punto de $f(n)+g(n)$ donde $f(n)$ $g(n)$ son el mayor y el menor primos divisores (ambos positivos) de $n$, respectivamente. Determinar todos los valores de $k$ para que Tita se visita una infinidad de distintos puntos en la recta numérica.

Answer 1

Tita se visita sólo un número finito de puntos distintos para cualquier $k>1$. Para probar esto, para cualquier $k>1$ vamos a definir una secuencia de forma recursiva por: $s_{0,k}\doteq k$, $s_{n+1,k} \doteq f(s_{n,k})+g(s_{n,k})$ para cualquier $n \geq 0$. Así que queremos mostrar a $(s_{n,k})$ tiene sólo un número finito de términos distintos para cualquier $k$.

En primer lugar, vamos a probar el siguiente instrucción: Para cualquier $k>1$, $(s_{n,k})$ es, finalmente, constante o hay un $n \in \mathbb{N}$ tal que $s_{n,k} \leq k$.

$\textit{Proof:}$ Si $k$ no es primo, entonces $f(k), g(k) \leq \frac{k}{2}$, lo $s_{1,k} \leq k$ y hemos terminado, así que supongo $k$ es primo. Para simplificar las cosas, supongamos $k \geq 12$ (la afirmación se comprueba fácilmente para el prime $k<12$).

Desde $k$ es primo, tenemos $s_{2,k}=k+2$. Si $k+2$ no es primo, entonces $s_{3,k} \leq k+2$. En este caso, si $s_{3,k}=k+2$ lo hace desde $(s_{n,k})$, entonces sería eventualmente constante. Del mismo modo, si $s_{3,k} \leq k$ lo que también se hace, así que la única opción a considerar es $s_{3,k}=k+1$. Entonces tendríamos $2| s_{3,k}$, por lo que el $s_{4,k} \leq 2+ \frac{k+1}{2} \leq k$. Esto cubre el caso al $k+2$ no es primo, por lo que ahora vamos a considerar el caso restante.

Si $k+2$ es primo, entonces $s_{4,k}=k+4$. Nota entonces que, puesto que tanto $k$ $k+2$ es de los primeros, $k+4$ no puede ser primo. A continuación,$g(k+4) \leq \sqrt{k+4}$$f(k+4) \leq \frac{k+4}{2}$, lo $s_{5,k} \leq \sqrt{k+4}+ \frac{k+4}{2} \leq k$ (desde $k \geq 12)$. $\Box$

La demanda original, sigue ahora de una manera rápida argumento inductivo.

Answer 2

Vamos a demostrar que no hay valor entero $k$ toma en infinidad de valores. Vamos a llamar a todos los números de "escapar al infinito". Por otra parte, se denota la transición de la función de $f(n)+g(n)$$t(n)$. Un número $x$ es un sucesor de $y$ si existe un entero $l$ tal que $x = t^{(l)} (y)$.

La idea principal utilizado en la prueba de ello es que para cualquier número que se escapa al infinito, todos los sucesores de él también escapar al infinito.

Basta de no mostrar los números primos escapar al infinito. Esto es como para cualquier compuesto $k$, $t(k) \leq k$, por lo tanto debe tener un primer sucesor.

Del mismo modo, es suficiente para mostrar que ningún extraño compuestos de la forma $p+2$ donde $p$ es primo, se escapa al infinito. Esto sigue como $t(t(p)) = p+2$ y el incluso el primer 2 puede ser calculada para que no escape al infinito.

Sin embargo, para un número impar de la forma $p+2$ a escapar hacia el infinito, debe tener un sucesor de la forma $q+2$ donde $q$ es una extraña primer y $q > p$, pero esto no es posible ya que observamos $t(t(p+2)) = \frac{f(n)+g(n)}{2} + 2 \leq p+2$. Así que no hay tal $q$ existen.