Maths Olympiad Prep

Library / /18 of 63

Algebra Difficulty 6.4 National olympiad Prove it Japan

Let N0N_0 be the set of nonnegative integers and Z\mathbb{Z} be the set of integers. Find the number of possible tuples (f(0),f(1),,f(2024))(f(0), f(1), \dots, f(2024)) for f:N0Zf: N_0 \to \mathbb{Z} satisfying
f(m+n)2=f(mf(n))+f(n2) f(m+n)^2 = f(m|f(n)|) + f(n^2)
for any m,nN0m, n \in N_0.

Solution

Denote the equation f(m+n)2=f(mf(n))+f(n2)f(m + n)^2 = f(m|f(n)|) + f(n^2) by P(m,n)P(m, n). P(0,0)P(0, 0) implies f(0)2=2f(0)f(0)^2 = 2f(0), thus f(0){0,2}f(0) \in \{0, 2\}.

When f(0)=0f(0) = 0, P(m,0)P(m, 0) implies f(m)=0f(m) = 0 for any mN0m \in \mathbb{N}_0. Since this ff satisfies the condition, there is just one possible tuple (f(0),f(1),,f(2024))(f(0), f(1), \dots, f(2024)) in this case.

We consider the case f(0)=2f(0) = 2. P(0,1)P(0, 1) implies f(1)2=f(1)+2f(1)^2 = f(1)+2, thus we have f(1){1,2}f(1) \in \{-1, 2\}. If f(1)=1f(1) = -1, P(1,1)P(1, 1) implies f(2)2=2f(2)^2 = -2 which contradicts f(2)Zf(2) \in \mathbb{Z}. Therefore we have f(1)=2f(1) = 2. Then P(m,1)P(m, 1) and P(m,0)P(m, 0) imply that f(m+1)2=f(2m)+2=f(m)2f(m+1)^2 = f(2m)+2 = f(m)^2. By induction we have f(m)=2|f(m)| = 2 for any mN0m \in \mathbb{N}_0. Moreover, f(2m)=f(m)22=2f(2m) = f(m)^2 - 2 = 2 holds. On the other hand, P(0,n)P(0, n) implies f(n2)=f(n)2f(0)=2f(n^2) = f(n)^2 - f(0) = 2 for any nN0n \in \mathbb{N}_0.

Conversely, if we choose f:N0{2,2}f: \mathbb{N}_0 \to \{-2, 2\} so that f(n)=2f(n) = 2 whenever nn is even or square, ff satisfies the condition because f(m+n)2=4f(m+n)^2 = 4, f(mf(n))=f(2m)=2f(m|f(n)|) = f(2m) = 2 and f(n2)=2f(n^2) = 2 for any m,nN0m, n \in \mathbb{N}_0. Since there exist 990 integers between 0 to 2024 which are neither even nor square, the number of possible tuples (f(0),f(1),,f(2024))(f(0), f(1), \dots, f(2024)) in this case is 29902^{990}.

Therefore the answer is 2990+12^{990} + 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: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.