Maths Olympiad Prep

Library / /334 of 397

Algebra Difficulty 6.8 National Olympiad Prove it Taiwan

Let NN denote the set of all positive integers. Find all one-to-one functions f:NNf: N \to N such that
ff(a)(b)ff(b)(a)=(f(a+b))2 f^{f(a)}(b) f^{f(b)}(a) = (f(a+b))^2
holds for all positive integers a,ba, b. Here fk(n)f^k(n) denotes f(f(f(n)))k\underbrace{f(f(\dots f(n)\dots))}_{k}

Solution

Answer: f(n)=n+1f(n) = n+1, for all positive integers nn.

Let ff be such a solution.

First step. The pre-image of 1 is empty.

Obviously, if there is an integer xx so that f(x)=1f(x) = 1. Set a=b=xa = b = x into (1), then
f(2x)2=ff(x)(x)ff(x)(x)=f(x)2=1 f(2x)^2 = f^{f(x)}(x) f^{f(x)}(x) = f(x)^2 = 1
This implies f(2x)=1f(2x) = 1. But, it's impossible since ff is injective, as desired.

Second step. ff(n)1(n)=2nf^{f(n)-1}(n) = 2n for all nNn \in N. Moreover, f(1)=2f(1) = 2

It's also clear. Set a=b=na = b = n into (1) and use the injectivity of ff:
ff(n)(n)2=f(2n)2ff(n)(n)=f(2n)ff(n)1(n)=2n(1) f^{f(n)}(n)^2 = f(2n)^2 \rightarrow f^{f(n)}(n) = f(2n) \rightarrow f^{f(n)-1}(n) = 2n \quad (1)
In particular, there is an integer cc such that f(c)=2f(c) = 2. Then
2c=ff(c)1(c)=f(c)=2. 2c = f^{f(c)-1}(c) = f(c) = 2.
So c=1c=1, as desired.

Third step. The pre-image of 5 is non-empty.

According to the previous work, we get that the pre-images of even integers are non-empty. There must be an integer dd such that f(d)=4f(d) = 4. By using (1),
2d=ff(d)1(d)=f3(d)=f2(4)(2) 2d = f^{f(d)-1}(d) = f^3(d) = f^2(4) \qquad (2)
Substitute a=1,b=4a = 1, b = 4 into the problem statement:
f2(4)ff(4)(1)=f(5)2(3) f^2(4) f^{f(4)}(1) = f(5)^2 \qquad (3)
Combining the problem statement with (1), it follows f(5)f(5) is an even integer, say 2e2e. By (1) again,
f(5)=2e=ff(e)1(e) f(5) = 2e = f^{f(e)-1}(e)
Clearly, e1e \neq 1 since ff is injective, so f(e)>2f(e) > 2 and 55 is in the image of ff.

Because the pre-image of 1 is empty, f2(g1)f^2(g-1) and ff(g1)(1)f^{f(g-1)}(1) both are
3. Notice that
f2(g1)=3=f(g)f(g1)=g f^2(g-1) = 3 = f(g) \rightarrow f(g-1) = g
Furthermore, take a=2,b=g2a = 2, b = g - 2 in the problem statement
f5(g2)ff(g2)(2)=f(g)2=9(5) f^5(g-2) f^{f(g-2)}(2) = f(g)^2 = 9 \quad (5)
By the result of the first step, we then get
fg(1)=ff(g1)(1)=3=ff(g2)(2)=ff(g2)+1(1) f^g(1) = f^{f(g-1)}(1) = 3 = f^{f(g-2)}(2) = f^{f(g-2)+1}(1)
Therefore, f(g2)f(g-2) equals to g1g-1. Also, (3) tells us
3=f5(g2)=f2(3). 3 = f^5(g-2) = f^2(3).
Since
ff(3)1(3)=6 f^{f(3)-1}(3) = 6
The only possibility is f(3)=6f(3) = 6. This means e=92e = \frac{9}{2}, which is absurd!

fh(1)=ff(h1)(1)=5=ff(h2)(2)=ff(h2)(2)=ff(h2)+1(1) f^h (1) = f^{f(h-1)} (1) = 5 = f^{f(h-2)} (2) = f^{f(h-2)} (2) = f^{f(h-2)+1} (1)
which implies f(h2)=h1f(h-2) = h-1. And we'll have
5=ff(2)(h2)=ff(2)3(5) 5 = f^{f(2)} (h-2) = f^{f(2)-3} (5)
If f(2)3f(2) \neq 3, then the sequence 5,f(5),f2(5),5, f(5), f^2(5), \dots contains only finite distinct values. On the other hand, (1) tells us that
ff(5)1(5)=10,ff(10)1(10)=20,,ff(52m)1(52m)=52m+1, f^{f(5)-1}(5) = 10, f^{f(10)-1}(10) = 20, \dots, f^{f(5 \cdot 2^m)-1}(5 \cdot 2^m) = 5 \cdot 2^{m+1}, \dots
In particular, the sequence 5,f(5),f2(5),5, f(5), f^2(5), \dots contains 52m5 \cdot 2^m for all mN{0}m \in N \cup \{0\}. Thus, our assumption is false. That is, f(2)=3f(2) = 3 and 4=ff(2)1(2)=f(3)4 = f^{f(2)-1}(2) = f(3)

Sixth step. f(n)=n+1f(n) = n+1 for all nNn \in N

We have shown that the statement f(n)=n+1f(n) = n+1 is true for n=1,2,3n = 1, 2, 3. Assume that it's true for all n<kn < k. If kk is odd, write k=2l+1k = 2l+1 take a=l,b=l+2a = l, b = l+2:
f(2l+2)2=ff(l)(l+2)ff(l+2)(l)=fl+1(l+2)fl+3(l)=fl+1(l+2)22l+2=fl+1(l+2)=f(2l+1) f(2l + 2)^2 = f^{f(l)}(l + 2) f^{f(l+2)}(l) = f^{l+1}(l + 2) f^{l+3}(l) = f^{l+1}(l + 2)^2 \\ \Rightarrow 2l + 2 = f^{l+1}(l + 2) = f(2l + 1)
For the other case: if k=2lk = 2l, take a=l,b=l+1a = l, b = l+1:
f(2l+1)2=ff(l)(l+1)ff(l+1)(l)=fl+1(l+1)22l+1=fl(l+1)=f(2l) f(2l + 1)^2 = f^{f(l)}(l + 1) f^{f(l+1)}(l) = f^{l+1}(l + 1)^2 \\ \Rightarrow 2l + 1 = f^l(l + 1) = f(2l)
Thus, use the principle of induction, the conclusion follows.

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 translated into English from zh; metadata (topic, difficulty) added by this project.