Maths Olympiad Prep

Library / /207 of 397

Algebra Difficulty 5.9 AIME, harder Prove it Taiwan

Let NN denote the set of all positive integers. Find all functions f:NNf: N \rightarrow N satisfying: for all m,nNm, n \in N, f(m)+f(n)mn0f(m) + f(n) - mn \neq 0 and (f(m)+f(n)mn)(f(m) + f(n) - mn) divides (mf(m)+nf(n))(mf(m) + nf(n)).

Solution

f(n)=n2f(n) = n^2.

It is given that
(f(m)+f(n)mn)(mf(m)+nf(n)).(1) (f(m) + f(n) - mn) \mid (mf(m) + nf(n)). \quad (1)

1. Take m=n=1m = n = 1 in (1), we have 2f(1)12f(1)f(1)=12f(1) - 1 \mid 2f(1) \Rightarrow f(1) = 1.

2. Let pp be a prime number, and take (m,n)=(p,1)(m, n) = (p, 1), then we have f(p)1+ppf(p)+1f(p) - 1 + p \mid pf(p) + 1, which is
f(p)p+1pf(p)+1p(f(p)p+1)=p2p+1. f(p) - p + 1 \mid pf(p) + 1 - p(f(p) - p + 1) = p^2 - p + 1.
- If f(p)p+1=p2p+1f(p) - p + 1 = p^2 - p + 1, then f(p)=p2f(p) = p^2.
- If f(p)p+1p2p+1f(p) - p + 1 \neq p^2 - p + 1, since p2p+1p^2 - p + 1 is odd, we must have 3(f(p)p+1)(p2p+1)3(f(p) - p + 1) \leq (p^2 - p + 1), that is
f(p)13(p2+2p2)(2) f(p) \leq \frac{1}{3}(p^2 + 2p - 2) \quad (2)

Now, take m=n=pm = n = p in (1), we have 2f(p)p22pf(p)2f(p) - p^2 \mid 2pf(p). This implies
2f(p)p22pf(p)p(2f(p)p2)=p3. 2f(p) - p^2 \mid 2pf(p) - p(2f(p) - p^2) = p^3.
But by (2) and by the fact that f(p)1f(p) \geq 1, we have
p2<2f(p)p223(p2+2p2)p2<p -p^2 < 2f(p) - p^2 \leq \frac{2}{3}(p^2 + 2p - 2) - p^2 < -p
for p7p \geq 7. This contradicts to the fact that 2f(p)p22f(p) - p^2 is a factor of p3p^3.

Hence, we have proved that f(p)=p2f(p) = p^2 for all prime p7p \ge 7.

3. Now, fixed nn, and take prime p7p \ge 7. Set m=pm = p in (2), and we have
p2+f(n)pn=f(p)+f(n)pnpf(p)+nf(n)n(f(p)+f(n)pn)=pf(p)nf(p)+pn2=p(p2pn+n2). \begin{aligned} & p^2 + f(n) - pn \\ = & f(p) + f(n) - pn \mid p f(p) + n f(n) - n(f(p) + f(n) - pn) \\ = & p f(p) - n f(p) + pn^2 = p(p^2 - pn + n^2). \end{aligned}
However, we can take pp sufficiently large such that pf(n)p \nmid f(n), which means (p,p2pn+f(n))=1(p, p^2 - pn + f(n)) = 1, so p2pn+f(n)p2pn+n2p^2 - pn + f(n) \nmid p^2 - pn + n^2. Hence,
p2pn+f(n)p2pn+n2+(p2pn+f(n))=n2f(n). p^2 - pn + f(n) \nmid p^2 - pn + n^2 + (p^2 - pn + f(n)) = n^2 - f(n).
Since this must hold for all pp, but p2pn+f(n)p^2 - pn + f(n) \to \infty, the only possibility is n2f(n)=0n^2 - f(n) = 0, that is f(n)=n2f(n) = n^2.

4. The rest is to check that f(n)=n2f(n) = n^2 indeed satisfies the 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.