Maths Olympiad Prep

Library / Brazilian Mathematical Olympiad /39 of 120

Brazilian Mathematical Olympiad

Algebra Difficulty 4.8 AIME Prove it Brazil

Let N={0,1,2,3,… }N = \{0, 1, 2, 3, \dots\}. Find all functions f:N→Nf: 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 m≥1998m \ge 1998 then m=1998+km = 1998 + k for some k≥0k \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,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.