Maths Olympiad Prep

Library / /7 of 11

Algebra Difficulty 5.9 AIME, harder Prove it Spain

The function f:NNf : \mathbb{N}^* \rightarrow \mathbb{N} satisfies that f(2)=0f(2) = 0, f(3)>0f(3) > 0, f(6042)=2014f(6042) = 2014 and if (m,n)N×N(m, n) \in \mathbb{N}^* \times \mathbb{N}^* then f(m+n)f(n)f(m){0,1}f(m+n) - f(n) - f(m) \in \{0, 1\}. Find the value of f(2014)f(2014). Here, N={1,2,3,}\mathbb{N}^* = \{1, 2, 3, \dots\}.

Solution

Since f(2)f(1)+f(1)=2f(1)f(2) \ge f(1) + f(1) = 2 \cdot f(1) and f(2)=0f(2) = 0 then f(1)0f(1) \le 0. Therefore, f(1)=0f(1) = 0. On the other hand, from f(3)>0f(3) > 0 and f(3)f(2)f(1){0,1}f(3) - f(2) - f(1) \in \{0, 1\} we have f(3)=1f(3) = 1. Putting m=1m = 1 in the condition f(m+n)f(n)f(m){0,1}f(m+n) - f(n) - f(m) \in \{0, 1\}, we obtain f(n+1)f(1)f(n)=f(n+1)f(n){0,1}f(n+1) - f(1) - f(n) = f(n+1) - f(n) \in \{0, 1\} from which follows that f(n+1)f(n)f(n+1) \ge f(n) for all positive integer nn. That is, ff is increasing.

Now we will prove by induction that f(3n)nf(3n) \ge n. The case n=1n = 1 trivially holds. Assume that f(3n)nf(3n) \ge n and we have to see that f(3n+3)n+1f(3n + 3) \ge n + 1. Indeed, f(3n+3)f(3n)f(3)0f(3n + 3) - f(3n) - f(3) \ge 0. So, f(3n+3)f(3n)+f(3)n+1f(3n + 3) \ge f(3n) + f(3) \ge n + 1. On account that f(6042)=2014f(6042) = 2014 then f(3n)=nf(3n) = n for 1n20141 \le n \le 2014. Otherwise, if for some n{1,2,3,,2014}n \in \{1, 2, 3, \dots, 2014\} we have a strict inequality, then it is not possible to obtain f(6042)=2014f(6042) = 2014.

Since f(2014)=f(3671+1)f(2014) = f(3 \cdot 671 + 1) if we see that f(3n+1)=nf(3n + 1) = n for all n{1,2,3,,2014}n \in \{1, 2, 3, \dots, 2014\}, then f(2014)=671f(2014) = 671. Finally, we will prove that f(3n+1)=nf(3n+1) = n. Indeed, f(3n+1)f(3n)+f(1)=f(3n)=nf(3n + 1) \ge f(3n) + f(1) = f(3n) = n. On the other hand, we have 3n+1=f(9n+3)f(6n+2)+f(3n+1)3f(3n+1)3n + 1 = f(9n + 3) \ge f(6n + 2) + f(3n + 1) \ge 3 \cdot f(3n + 1) from which follows f(3n+1)n+13<n+1f(3n + 1) \le n + \frac{1}{3} < n + 1. Hence, f(3n+1)=nf(3n + 1) = n.

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 reproduced verbatim; metadata (topic, difficulty) added by this project.