Olympiad Maths Prep

Track / Stage 6 / 232 of 400 #1232 of 2000

Problem 1232

National olympiad, first round
Combinatorics Difficulty 6.4 Find the answer

Find all injective functions f:NN f:\mathbb{N} \to \mathbb{N} such that ff(a)(b)ff(b)(a)=(f(a+b))2 f^{f\left(a\right)}\left(b\right)f^{f\left(b\right)}\left(a\right)=\left(f\left(a+b\right)\right)^2 holds for all a,bN a,b \in \mathbb{N} . Note that fk(n) f^{k}\left(n\right) means f(f(fk(n))) \underbrace{f(f(\ldots f}_{k}(n) \ldots ))

Official solution

1. Initial Setup and Definitions:
We are given the functional equation:
ff(a)(b)ff(b)(a)=(f(a+b))2 f^{f(a)}(b) f^{f(b)}(a) = (f(a+b))^2
for all a,bNa, b \in \mathbb{N}, where fk(n)f^k(n) denotes the kk-th iterate of ff applied to nn.

2. Injectivity and Initial Claims:
- Claim: f(x)1f(x) \neq 1 for all xx.
- Proof: Suppose f(k)=1f(k) = 1 for some kk. Then, using the functional equation with a=b=ka = b = k:
ff(k)(k)ff(k)(k)=(f(2k))2    f(k)f(k)=(f(2k))2    1=(f(2k))2 f^{f(k)}(k) f^{f(k)}(k) = (f(2k))^2 \implies f(k) f(k) = (f(2k))^2 \implies 1 = (f(2k))^2
This implies f(2k)=1f(2k) = 1, which contradicts the injectivity of ff since f(k)=f(2k)=1f(k) = f(2k) = 1. Therefore, f(x)1f(x) \neq 1 for all xx. \blacksquare

- Claim: f(1)=2f(1) = 2.
- Proof: Suppose f(1)2f(1) \neq 2. Consider the functional equation with a=b=1a = b = 1:
ff(1)(1)ff(1)(1)=(f(2))2    (ff(1)(1))2=(f(2))2 f^{f(1)}(1) f^{f(1)}(1) = (f(2))^2 \implies (f^{f(1)}(1))^2 = (f(2))^2
Since ff is injective, ff(1)(1)=f(2)f^{f(1)}(1) = f(2). If f(1)=kf(1) = k, then fk(1)=f(2)f^k(1) = f(2). If k>2k > 2, this would imply a contradiction as ff would not be injective. Therefore, f(1)=2f(1) = 2. \blacksquare

3. Functional Equation Analysis:
- Using P(a,1)P(a, 1):
ff(a)(1)f2(a)=(f(a+1))2 f^{f(a)}(1) f^2(a) = (f(a+1))^2
- Using P(a,a)P(a, a):
ff(a)(a)ff(a)(a)=(f(2a))2    (ff(a)(a))2=(f(2a))2    ff(a)(a)=f(2a) f^{f(a)}(a) f^{f(a)}(a) = (f(2a))^2 \implies (f^{f(a)}(a))^2 = (f(2a))^2 \implies f^{f(a)}(a) = f(2a)

4. Inductive Step:
- Base Case: We have f(1)=2f(1) = 2 and f(2)=3f(2) = 3.
- Inductive Hypothesis: Assume f(n)=n+1f(n) = n+1 for all ntn \leq t.
- Inductive Step: We need to show f(t+1)=t+2f(t+1) = t+2.
- Using P(t,1)P(t, 1):
ff(t)(1)f2(t)=(f(t+1))2 f^{f(t)}(1) f^2(t) = (f(t+1))^2
Since f(t)=t+1f(t) = t+1, we have:
ft+1(1)f2(t)=(f(t+1))2 f^{t+1}(1) f^2(t) = (f(t+1))^2
Given f2(t)=f(f(t))=f(t+1)f^2(t) = f(f(t)) = f(t+1), we get:
ft+1(1)f(t+1)=(f(t+1))2 f^{t+1}(1) f(t+1) = (f(t+1))^2
Since ft+1(1)=t+2f^{t+1}(1) = t+2, we have:
(t+2)f(t+1)=(f(t+1))2    t+2=f(t+1) (t+2) f(t+1) = (f(t+1))^2 \implies t+2 = f(t+1)
Thus, f(t+1)=t+2f(t+1) = t+2.

5. Conclusion:
By induction, we have shown that f(n)=n+1f(n) = n+1 for all nNn \in \mathbb{N}.

The final answer is f(x)=x+1\boxed{f(x) = x+1}.

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic, difficulty and ordering added by this site.