Maths Olympiad Prep

Library / /138 of 397

Algebra Difficulty 5.5 AIME, harder Prove it Taiwan

Let Z,N0Z, N_0 be the sets of all integers and non-negative integers respectively.
Find all increasing functions f:N0Zf : N_0 \to Z such that
f(2)=7,f(mn)=f(m)+f(n)+f(m)f(n),m,nN0. f(2) = 7, \quad f(mn) = f(m) + f(n) + f(m)f(n), \quad \forall m, n \in N_0.

Solution

Answer: f(n)=n31,nN0f(n) = n^3 - 1, n \in N_0.

From the given conditions we observe that: f(0)=f(1)=0f(0) = f(1) = 0. For n2n \ge 2, define g(n)=f(n)+1g(n) = f(n) + 1. Then
g(2)=8g(2) = 8 and
g(mn)=f(mn)+1=f(m)+f(n)+f(m)f(n)+1=(f(m)+1)(f(n)+1)=g(m)g(n), for all m,n2. \begin{aligned} g(mn) &= f(mn) + 1 = f(m) + f(n) + f(m)f(n) + 1 \\ &= (f(m) + 1)(f(n) + 1) \\ &= g(m)g(n), \text{ for all } m, n \ge 2. \end{aligned}

Fix an integer n>2n > 2, and consider a sequence of rational numbers {pk/qk,k1}\{p_k/q_k, k \ge 1\}, each term of which is greater than log2n\log_2 n and which converges to log2n\log_2 n. Then from n<2pk/qkn < 2^{p_k/q_k} we get nqk<2pkn^{q_k} < 2^{p_k}, and by the monotonicity of gg we obtain
g(nqk)g(2pk). g(n^{q_k}) \le g(2^{p_k}).
By the multiplicativity of gg we get
g(n)g(2)pk/qk=23pk/qk=(2pk/qk)3. g(n) \ge g(2)^{p_k/q_k} = 2^{3p_k/q_k} = (2^{p_k/q_k})^3.
Letting kk \to \infty, then g(n)n3g(n) \le n^3. Arguing similarly, we get g(n)n3g(n) \ge n^3. Hence g(n)=n3g(n) = n^3. Therefore f(n)=n31,nf(n) = n^3 - 1, \forall n is the unique solution satisfying the given conditions.

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.