It's easy to see that $f(n)=v_2(n)+1$ is a solution and we want to prove that it's the only one. Denote $P(a,b)$ the assertion that either $f(a)=f(b)$ either $f(a+b)=\min\{f(a),f(b)\}$. Define a function $g:\mathbb{N}_0 \to \mathbb{N}$ satisfying $g(n)=f(2^n)$. $P(a,a)$ implies that $f(a) \ne f(2a)$. $P(a,2a)$ implies that $f(3a) =\min\{f(a),f(2a)\}$ Assume $f(3a)=f(2a) < f(a)$ for some $a$. Then $P(a,3a)$ implies that $f(4a)=f(a)<f(2a)$ since $f(4a) \ne f(2a)$. So $f(a)<f(2a)<f(a)$. Absurd! Hence our assumtion must have been wrong and we conclude that $f(3a)=f(a)$ must hold for all $a$. Also $P(a,2a)$ implies $f(a)<f(2a)$ for all $a$. In particular, we conclude that $g$ is a strictly increasing function. Now we are going to prove by induction over $k$ that $f(n)=g(v_2(n))$ holds for all $n \le 2^k$. For $k=0,1,2$ we already proved it. Now we do the induction step from $k$ to $k+1$. Take any $a \in \{1,2,\dotsc,2^k-1\}$ and we want to prove $f(2^k+a)=g(v_p(2^k+a))$ i.e. $f(2^k+a)=g(v_p(a))$ i.e. $f(2^k+a)=f(a)$. Indeed, it is clear that $f(a) \ne f(2^k)$ and so $P(2^k,a)$ implies that $f(2^k+a)=\min\{f(2^k),f(a)\}=f(a)$ since $f(2^k)=g(k)>g(v_2(a))=f(a)$. So we proved the induction step and thus for all $n$ it holds $f(n)=g(v_2(n))$. But since $f$ is surjective, also $g$ must be surjective. As $g$ is also strictly increasing, the only possible function is $g(n)=n+1$ and hence $\boxed{f(n)=v_2(n)+1}$ which is indeed a solution.

randomusername wrote: Find all surjective functions $f:\mathbb{N}\to\mathbb{N}$ such that for all positive integers $a$ and $b$, exactly one of the following equations is true: \begin{align*} f(a)&=f(b), \\ f(a+b)&=\min\{f(a),f(b)\}. \end{align*} Remarks: $\mathbb{N}$ denotes the set of all positive integers. A function $f:X\to Y$ is said to be surjective if for every $y\in Y$ there exists $x\in X$ such that $f(x)=y$. Let $P(x,y)$ be the assertion ($f(x)=f(y)$ and $f(x+y)\ne\min(f(x),f(y))$) or ($f(x)\ne f(y)$ and $f(x+y)=\min(f(x),f(y))$) $P(x,x)$ $\implies$ $f(2x)\ne f(x)$ 1) $f(2n-1)=1$ and $f(2n)\ne 1$ $\forall n$ Since surjective, let $u>0$ such that $f(u)=1$ If $f(1)>f(u)=1$, then $P(u,1)$ $\implies$ $f(u+1)=\min(f(1),f(u))=1$ and so $f(x)=1$ $\forall x\ge u$. Impossible since surjective. So $f(1)=1$ (and $f(2)>1$) Let $u$ such that $f(u)=1$. $P(u,2)$ $\implies$ $f(u+2)=1$ and so $f(2n-1)=1$ $\forall n\in\mathbb N$ And also $f(2n)\ne 1$ $\forall n$ else $f(x)=1$ $\forall x\ge n$ (impossible since surjective) 2) $f(4n-2)=2$ and $f(4n)\ne 2$ $\forall n$ Since surjective, let $v>0$ such that $f(v)=2$ If $f(2)>f(v)=2$, then $P(v,2)$ $\implies$ $f(v+2)=\min(f(2),f(v))=2$ and so $f(x)\in\{1,2\}$ $\forall x\ge v$. Impossible since surjective. So $f(2)=2$ (and $f(4)>2$) Let $v$ (even)such that $f(v)=2$. $P(v,4)$ $\implies$ $f(v+4)=2$ and so $f(4n-2)=2$ $\forall n\in\mathbb N$ And also $f(4n)\ne 2$ $\forall n$ else $f(x)\in\{1,2\}$ $\forall x\ge n$ (impossible since surjective) 3) Result. The process 1) and 2) can easily be reproduced to show with induction the result : $\boxed{f(x)=v_2(x)+1\text{ }\forall x>0}$ which indeed is a solution Too late, I know

We can actually solve the problem with the weaker condition that at least one of the two conditions is satisfied, i.e. $f(a)\neq f(b)\implies f(a+b)=\min\{f(a),f(b)\}$. Fix some positive integer $M$, and let $m$ be the smallest value at which $f(m)$ is at least $M$. Let $f(m)=t$. Then $f(1),f(2),\dots,f(m-1)<M$. We will now prove by induction that from now on, $f(n)\ge t$ if $m\mid n$ and else $f(n)<M$. $(*)$ We will do this by looking at blocks of $m$. Note that $f(m+n)=\min\{f(n),f(m)\}=f(n)<t$ if $f(n)<t$, call this $(*)$. Because of $(*)$, we cannot have $m$ consecutive values of $f$ which are $<t$, because then the next $m$ values are also $<t$, and so on until infinity, which means $f$ attains finitely many values, contradicting the surjectivity. Moreover, if $f(km)\ge t$ for some positive integer $k$, then we have $f(km+r)=\min\{f(r),f(km)\}=f(r)<M$ for $0<r<m$. Now we cannot have $f((k+1)m)<t$ as it would give $m$ consecutive $<t$ values, so $f((k+1)m)\ge t$. By induction, our claim is proven. Also, if we'd have $M<t$, then $f$ wouldn't attain the value $M$, hence we must have $t=M$. This turns out to be enough to determine $f$. For $i=1,2,3,\dots$, denote $b_i$ as the smallest positive integer for which $f(b_i)=i$. Because of the above, $f(1)$ can only be $1$, else all the values would be $>1$. Also, $b_{i}\mid b_{i+1}$ because of the above, so let $a_i=\frac{b_i}{b_{i-1}}\ge 2$. Thus, $b_1=1$ and $b_i=a_ia_{i-1}\dots a_2$. Let $j$ be the largest $i$ such that $b_i\mid n$. Then $b_j\mid n$ implies $f(n)\ge j$ by $(*)$. Also, $f(n)<j+1$ because $b_{j+1}\not| n$. So $f(n)=j$. This function satisfies our condition because if $f(c)\neq f(d)$, say $i=f(c)<f(d)=j$, then $f(c+d)=i=\min\{f(c),f(d)\}$ because $b_i\mid c+d$, but if $b_{i+1}\mid c+d$, then as $b_{i+1}\mid b_j\mid d$, we get $b_{i+1}\mid c$, false. To solve the MEMO problem from here, we just need to note that $f(2n)\neq f(n)$, which follows from the MEMO problem's condition for $a=b$.

For $n\in \mathbb N$, let's define the sets $A_n=\left\{x\in\mathbb N\mid f(x)=n\right\}$ and $B_n=\left\{x\in\mathbb N\mid \nu_2(x)+1=n\right\}$. By induction on $n$, we'll prove that $A_n=B_n$ for all $n\in\mathbb N$. Interestingly enough, the base case $n=1$ is not trivial; at least, it's way more non-trivial than the actual induction step. Let's settle this case first. If $f(1)=a\neq 1$, then $1\in A_a$, and it's meaningful to consider the set $A_{a-1}$. Because of surjectivity, this set is nonempty; so let $x\in A_{a-1}$. Since $f(x)=f(1)\iff a-1=a$ doesn't hold, we must have $f(x+1)=\min\{f(x),f(1)\}=\min\{a-1,a\}=a-1$. Therefore $x\in A_{a-1}\implies x+1\in A_{a-1}$. Continuing ad infinitum, we see that all numbers from $x$ onwards map to $a-1$, so $f$ can only attain finitely many values; a contradiction to the surjectivity of $f$. So $a=1$ must hold. Now that we have figured out $f(1)=1$, let's see how many more values of $f$ we can ascertain. Note that: For any $x\in\mathbb N$, $f(x)=1=f(1)\implies f(x+1)\neq \min\{f(x),f(1)\}=1$. In other words, $x\in A_1\implies x+1\not\in A_1$. On the other hand, if $f(x)\neq 1=f(1)$, we must have $f(x+1)=\min\{f(x),f(1)\}=\min\{f(x),1\}=1$. Id est, $x\not\in A_1\implies x+1\in A_1$. These two points imply one thing; the elements of $\mathbb N$ alternately occur and don't occur in $A_1$. Since $1$ does occur in $A_1$, all odd numbers are in $A_1$, and none of the even numbers are in $A_1$; that is, $A_1=B_1$. Great thing. Next, suppose we have already proved $A_1=B_1,\cdots, A_m=B_m$. All the numbers of $\mathbb N$ that haven't found a home in the $A_i$'s yet are those divisible by $2^m$. Let's now define a function $g:\mathbb N\to\mathbb N$ as follows: $g(n)=f(2^mn)-m$. Note that this is a perfectly legit definition, because $2^mn\not\in B_i$ for any $1\le i\le m$, hence it's not in any of the corresponding $A_i$'s either, so $f(2^mn)>m$. This brand new function has some spectacular properties: $g$ is surjective, since $f$ takes all integer values$>m$ for arguments divisible by $2^m$; For any $(a,b)\in\mathbb N^2$, exactly one of the statements hold: $g(a)=g(b)$ or $g(a+b)=\min\{g(a),g(b)\}$, because, meh, it's merely a scaled and shifted version of $f$. Now that's interesting; $g$ satisfies the same conditions as $f$ itself. So by the exact same analysis as the base case, one can show that $g(n)=1\iff n$ is odd, i.e., $f(n)=m+1\iff \nu_2(n)=m$. In other words, $A_{m+1}=B_{m+1}$,completing the induction step. The result proved above trivially implies $\boxed{f(n)=\nu_2(n)+1}$, which fortunately, satisfies the given conditions. $\blacksquare$

randomusername wrote: We can actually solve the problem with the weaker condition that at least one of the two conditions is satisfied, i.e. $f(a)\neq f(b)\implies f(a+b)=\min\{f(a),f(b)\}$. Fix some positive integer $M$, and let $m$ be the smallest value at which $f(m)$ is at least $M$. Let $f(m)=t$. Then $f(1),f(2),\dots,f(m-1)<M$. We will now prove by induction that from now on, $f(n)\ge t$ if $m\mid n$ and else $f(n)<M$. $(*)$ We will do this by looking at blocks of $m$. Note that $f(m+n)=\min\{f(n),f(m)\}=f(n)<t$ if $f(n)<t$, call this $(*)$. Because of $(*)$, we cannot have $m$ consecutive values of $f$ which are $<t$, because then the next $m$ values are also $<t$, and so on until infinity, which means $f$ attains finitely many values, contradicting the surjectivity. Moreover, if $f(km)\ge t$ for some positive integer $k$, then we have $f(km+r)=\min\{f(r),f(km)\}=f(r)<M$ for $0<r<m$. Now we cannot have $f((k+1)m)<t$ as it would give $m$ consecutive $<t$ values, so $f((k+1)m)\ge t$. By induction, our claim is proven. Also, if we'd have $M<t$, then $f$ wouldn't attain the value $M$, hence we must have $t=M$. This turns out to be enough to determine $f$. For $i=1,2,3,\dots$, denote $b_i$ as the smallest positive integer for which $f(b_i)=i$. Because of the above, $f(1)$ can only be $1$, else all the values would be $>1$. Also, $b_{i}\mid b_{i+1}$ because of the above, so let $a_i=\frac{b_i}{b_{i-1}}\ge 2$. Thus, $b_1=1$ and $b_i=a_ia_{i-1}\dots a_2$. Let $j$ be the largest $i$ such that $b_i\mid n$. Then $b_j\mid n$ implies $f(n)\ge j$ by $(*)$. Also, $f(n)<j+1$ because $b_{j+1}\not| n$. So $f(n)=j$. This function satisfies our condition because if $f(c)\neq f(d)$, say $i=f(c)<f(d)=j$, then $f(c+d)=i=\min\{f(c),f(d)\}$ because $b_i\mid c+d$, but if $b_{i+1}\mid c+d$, then as $b_{i+1}\mid b_j\mid d$, we get $b_{i+1}\mid c$, false. To solve the MEMO problem from here, we just need to note that $f(2n)\neq f(n)$, which follows from the MEMO problem's condition for $a=b$. how did you strike with that non trivial observation of the weaker condition.

We claim the only solution is $f(x) = \nu_2(x) + 1$. Clearly this function does work. Now we prove it is the only one. We prove the same using induction. Base case (n = 1): Let $m$ be the smallest number such that $f(m) = 1$. If $m \ne 1$, then clearly $f(m+1) = \min\{f(1), f(m)\} = 1$, and so on, i.e. $f(x) = 1 \forall x \ge m$. However, in this case, $f$ would not be surjective. Therefore $m = 1$. Now we induct. If $x$ is even and $f(x-1) = 1$, then $f(1) = f(x-1) \implies f(x) \ne 1$, and for odd x $f(1) \ne f(x-1) \implies f(x) = f(1) = 1$. Inductive step: Let the statement hold for $n = 1, 2, \dots , k-1$. We now show it holds for $n = k$. Let $m_k$ be the smallest element such that $f(m_k) = k$. We claim that $m_k = 2^{n-1}$. Indeed, if this is not the case, $f(m_k + p*2^{n-1}) = k \forall p \in \mathbb{N}$in a similar argument as the base case, and so $f$ would not be surjective. Now from a similar argument as the base case, if $2^n \mid x$ and $f(x-2^{n-1}) = n$, then $f(x) \ne n$, and if $\nu_2(x) = n-1$, and $f(x-2^{n-1}) \ne n$, then $f(x) = n$. $\square$.