Solution:

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 $k<k_{0}$. We define new function $g: \mathbb{N} \rightarrow \mathbb{N}$ by $g(n)=f\left(2^{k_{0}} n\right)-k_{0}$. By induction hypothesis $g$ indeed maps to $\mathbb{N}$. In addition, on the set of all integers not divisible by $2^{k_{0}}$, the values of $f$ are smaller than $k_{0}+1$. Values greater or equal to $k_{0}+1$ are thus attained by $f$ on the set of integers divisible by $2^{k_{0}}$, making $g$ surjective. A straightforward verification shows that $g$ also satisfies the remaining condition of the initial problem. So $g(n)=1$ if $n$ is odd and $g(n)>1$ 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}} 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.

Like in Solution 1 we prove that
$$f(\text{ odd })=1, \quad \text{ and } \quad f(\text{ even })>1$$
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 $k<k_{0}$. Induction step is proved similarly as above. Suppose $f\left(2^{k_{0}}\right) \neq k_{0}+1$, meaning that $f\left(2^{k_{0}}\right)>k_{0}+1$. Surjectivity of $f$ implies, that there exists positive integer $b$ such that $f(b)=k_{0}+1$. By induction hypothesis $b$ is of the form $b=2^{k_{0}} r$ for some $r$ ($r$ may be odd or even). Considering the pair $\left(2^{k_{0}}, b\right)$ we get $f\left(2^{k_{0}}(r+1)\right)=f\left(b+2^{k_{0}}\right)=\min \left\{f\left(2^{k_{0}}\right), f(b)\right\}=k_{0}+1$. By induction we get $f\left(2^{k_{0}} r'\right)=k_{0}+1$ for all $r' \geqslant r$, contradicting the surjectivity of $f$. Hence $f\left(2^{k_{0}}\right)=k_{0}+1$. Conditions of the problem and induction hypothesis imply that $f(n)=k_{0}+1$ iff $f\left(n+2^{k_{0}}\right)>k_{0}+1$. Therefore it follows inductively that $f\left(2^{k_{0}} l\right)=k_{0}+1$ for odd $l$ and $f\left(2^{k_{0}} m\right)>k_{0}+1$ for even $m$, which finishes the induction step.
It is easy to check that the function defined by $f\left(2^{k_{0}} l\right)=k_{0}+1$ for odd $l$ indeed satisfies the conditions of the problem.

Solution:

Like in Solution 1 we prove that $f($ odd $)=1$, and $f($ even $)>1$. Define a sequence of functions $g_{k}: \mathbb{N} \rightarrow \mathbb{N}$ by
$$g_{0}(n)=f(n) \quad \text{ and } \quad g_{k}(n)=g_{k-1}(2 n)-1, \quad \text{ for } k \in \mathbb{N}$$
Using the first part of the solution we prove by induction that all $g_{k}$ satisfy the initial conditions of the problem (they map to $\mathbb{N}$, are surjective and satisfy the mutually exclusive equations). It follows from the first part of the solution that $g_{k}($ odd $)=1$ for all $k=0,1,2, \ldots$ From $g_{k}(l)=1$ for odd $l$ we inductively obtain $f\left(2^{k} l\right)=k+1$ by backward substitution. This shows that the problem has a unique solution given by $f\left(2^{k} l\right)=k+1$ for all $k \geqslant 0$ and all odd $l$. It is easy to check that this function indeed satisfies the conditions of the problem.

Solution:

Plugging pair $(a, a)$ into the given equations we obtain $f(2 a) \neq \min \{f(a), f(a)\}=f(a)$, in particular $f(4 a) \neq f(2 a)$. From pair $(a, 2 a)$ we get $f(3 a)=f(2 a+a)=\min \{f(2 a), f(a)\}$. Suppose $f(2 a)<f(a)$. Then $f(3 a)=f(2 a) \neq f(a)$. Considering pair $(a, 3 a)$ we thus get $f(4 a)=\min \{f(a), f(3 a)\}=f(2 a)$, a contradiction. Hence $f(2 a)>f(a)$.

Next we prove by induction on $l$ that $f(l a)=f(a)$ for all odd $l$. For $l=1$, there is nothing to show. We assume that $f((l-2) a)=f(a)$. As $f(2 a)>f(a)$, we have
$$f(l a)=\min \{f((l-2) a), f(2 a)\}=\min \{f(a), f(2 a)\}=f(a)$$
which proves the induction step.

Let now $n=2^{k} l$ for odd $l$. By the above we have $f(n)=f\left(2^{k}\right)$. Thus we only have to determine $f\left(2^{k}\right)$ for $k \geqslant 0$. Since $f(2 a)>f(a)$ for all $a$, $f\left(2^{k}\right)$ is increasing in $k$. By surjectivity, the only solution is $f\left(2^{k}\right)=k+1$. It is easily seen that $f\left(2^{k} l\right)=k+1$ is indeed a solution.