Maths Olympiad Prep

Library / /320 of 462

Algebra Difficulty 6.3 National Olympiad Prove it Ireland

Let f:ZZf : \mathbb{Z} \to \mathbb{Z} be such that, for all a,bZa, b \in \mathbb{Z}
f(a+b)=f(f(a))+f(f(b)). f(a + b) = f(f(a)) + f(f(b)).
Find all possible values of f(2020)f(2020).

Solution

Solution 1. We first show that f(f(x))f(f(x)) must be affine. To see this, replace (a,b)(a, b) first by (a1,a+1)(a - 1, a + 1) and then by (a,a)(a, a) to obtain
f(f(a1))+f(f(a+1))=f(2a)=2f(f(a)). f(f(a - 1)) + f(f(a + 1)) = f(2a) = 2f(f(a)).
Therefore,
f(f(a+1))f(f(a))=f(f(a))f(f(a1)). f(f(a + 1)) - f(f(a)) = f(f(a)) - f(f(a - 1)).
This means that there is a constant mm so that for all aZa \in \mathbb{Z}:
f(f(a+1))f(f(a))=m. f(f(a + 1)) - f(f(a)) = m.
Inductively it follows that for all aZa \in \mathbb{Z}
f(f(a))=ma+c. f(f(a)) = ma + c.
Then, taking the original functional equation with b=0b = 0.
f(a+0)=f(f(a))+f(f(0))=ma+2c. f(a + 0) = f(f(a)) + f(f(0)) = ma + 2c.
Taking the full original function equation, then we have:
m(a+b)+2c=f(a+b)=f(f(a))+f(f(b))=f(ma+2c)+f(mb+2c)=m(ma+2c)+2c+m(mb+2c)+2c=m2(a+b)+2c(2m+2). \begin{aligned} m(a + b) + 2c &= f(a + b) \\ &= f(f(a)) + f(f(b)) \\ &= f(ma + 2c) + f(mb + 2c) \\ &= m(ma + 2c) + 2c + m(mb + 2c) + 2c \\ &= m^2(a + b) + 2c(2m + 2). \end{aligned}
As this holds for arbitrary a+ba + b we must have:
m=m20=(2m+1)c. \begin{aligned} m &= m^2 \\ 0 &= (2m + 1)c. \end{aligned}
The first equation implies either m=0m = 0 or m=1m = 1, so 2m+102m + 1 \neq 0 and the second equation then implies c=0c = 0. Putting these together, we see that either f(a)=0f(a) = 0 for all aZa \in \mathbb{Z} or f(a)=af(a) = a for all aZa \in \mathbb{Z} and the possible values of f(2020)f(2020) are 0 or 2020.

Solution 2. Let fnf^n denote the nn-th iterate of ff, i.e. f2(x)=f(f(x))f^2(x) = f(f(x)), f3(x)=f(f(f(x)))f^3(x) = f(f(f(x))) etc. The given equation can then be written as
f(a+b)=f2(a)+f2(b). f(a + b) = f^2(a) + f^2(b).
Using a=f(0)a = f(0) and b=0b = 0, we get f2(0)=f3(0)+f2(0)f^2(0) = f^3(0) + f^2(0), which implies
f3(0)=0. f^3(0) = 0.
Let a=b=0a = b = 0 to get f(0)=2f2(0)f(0) = 2f^2(0). Let now a=b=f2(0)a = b = f^2(0) and use the two previous identities to see that
f2(0)=f(f(0))=f(2f2(0))=2f4(0)=2f(f3(0))=2f(0)=4f2(0). f^2(0) = f(f(0)) = f(2f^2(0)) = 2f^4(0) = 2f(f^3(0)) = 2f(0) = 4f^2(0).
This implies f2(0)=0f^2(0) = 0. Letting b=0b = 0 in the original equation, we now obtain f2(a)=f(a)f^2(a) = f(a) for all aZa \in \mathbb{Z}. This means that the given equation is equivalent to Cauchy's equation
f(a+b)=f(a)+f(b) f(a + b) = f(a) + f(b)
whose solutions over the integers are known to be of the form f(a)=caf(a) = ca for some integer cc. From f2(1)=f(1)f^2(1) = f(1) we obtain c2=cc^2 = c, i.e. c=0c = 0 or c=1c = 1. Therefore, the possible values of f(2020)f(2020) are 0 or 2020.

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 reproduced verbatim; metadata (topic, difficulty) added by this project.