Maths Olympiad Prep

Library / /16 of 35

Algebra Difficulty 5.4 AIME, harder Prove it 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.

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.

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 and solution reproduced as published; topic and difficulty added by this site.