Maths Olympiad Prep

Library / /216 of 397

, 2023

Algebra Difficulty 6.0 AIME, harder Prove it Taiwan

Denote the set of positive integers by N\mathbb{N}. Find all functions f:NNf : \mathbb{N} \to \mathbb{N} satisfying that for all m,nNm, 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 nNn \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 k2k \ge 2, contradict to the fact that ff is injective.

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.