Let N={0,1,2,3,…}. Find all functions f:N→N which satisfy f(2f(n))=n+1998 for all n.
Solution
First of all, f is injective: indeed, f(x)=f(y)⟹f(2f(x))=f(2f(y))⟺x+1998=y+1998⟺x=y.
Moreover, f takes all integer values bigger than 1997: if m≥1998 then m=1998+k for some k≥0 and f(2f(k))=k+1998=m.
Notice that the values of m such that f(m)≥1998 are all even; since f is injective, f(x) can't be bigger than 1997 for every x odd. This means that all odd numbers are taken by f to numbers not exceeding 1998. By the pigeon hole principle, there are two different odd numbers x and y such that f(x)=f(y), contradiction. So there is no such function.
Want a route through all this instead of an archive? The track
puts 2,604 problems in a working order, from Junior Challenge level to the IMO shortlist.
Source: MathNet,
licensed CC-BY-4.0.
Statement reproduced verbatim; metadata (topic, difficulty) added by this project.