Maths Olympiad Prep

Track / Stage 7 / 151 of 300 #2031 of 2444

Problem 2031

National Olympiad second round; IMO P1/P4
Algebra Difficulty 7.5 Prove it Hkg TST · Hong Kong

Let ff be a function with the following properties:
(i) f(n)f(n) is defined for every positive integer nn;
(ii) f(n)f(n) is a positive integer;
(iii) f(f(m)+f(n))=m+nf(f(m) + f(n)) = m + n for all mm and nn.
Find f(1997)f(1997).

This one wants a proof. Work it on paper, then read the official solution and mark yourself. Be honest about it: the record is only any use to you if it is.

Next problem →

Official solution

We have f(1997)=1997f(1997) = 1997.

Label the equation as follows.
f(f(m)+f(n))=m+n(1) f(f(m) + f(n)) = m + n \quad (1)
If f(a)=f(b)f(a) = f(b) for some a,bZ+a, b \in \mathbb{Z}^+, then by putting m=am = a and m=bm = b in (1), we obtain
a+n=f(f(a)+f(n))=f(f(b)+f(n))=b+n. a + n = f(f(a) + f(n)) = f(f(b) + f(n)) = b + n.
This implies a=ba = b. So ff is injective. Now, using (1), we have
f(f(m+1)+f(1))=(m+1)+1=m+2=f(f(m)+f(2)). f(f(m + 1) + f(1)) = (m + 1) + 1 = m + 2 = f(f(m) + f(2)).
Using the injectivity, this becomes
f(m+1)+f(1)=f(m)+f(2). f(m + 1) + f(1) = f(m) + f(2).
Let d=f(2)f(1)d = f(2) - f(1). By induction, we can easily prove that
f(m)=f(1)+(m1)d f(m) = f(1) + (m - 1)d
for any mZ+m \in \mathbb{Z}^+. In other words, f(m)=am+bf(m) = am + b for some integers a,ba, b. Now, we have
f(f(m)+f(n))=a(am+b+an+b)+b=a2m+a2n+(2ab+b). f(f(m) + f(n)) = a(am + b + an + b) + b = a^2m + a^2n + (2ab + b).
This is equal to m+nm+n for any m,nZ+m, n \in \mathbb{Z}^+ if and only if a2=1a^2 = 1 and 2ab+b=02ab + b = 0. Clearly, the only solution with a0a \ge 0 is (a,b)=(1,0)(a, b) = (1, 0). This means f(m)=mf(m) = m for any mZ+m \in \mathbb{Z}^+. In particular, we have f(1997)=1997f(1997) = 1997.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty, ordering) added by this project.