Bariz - Problem

Source: IGMO 2020 Round 2 P3

Tags: number theory, function, floor function

Mathological03

17.02.2021 19:11

Let's define a function $\phi: \mathbb{N} \to \mathbb{N}$, where $0 \notin \mathbb{N}$, as follows \[ \phi(n) = \sum_{k = 1}^n k! \]Let $\mathbb{V}$ be defined as the set of all triplets $(x,y,z) \in \mathbb{N}$ such that $\phi(x) = y^{z + 1}$. For a triplet $x,y,z$ (denoted by $v$) in $\mathbb{V}$, we define \[ f_v(n) = 8 \left \{ \frac{xy}{8} \right \} \lfloor \sqrt{n} \rfloor + \frac{zn}{z + x - y} \]Show that for any $v \in \mathbb{V}$ and $m \in \mathbb{N}$, the sequence \[ m, f_v(m), f_v(f_v(m)), f_v(f_v(f_v(m))), \dots \]contains at least one square of a natural numbers.

Note that for $n \ge 10$ we have $11 \mid \phi(n)$, but $11^2 \nmid \phi(n)$ (this can be easily checked without a computer by working modulo 11). So they are never perfect powers. Checking manually the cases $n \le 9$ we see that $\mathbb{V}$ only consists of $(3,3,1)$ and $(1,1,z)$ for any $z \in \mathbb{N}$. In both cases we have $f_v(n)=g(n):=\lfloor \sqrt{n}\rfloor+n$. So we really need to check that the sequence of iterates $n,g(n),g(g(n)),\dots$ contains a perfect square for every initial value $n$. But this is quite easy, analyzing the behaviour of $g$. Indeed, identifying $n$ with $(a,b)$ where $n=a^2+b$ and $0 \le b \le 2a$, the map $g$ is $(a,b) \mapsto \begin{cases} (a,b+a) & b \le a\\(a+1,b-a-1) & b \ge a+1 \end{cases}$. Suppose that for some initial value we never meet a square. Then it's easy to see that we change alternatingly between the two cases $b \le a$ and $b \ge a+1$. So in every second step we change from $(a,b)$ with $b \le a$ to $(a+1,b-1)$. Hence $b$ decreases by $1$ in each step but never reaches $0$ which is a fair contradiction.