Romanian Master of Mathematics

The identity is the only surjection of the positive integers onto themselves sending every sum-free set onto a sum-free set (no verification is needed, of course). To prove this, fix a function $f$ satisfying the conditions in the statement, and proceed in several steps.

Step 1. Notice that a 2-element set $\{x,y\}$, where $x<y$, is not sum-free if and only if $y=2x$.

Choose any $a\in \mathbb{N}$, and for any $i\ge 0$ choose some $x_i$ such that $f(x_i)=2^{i}a$. The set $f(\{x_i,x_{i+1}\})$ is not sum-free, so neither is $\{x_i,x_{i+1}\}$, whence $x_i=2x_{i+1}$ or $x_{i+1}=2x_i$. Since the $x_i$ are all distinct, the same option should hold for all $i$. The former option yields $x_i=x_0{2}^{-i}$ which cannot hold for large enough $i$. So $x_{i+1}=2x_i$ for all $i$. Therefore, $f(2x)=2f(x)$ for all $x$, and, moreover, $x$ is the only argument $t$ with $f(t)=f(2x)/2$. Therefore, $f$ is injective (and hence bijective).

Step 2. Say that a 3-element set $\{a,b,c\}$ is good if it is not sum-free, but each of its 2-element subsets is (in other words, no element is twice another). It is easily seen that a set $\{a,b,c\}$, where $a<b$, is good only if $c=b\pm a$. Notice that the pre-image of a good set is also a good set, due to Step 1. Now let $f(1)=a$. We show that $f(n)=an$ by induction on $n$. The base cases are $n=1,2,3,4,5$; for $n=1,2,4$ the result follows from Step 1. Set $t=f^{-1}(3a)$ and $s=f^{-1}(5a)$. The sets $\{a,4a,3a\}$ and $\{a,4a,5a\}$ are good, hence so are $\{1,4,t\}$ and $\{1,4,s\}$. Therefore, $\{s,t\}=\{3,5\}$. But the set $\{a,5a,6a\}$ is also good, so the pair $\{1,s\}$ is contained in one more good set, which is not the case if $s=3$, since $\{1,3\}$ is contained in one single good set, namely, $\{1,4,3\}$. Thus $t=3$ and $s=5$, which establishes the base. For the induction step, assume that $f(k)=ak$ for all $k\le n$, where $n\ge 5$. Choose $t=f^{-1}((n+1)a)$. Then the pair $\{a,na\}$ is contained in two good sets, namely, $\{a,na,(n-1)a\}$ and $\{a,na,(n+1)a\}$. Their pre-images, $\{1,n,n-1\}$ and $\{1,n,t\}$, are also good, and injectivity of $f$ forces $t=n+1$. This completes the induction step. Finally, since $f$ is surjective, $1=f(n)=an$ for some positive integer $n$, so $a=1=n$. Consequently, $f$ is the identity, as claimed at the beginning of the solution.

---

Alternative solution.

The approach is similar to Solution 1, but avoids directly defining and working with good sets. Step 1 in Solution 1 is proved similarly. For any odd integer $a\ge 3$, we claim $f(a)+f(1)$ is equal to one of $f(a+1)$ and $f(a-1)$. Indeed, its preimage should, together with $a$ and $1$, form a set that is not sum-free. $f(a)+f(1)=f(2a)=2f(a)$ contradicts injectivity, as does $f(a)+f(1)=f(2)=2f(1)$, hence $f(a)+f(1)=f(a+1)$ or $f(a)+f(1)=f(a-1)$.

$f(2)=2f(1)$, contradicting injectivity. Therefore, $f(a)+f(1)=f(a+1)$ for all odd integers $a$. Finally, we prove $f(n)=nf(1)$ by induction. Indeed, assume the statements holds for all integers up to some even $n$. The base case for $n\in \{1,2\}$ holds by Step 1 of Solution 1. Then, by assumption, $$f(n+1)+f(1)=f(n+2)=2f\left(\frac{n+2}{2}\right)=2\left(\frac{n+2}{2}\right)f(1)=(n+2)f(1),$$ implying $f(n+1)=(n+1)f(n)$ and, by the above result, $$f(n+2)=f(n+1)+f(1)=(n+2)f(1),$$ completing the induction.

Assume that $f(a)+f(1)=f(a-1)$ for some odd integer $2$. Inducting backwards, we see the statement holds for all odd integers up to $a$, in particular $f(3)+f(1)=$

The conclusion now follows as in Solution 1.