Infinite points in a line (Contest Math)

Question

Today, the Central American and Caribbean Mathematical Olympiad was held in El Salvador.

Problem 6 was as follows:

Let $k$ be an integer greater than $1$. Initially, Tita the frog is sitting at the point k on the number line. In one movement, if Tita is located on the point $n$, then she jumps to the point $f(n)+g(n)$, where $f(n)$ and $g(n)$ are the greatest and the least prime divisors (both positive) of $n$, respectively. Determine all the values of $k$ for which Tita will visit infinitely many distinct points on the number line.

Answer 1

We shall show that no integer value $k$ takes on infinitely many values. We shall call all such numbers "escaping to infinity". Moreover, we denote the transition function $f(n)+g(n)$ as $t(n)$. A number $x$ is a successor of $y$ if there exist an integer $l$ such that $x = t^{(l)} (y)$.

The main idea utilised in the proof is that for any number that escapes to infinity, all successors of it will also escape to infinity.

It suffices to show no primes escape to infinity. This is as for any composite $k$, $t(k) \leq k$, hence it must have a prime successor.

Similarly, it suffices to show that no odd composites of the form $p+2$, where $p$ is prime, escapes to infinity. This follows as $t(t(p)) = p+2$ and the even prime 2 can be computed to not escape to infinity.

However, for a odd number of the form $p+2$ to escape to infinity, it must have a successor of the form $q+2$ where $q$ is an odd prime and $q > p$, but this isn't possible as we note $t(t(p+2)) = \frac{f(n)+g(n)}{2} + 2 \leq p+2$. So no such $q$ exist.

Answer 2

Tita will visit only finitely many distinct points for any $k>1$. To prove this, for any $k>1$ let's define a sequence recursively by: $s_{0,k}\doteq k$, $s_{n+1,k} \doteq f(s_{n,k})+g(s_{n,k})$ for any $n \geq 0$. So we want to show $(s_{n,k})$ has only finitely many distinct terms for any $k$.

First, let's prove the following statement: For any $k>1$, $(s_{n,k})$ is either eventually constant or there is an $n \in \mathbb{N}$ such that $s_{n,k} \leq k$.

$\textit{Proof:}$ If $k$ is not prime, then $f(k), g(k) \leq \frac{k}{2}$, so $s_{1,k} \leq k$ and we are done, so suppose $k$ is prime. To make things easier, let's suppose $k \geq 12$ (the claim is easily verified for prime $k<12$).

Since $k$ is prime, we have $s_{2,k}=k+2$. If $k+2$ is not prime, then $s_{3,k} \leq k+2$. In this case, if $s_{3,k}=k+2$ we are done since $(s_{n,k})$ would then be eventually constant. Likewise, if $s_{3,k} \leq k$ we are also done, so the only option to consider is $s_{3,k}=k+1$. We would then have $2| s_{3,k}$, so that $s_{4,k} \leq 2+ \frac{k+1}{2} \leq k$. This covers the case when $k+2$ is not prime, so let's now consider the remaining case.

If $k+2$ is prime, then $s_{4,k}=k+4$. Note then that since both $k$ and $k+2$ are prime, $k+4$ cannot be prime. Then $g(k+4) \leq \sqrt{k+4}$ and $f(k+4) \leq \frac{k+4}{2}$, so $s_{5,k} \leq \sqrt{k+4}+ \frac{k+4}{2} \leq k$ (since $k \geq 12)$. $\Box$

The original claim now follows from a quick inductive argument.