Maths Olympiad Prep

Library / Taiwan IMO Selection Camp /199 of 359

Taiwan IMO Selection Camp, 2023

Algebra Difficulty 6.0 AIME, harder Prove it Taiwan

Denote the set of positive integers by N\mathbb{N}. Find all functions f:N→Nf : \mathbb{N} \to \mathbb{N} satisfying that for all m,n∈Nm, n \in \mathbb{N}, ∣f(m+n)−f(m)∣|f(m+n) - f(m)| divides f(n)f(n).

Solution

From the assumptions of the problem, we have the following facts:
1. ff is injective
2. f(m+n)≤f(m)+f(n)f(m+n) \le f(m) + f(n)
3. ∣f(m+1)−f(m)∣≤f(1)|f(m+1) - f(m)| \le f(1)
4. (f(m+1)−f(1))∣f(m)(f(m+1) - f(1)) \mid f(m)
Since ff is injective, f(m+1)>3f(1)f(m+1) > 3f(1) for sufficiently large mm. Combine the above listed facts, we have
2f(1)<f(m+1)−f(1)∣∣f(m)−f(m+1)+f(1)∣≤2f(1) 2f(1) < f(m+1) - f(1) \mid |f(m) - f(m+1) + f(1)| \le 2f(1)
Therefore, we must have f(m)−f(m+1)+f(1)=0f(m) - f(m+1) + f(1) = 0. That is, f(m)=mf(1)+cf(m) = mf(1) + c for some constant cc for sufficiently large mm. Hence, for every sufficiently large m,nm, n, we have f(m+n)−f(m)=nf(1)f(m+n) - f(m) = nf(1) divides f(n)=nf(1)+cf(n) = nf(1) + c, cc is forced to be 0. Claim, that f(n)=nf(1)f(n) = nf(1) for all n∈Nn \in \mathbb{N}. Toward contradiction, assume nn to be the largest number such that f(n)≠nf(1)f(n) \ne nf(1). Fix a sufficiently large mm, we have nf(1)=f(m+n)−f(m)∣f(n)nf(1) = f(m+n) - f(m) \mid f(n), thus f(n)=knf(1)=f(kn)f(n) = knf(1) = f(kn) for some k≥2k \ge 2, contradict to the fact that ff is injective.

Want a route through all this instead of an archive? The track puts 2,604 problems in a working order, from Junior Challenge 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.