Maths Olympiad Prep

Library / /2 of 5

Algebra Difficulty 7.7 National olympiad, round 2 Prove it Romania

Let N\mathbb{N} be the set of all positive integers. A subset AA of N\mathbb{N} is sum-free if, whenever xx and yy are (not necessarily distinct) members of AA, their sum x+yx+y does not belong to AA. Determine all surjective functions f:NNf: \mathbb{N} \to \mathbb{N} such that, for each sum-free subset AA of N\mathbb{N}, the image {f(a):aA}\{f(a): a \in A\} is again sum-free.
India, Sutanay Bhattacharya

Solutions — 2

Solution 1

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 ff satisfying the conditions in the statement, and proceed in several steps.

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

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

Step 2. Say that a 3-element set {a,b,c}\{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}\{a, b, c\}, where a<ba < b, is good only if c=b±ac = 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)=af(1) = a. We show that f(n)=anf(n) = an by induction on nn. The base cases are n=1,2,3,4,5n=1, 2, 3, 4, 5; for n=1,2,4n=1, 2, 4 the result follows from Step 1.
Set t=f1(3a)t = f^{-1}(3a) and s=f1(5a)s = f^{-1}(5a). The sets {a,4a,3a}\{a, 4a, 3a\} and {a,4a,5a}\{a, 4a, 5a\} are good, hence so are {1,4,t}\{1, 4, t\} and {1,4,s}\{1, 4, s\}. Therefore, {s,t}={3,5}\{s, t\} = \{3, 5\}. But the set {a,5a,6a}\{a, 5a, 6a\} is also good, so the pair {1,s}\{1, s\} is contained in one more good set, which is not the case if s=3s=3, since {1,3}\{1, 3\} is contained in one single good set, namely, {1,4,3}\{1, 4, 3\}. Thus t=3t=3 and s=5s=5, which establishes the base.
For the induction step, assume that f(k)=akf(k) = ak for all knk \le n, where n5n \ge 5. Choose t=f1((n+1)a)t = f^{-1}((n+1)a). Then the pair {a,na}\{a, na\} is contained in two good sets, namely, {a,na,(n1)a}\{a, na, (n-1)a\} and {a,na,(n+1)a}\{a, na, (n+1)a\}. Their pre-images, {1,n,n1}\{1, n, n-1\} and {1,n,t}\{1, n, t\}, are also good, and injectivity of ff forces t=n+1t = n+1. This completes the induction step.
Finally, since ff is surjective, 1=f(n)=an1 = f(n) = an for some positive integer nn, so a=1=na=1=n. Consequently, ff is the identity, as claimed at the beginning of the solution.

Solution 2

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 a3a \ge 3, we claim f(a)+f(1)f(a) + f(1) is equal to one of f(a+1)f(a+1) and f(a1)f(a-1). Indeed, its preimage should, together with aa and 11, form a set that is not sum-free. f(a)+f(1)=f(2a)=2f(a)f(a)+f(1) = f(2a) = 2f(a) contradicts injectivity, as does f(a)+f(1)=f(2)=2f(1)f(a)+f(1) = f(2) = 2f(1), hence f(a)+f(1)=f(a+1)f(a)+f(1) = f(a+1) or f(a)+f(1)=f(a1)f(a)+f(1) = f(a-1).

f(2)=2f(1)f(2) = 2f(1), contradicting injectivity. Therefore, f(a)+f(1)=f(a+1)f(a) + f(1) = f(a + 1) for all odd integers aa.
Finally, we prove f(n)=nf(1)f(n) = nf(1) by induction. Indeed, assume the statements holds for all integers up to some even nn. The base case for n{1,2}n \in \{1, 2\} holds by Step 1 of Solution 1. Then, by assumption,
f(n+1)+f(1)=f(n+2)=2f(n+22)=2(n+22)f(1)=(n+2)f(1), 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)f(n + 1) = (n + 1)f(n) and, by the above result,
f(n+2)=f(n+1)+f(1)=(n+2)f(1), f(n + 2) = f(n + 1) + f(1) = (n + 2)f(1),
completing the induction.

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

The conclusion now follows as in Solution 1.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.