Maths Olympiad Prep

Library / /225 of 520

Algebra Difficulty 5.5 AIME, harder Find the answer

Example 3 Find all functions f:ZZf: \mathbf{Z} \rightarrow \mathbf{Z} such that for all nZn \in \mathbf{Z}, f[f(n)]+f(n)=2n+3f[f(n)]+f(n)=2 n+3, and f(0)=1f(0)=1.

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

Solution

Solve for n=0n=0, f[f(0)]+f(0)=f(1)+f(0)=f(1)+1=20+3f[f(0)]+f(0)=f(1)+f(0)=f(1)+1=2 \cdot 0+3, so f(1)=2f(1)=2.
Let n=1n=1, then f[f(1)]+f(1)=21+3=5f[f(1)]+f(1)=2 \cdot 1+3=5, which means f(2)+2=5f(2)+2=5, so f(2)=3f(2)=3.
From this, we conjecture that f(n)=n+1f(n)=n+1.
We need to prove this by induction for all nn in the set of integers Z\mathbf{Z}.
For n0n \geqslant 0, if nkn \leqslant k, then f(n)=n+1f(n)=n+1, so
f[f(k)]+f(k)=2k+3,f(k+1)+k+1=2k+3, f[f(k)]+f(k)=2 k+3, f(k+1)+k+1=2 k+3,

which means f(k+1)=2k+3f(k+1)=2 k+3. Therefore, for n0n \geqslant 0 and nZn \in \mathbf{Z}, f(n)=n+1f(n)=n+1.
Assume for some k0k \leqslant 0, when nkn \geqslant k, f(n)=n+1f(n)=n+1.
We need to prove that when n=k1n=k-1, f(k1)=kf(k-1)=k.
Let f(k1)=aZf(k-1)=a \in \mathbf{Z}, then
f(a)=f[f(k1)]=2(k1)+3f(k1)=2k+1a, thus f(2k+1a)=f[f(a)]=2a+3(2k+1a)=3a2k+2,f(3a2k+2)=f[f(2k+1)a]=2(2k+1a)+3f(2k+1a)=6k+5a+3. \begin{array}{l} f(a)=f[f(k-1)]=2(k-1)+3-f(k-1)=2 k+1-a, \\ \text { thus } f(2 k+1-a)=f[f(a)]=2 a+3-(2 k+1-a)=3 a-2 k+2, \\ \begin{aligned} f(3 a-2 k+2) & =f[f(2 k+1)-a]=2(2 k+1-a)+3-f(2 k+1-a) \\ & =6 k+5 a+3 . \end{aligned} \end{array}

If 2k+1ak2 k+1-a \geqslant k, by the induction hypothesis,
f(2k+1a)=2k+2af(2 k+1-a)=2 k+2-a, which means 3a2k+2=2k+2a3 a-2 k+2=2 k+2-a, so a=ka=k.
If 3a+22kk3 a+2-2 k \geqslant k, by the induction hypothesis,
f(3a+22k)=3a+32k=6k5a+3f(3 a+2-2 k)=3 a+3-2 k=6 k-5 a+3, so a=ka=k.
If {2k+1ak+1,a<k23,\left\{\begin{array}{l}2 k+1-ak+1, \\ a<k-\frac{2}{3},\end{array}\right., a contradiction arises.
Thus, f(k1)=kf(k-1)=k.
In conclusion, for all nZn \in \mathbf{Z}, f(n)=n+1f(n)=n+1.

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.