Maths Olympiad Prep

Library / /41 of 44

Algebra Difficulty 6.8 National Olympiad Prove it Slovenia

Find all functions f:NNf: \mathbb{N} \to \mathbb{N} such that:
* for any positive integers aa and bb which are not relatively prime we have f(a)f(b)=f(ab)f(a)f(b) = f(ab),
* for any positive integers aa and bb there exists a non-degenerate triangle with the sides of lengths f(a)f(a), f(b)f(b) and f(a+b1)f(a + b - 1).
(Note: A triangle is non-degenerate if its three vertices do not lie on a common line.)

Solution

The second condition implies that for all a,bNa, b \in \mathbb{N} the triangle inequalities hold:
f(a)+f(b)>f(a+b1),f(a)+f(a+b1)>f(b),f(b)+f(a+b1)>f(a). \begin{aligned} f(a) + f(b) &> f(a+b-1), \\ f(a) + f(a+b-1) &> f(b), \\ f(b) + f(a+b-1) &> f(a). \end{aligned}
First, consider a=b=2a = b = 2. It then follows from the first condition that f(4)=f(2)2f(4) = f(2)^2, and the second condition implies that 2f(2)>f(3)2f(2) > f(3).

Now, let a=3a = 3, b=2b = 2. The second condition then implies that f(2)+f(3)>f(4)f(2) + f(3) > f(4). So,
f(2)2=f(4)<f(2)+f(3)<f(2)+2f(2)=3f(2)    f(2)(3f(2))>0. \begin{aligned} f(2)^2 &= f(4) < f(2) + f(3) < f(2) + 2f(2) = 3f(2) \\ &\implies f(2)(3 - f(2)) > 0. \end{aligned}
Since f(2)f(2) is a positive integer there are only two possibilities: f(2)=1f(2) = 1 and f(2)=2f(2) = 2. We consider the two cases separately:

* If f(2)=1f(2) = 1, then let a=2a = 2, b=1b = 1. The second condition implies that 2f(2)>f(1)2f(2) > f(1), so f(1)=1f(1) = 1. We can now use induction to show that f(n)=1f(n) = 1 for all nn. This is true for the base case. Now, assume that f(n)=1f(n) = 1 for some n2n \ge 2. Using a=na = n, b=2b = 2 in the second condition we get
f(n+1)<f(n)+f(2)=2    f(n+1)=1. f(n+1) < f(n) + f(2) = 2 \implies f(n+1) = 1.
This gives us the solution f(n)=1f(n) = 1 for all nNn \in \mathbb{N}.

* If f(2)=2f(2) = 2, then f(4)=f(2)2=4f(4) = f(2)^2 = 4. What is more, for all kNk \in \mathbb{N} the induction on the first condition implies that
f(2k)=f(2)f(2k1)==f(2)k=2k. f(2^k) = f(2)f(2^{k-1}) = \dots = f(2)^k = 2^k.
We know from before that f(4)f(2)<f(3)<2f(2)f(4) - f(2) < f(3) < 2f(2), which implies that f(3)=3f(3) = 3.

We now use induction to show that f(n)=nf(n) = n for all n2n \ge 2. The base case is obvious. Now, assume that the induction hypothesis holds for 2,3,,n12, 3, \dots, n-1. Using a=n1a = n-1, b=2b = 2 we get
f(n)<f(n1)+f(2)=n+1    f(n)n. f(n) < f(n-1) + f(2) = n+1 \implies f(n) \le n.
Let 2r2^r be the greatest power of 22, such that 2rn2^r \le n. If 2r=n2^r = n, then the induction step is concluded because f(2r)=2rf(2^r) = 2^r. Otherwise let n=2r+sn = 2^r + s, where 1s<2r1 \le s < 2^r.

We will use a=n=2r+sa = n = 2^r + s, b=2rs+1b = 2^r - s + 1 with the second condition. Since 2rs+122^r - s + 1 \ge 2 the induction hypothesis implies that f(2rs+1)=2rs+1f(2^r - s + 1) = 2^r - s + 1. So,
f(n)+f(2rs+1)>f(2r+s+2rs+11)=f(2r+1)    f(n)>f(2r+1)f(2rs+1)=2r+s1=n1    f(n)n. \begin{align*} f(n) + f(2^r - s + 1) &> f(2^r + s + 2^r - s + 1 - 1) = f(2^{r+1}) \\ \implies f(n) &> f(2^{r+1}) - f(2^r - s + 1) = 2^r + s - 1 = n - 1 \\ \implies f(n) &\ge n. \end{align*}
We have shown that f(n)=nf(n) = n which concludes the induction step. All that remains is to determine f(1)f(1). The only condition is that f(1)<2f(2)=4f(1) < 2f(2) = 4. So, f(1)f(1) can be either 11, 22 or 33.

We have obtained the solutions f(n)=1f(n) = 1 for all nn and f(n)=nf(n) = n for n2n \ge 2 with f(1){1,2,3}f(1) \in \{1, 2, 3\}. It is easy to check that all of these satisfy the conditions of the problem.

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.