Maths Olympiad Prep

Track / Stage 5 / 213 of 400 #1293 of 2444

Problem 1293

AIME late
Algebra Difficulty 5.4 Prove it Belarus — Selection and Training Session · Belarus

Determine all functions f:ZZf: \mathbb{Z} \to \mathbb{Z} satisfying
f(f(m)+n)+f(m)=f(n)+f(3m)+2014 f(f(m) + n) + f(m) = f(n) + f(3m) + 2014
for all integers mm and nn.

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

(Solution by I. Voronovich.) Rewrite the given equation as
f(f(m)+n)=f(n)f(m)+f(3m)+c,(1) f(f(m) + n) = f(n) - f(m) + f(3m) + c, \quad (1)
where c=2014c = 2014; all we need in this solution is that cc is even and coprime with 3. Let f(0)=af(0) = a.

1) Setting m=0m = 0 we get f(n+a)=f(n)+cf(n+a) = f(n)+c, then by standard induction to both sides f(n+ka)=f(n)+kcf(n+ka) = f(n) + kc, kZk \in \mathbb{Z}; in particular, f(ka)=a+kcf(ka) = a + kc and f(a)=a+cf(a) = a + c.

2) Set m=nm = n in (1), then
f(n)+n=f(3n)+c=[in view of 1]=f(3n+a). f(n) + n = f(3n) + c = [\text{in view of 1}] = f(3n + a).

3) Setting m=am = a in (1) we get
f(n+f(a))=f(n)f(a)+f(3a)+c, f(n + f(a)) = f(n) - f(a) + f(3a) + c,
or, in view of 1) f(n+c)+c=f(n+c+a)=f(n)ca+a+3c+cf(n+c) + c = f(n+c+a) = f(n) - c - a + a + 3c + c, or f(n+c)=f(n)+2cf(n+c) = f(n) + 2c. Again, by easy induction f(n+kc)=f(n)+2kcf(n+kc) = f(n) + 2kc.

4) Searching on injectivity: suppose that f(s)=f(t)f(s) = f(t). Then setting m=sm = s and m=tm = t in (1) we obtain f(3s)=f(3t)f(3s) = f(3t), and thus f(3ls)=f(3lt)f(3^l s) = f(3^l t) for all lNl \in \mathbb{N}. Since (3;c)=1(3;c)=1, there exists an ll such that 3l1=nc3^l - 1 = nc for some nNn \in \mathbb{N}. Then in view of 3) we have
f(3ls)=f(3lt)    f(s+(3l1)s)=f(t+(3l1)t), f(3^l s) = f(3^l t) \iff f(s + (3^l - 1)s) = f(t + (3^l - 1)t),
or f(s+nsc)=f(t+ntc)f(s + nsc) = f(t + ntc), or f(s)+2nsc=f(t)+2ntcf(s) + 2nsc = f(t) + 2ntc, 2nsc=2ntc2nsc = 2ntc, so s=ts = t. Thus ff is injective. Since in view of 2) f(f(n)+n)=f(3n+a)f(f(n) + n) = f(3n + a), we obtain f(n)+n=3n+af(n) + n = 3n + a, f(n)=2n+af(n) = 2n + a. Easy verification shows that the function is a solution of (1) if and only if a=c/2a = c/2.

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