Maths Olympiad Prep

Library / /231 of 520

Number theory Difficulty 6.4 National olympiad Prove it

N\mathbb{N}^{*} denotes the set of integers greater than or equal to one. Find all functions f:NN\mathrm{f}: \mathbb{N}^{*} \rightarrow \mathbb{N}^{*} satisfying:
i) for any nn in N,f(n+f(n))=f(n)\mathbb{N}^{*}, f(n+f(n))=f(n)
ii) f(2013)=1f(2013)=1.

Solution

Let ff be a potential solution.
Let aNa \in \mathbb{N}^{*} such that f(a)=1f(a)=1.
Then f(a+1)=f(a+f(a))=f(a)=1f(a+1)=f(a+f(a))=f(a)=1.
Since f(2013)=1f(2013)=1, we deduce by induction that f(n)=1f(n)=1 for all integers n2013\mathfrak{n} \geqslant 2013.
On the other hand, suppose that a2a \geqslant 2 is an integer such that f(n)=1f(n)=1 for all nan \geqslant a.
Then, a11a-1 \geqslant 1 and f(a1)1f(a-1) \geqslant 1, so a1+f(a1)aa-1+f(a-1) \geqslant a and thus from the first paragraph f(a1)=f(a1+f(a1))=1f(a-1)=f(a-1+f(a-1))=1.

This ensures that f(n)=1f(n)=1 for all na1n \geqslant a-1.
Since we have seen that f(n)=1f(n)=1 for all n2013n \geqslant 2013, we deduce by downward induction that f(n)=1f(n)=1 for all n1n \geqslant 1.

Conversely, it is clear that the constant function f:n1\mathrm{f}: \mathrm{n} \longmapsto 1 is a solution to the problem.
Finally, the only solution is the constant function f:n1\mathrm{f}: \mathfrak{n} \longmapsto 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.