Problem 1074

Solution 1. Each positive integer can be uniquely written as $n=2^{k} l$ where $k \geqslant 0$ and $l$ is odd. We will show that the only function satisfying the conditions is $f\left(2^{k} l\right)=k+1$ for all $k \geqslant 0$ and all odd $l$.

Assume that $f(1) \neq 1$. Since $f$ is surjective, there exists $a \in \mathbb{N}$ such that $f(a)=1$. Since $f(1) \neq 1=f(a)$, we get $f(a+1)=\min \{f(a), f(1)\}=1$, and inductively we get $f(n)=1$ for each $n \geqslant a$. However, this contradicts the surjectivity of $f$.

Therefore $f(1)=1$. Then $f(2) \neq \min \{f(1), f(1)\}=1$, and $f(3)=\min \{f(1), f(2)\}=1$. Now it easily follows by induction that $f(n)=1$ if $n$ is odd and $f(n)>1$ if $n$ is even.

We will show by induction on $k$ that $f\left(2^{k} l\right)=k+1$ for all odd $l$ and $f\left(2^{k} m\right)>k+1$ for all even $m$. The basis of induction has been proved above. Assume that the statement holds for all $k1$ if $n$ is even, as we have shown above. Therefore $f\left(2^{k_{0}} l\right)=k_{0}+1$ for odd $l$ and $f\left(2^{k_{0}} \mathrm{~m}\right)>k_{0}+1$ for even $m$, which completes the induction. It is easy to check that this function indeed satisfies the conditions of the problem.