Maths Olympiad Prep

Library / /419 of 520

Algebra Difficulty 6.7 National olympiad Find the answer

Example 10 ([37.3]) Let SS be the set of all non-negative integers. Find all functions f(m)f(m) defined on SS that take values in SS and satisfy the condition f(m+f(n))=f(f(m))+f(n)f(m+f(n))=f(f(m))+f(n) for all m,nSm, n \in S.

A number or a short expression. Spacing and $ signs are ignored.

Solution

(i)
f(f(0))=f(0+f(0))=f(f(0))+f(0)f(0)=0f(f(m))=f(m)f(m+f(n))=f(m)+f(n),f(m+f(n))=f(f(m))+f(n)f(m+f(n))=f(m)+f(n),f(0)=0.\begin{array}{l} f(f(0))=f(0+f(0))=f(f(0))+f(0) \Rightarrow f(0)=0 \\ \Rightarrow f(f(m))=f(m) \Rightarrow f(m+f(n))=f(m)+f(n), \\ f(m+f(n))=f(f(m))+f(n) \\ \Leftrightarrow f(m+f(n))=f(m)+f(n), f(0)=0 . \end{array}
(ii) f(2f(n))=2f(n)f(2 f(n))=2 f(n). By induction, we get f(kf(n))=kf(n)f(k f(n))=k f(n).
(iii) From f(f(m))=f(m)f(f(m))=f(m), we know that the function ff has fixed points, and all the fixed points are the values that f(m)f(m) can take.
(iv) If f(n)0f(n) \equiv 0, it clearly satisfies the requirement. Otherwise, let a1a \geqslant 1 be the smallest fixed point of f(m)f(m) (i.e., the smallest positive integer value that f(m)f(m) can take), i.e., f(a)=a,f(r)r,1r1f(a)=a, f(r) \neq r, 1 \leqslant r1, let n=ka+r,0r<an=k a+r, 0 \leqslant r<a, then (here we use the division with remainder from Chapter 1, §3)
f(n)=f(r+ka)=f(r+kf(a))=f(r+f(kf(a)))=f(r)+f(kf(a))=f(r)+ka\begin{aligned} f(n) & =f(r+k a)=f(r+k f(a))=f(r+f(k f(a))) \\ & =f(r)+f(k f(a))=f(r)+k a \end{aligned}
nn is a fixed point of ff r=f(r),0r<ar=0\Longleftrightarrow r=f(r), 0 \leqslant r<a \Longleftrightarrow r=0, i.e., n=kan=k a. Since f(n)f(n) is a fixed point of ff, we have f(n)=g(n)af(n)=g(n) a, where g(ka)=kg(k a)=k. Therefore,
f(n)=ka+f(r)=ka+g(r)a=([n/a]+g(r))a,f(n)=k a+f(r)=k a+g(r) a=([n / a]+g(r)) a,

where g(0)=0,g(r)(1r<a)g(0)=0, g(r)(1 \leqslant r<a) can be chosen arbitrarily.

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: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.