Maths Olympiad Prep

Library / /2 of 5

Algebra Difficulty 4.8 AIME Prove it Brazil

Let N={0,1,2,3,}N = \{0, 1, 2, 3, \dots\}. Find all functions f:NNf: N \to N which satisfy f(2f(n))=n+1998f(2f(n)) = n + 1998 for all nn.

Solution

First of all, ff is injective: indeed, f(x)=f(y)    f(2f(x))=f(2f(y))    x+1998=y+1998    x=yf(x) = f(y) \implies f(2f(x)) = f(2f(y)) \iff x + 1998 = y + 1998 \iff x = y.

Moreover, ff takes all integer values bigger than 19971997: if m1998m \ge 1998 then m=1998+km = 1998 + k for some k0k \ge 0 and f(2f(k))=k+1998=mf(2f(k)) = k+1998 = m.

Notice that the values of mm such that f(m)1998f(m) \ge 1998 are all even; since ff is injective, f(x)f(x) can't be bigger than 19971997 for every xx odd. This means that all odd numbers are taken by ff to numbers not exceeding 19981998. By the pigeon hole principle, there are two different odd numbers xx and yy such that f(x)=f(y)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,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.