Home > Uncategorized > Balkan Mathematica Olympiad 2017 – Problem 3

Balkan Mathematica Olympiad 2017 – Problem 3

Problem 3. Let ${\mathbb{N}}$ denote the set of positive integers. Find all functions ${f:\mathbb{N}\longrightarrow\mathbb{N}}$ such that

$\displaystyle n+f(m)\mid f(n)+nf(m)$

for all ${m,n\in \mathbb{N}}$

Solution: Note that we obviously have

$\displaystyle n+f(m) | n^2+nf(m)$

and using the hypothesis we obtain that

$\displaystyle n+f(m) | f(n)-n^2,$

for every ${n,m \in \Bbb{N}}$. Now we have two options. Suppose the image of ${f}$ is unbounded. Then, since if we fix ${n}$ it would follow that ${f(n)-n^2}$ has arbitrarily large divisor, which is not possible unless ${f(n)=n^2}$. This is one solution, as it can easily be checked.

The other alternative is that ${f(\Bbb{N})}$ is bounded. If this is true, then there is a value of ${f}$ which is repeated for an infinite increasing sequence ${n_k}$: ${f(n_k) = M}$. It follows that

$\displaystyle n_k + f(m) | M+n_k f(m)$

for every ${m}$ and for ${n_k}$ defined as above. Since the fraction

$\displaystyle \frac{M+n_kf(m)}{n_k+f(m)}$

is an integer and it converges to ${f(m)}$ as ${n_k \rightarrow \infty}$ it follows that for ${n_k}$ large enough we have ${f(m)n_k +f(m)^2 = M+n_kf(m)}$. This implies that ${f(m)^2 = M}$, and this is independent of ${m}$. Therefore ${f}$ is constant. From the previous relation we have ${f(m)^2 = M = f(m)}$ so the only possible constant is ${f\equiv 1}$.