Maths Olympiad Prep

Library / /9 of 9

Number theory Difficulty 7.0 National Olympiad Prove it Italy

Problem:

Let ff be a function defined on the set of positive integers with positive integer values.
We say that:
- ff is increasing if n<mn < m implies f(n)<f(m)f(n) < f(m)
- ff is multiplicative if MCD(m,n)=1\operatorname{MCD}(m, n) = 1 implies f(nm)=f(n)f(m)f(n m) = f(n) \cdot f(m)
- ff is completely multiplicative if f(nm)=f(n)f(m)f(n m) = f(n) \cdot f(m) for every n,mn, m.

a. Prove that if ff is increasing then f(n)nf(n) \geq n for every nn.

b. Prove that if ff is increasing, completely multiplicative and f(2)=2f(2) = 2 then f(n)=nf(n) = n for every nn.

c. Does statement (b) remain true if the adverb completely is removed?

Solution

Solution:

a.
If mm is the smallest positive integer such that f(m)<mf(m) < m, the m1m-1 numbers preceding mm must all have image smaller than f(m)f(m) and therefore cannot all be different, since at most m2m-2 values are available, a contradiction.

b.
If mm is the smallest positive integer such that f(m)>mf(m) > m and is even, then f(m)=2f(m2)=2m2=mf(m) = 2 f\left(\frac{m}{2}\right) = 2 \frac{m}{2} = m, a contradiction.
If mm is odd, then f(m+1)=2f(m+12)=m+1f(m+1) = 2 f\left(\frac{m+1}{2}\right) = m+1 since m+12<m\frac{m+1}{2} < m, because m>2m > 2, hence f(m)<m+1f(m) < m+1, a contradiction.

c.
Yes. Indeed, if mm is the smallest positive integer such that f(m)<mf(m) < m and is even, then one proceeds as before if m2\frac{m}{2} is odd, and one passes to f(m+2)=2f(m+22)=m+2f(m+2) = 2 f\left(\frac{m+2}{2}\right) = m+2 if m2\frac{m}{2} is even (note that m+22<m\frac{m+2}{2} < m because m>2m > 2).
If mm is odd, again one proceeds as before if m+12\frac{m+1}{2} is odd, otherwise one passes to f(m+3)=2f(m+32)=m+3f(m+3) = 2 f\left(\frac{m+3}{2}\right) = m+3 because m+32<m\frac{m+3}{2} < m, obviously provided that m>3m > 3. It thus remains to exclude the case m=3m = 3, that is, one must prove that f(3)=3f(3) = 3. To this end let dd be an odd number, not divisible by 33, and such that 3d+12\frac{3d+1}{2} is odd (for example d=7d = 7 works). Then we have:
f(3d+12)<f(2d)=2f(d)f(3d+1)=2f(3d+12)>f(3d)=f(3)f(d) \begin{gathered} f\left(\frac{3d+1}{2}\right) < f(2d) = 2 f(d) \\ f(3d+1) = 2 f\left(\frac{3d+1}{2}\right) > f(3d) = f(3) f(d) \end{gathered}
from which 2>f(3)22 > \frac{f(3)}{2} and hence f(3)<4f(3) < 4.
We observe that in a more direct way one can prove that f(3)=3f(3) = 3 as follows.
Let us set f(3)=xf(3) = x.
By monotonicity we have f(5)x+2f(5) \geq x+2 and, by multiplicativity, f(15)x(x+2)=x2+2xf(15) \geq x(x+2) = x^{2} + 2x. Using alternately multiplicativity and monotonicity we also have:
f(6)=2xf(5)2x1f(10)4x2f(9)4x3f(18)8x6 \begin{aligned} & f(6) = 2x \\ & f(5) \leq 2x-1 \\ & f(10) \leq 4x-2 \\ & f(9) \leq 4x-3 \\ & f(18) \leq 8x-6 \end{aligned}
Again by monotonicity, we have f(15)+3f(18)f(15) + 3 \leq f(18), from which
x2+2x+38x6x26x+9=(x3)20 \begin{gathered} x^{2} + 2x + 3 \leq 8x - 6 \\ x^{2} - 6x + 9 = (x-3)^{2} \leq 0 \end{gathered}
and hence x=3x = 3.

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 translated into English from it; metadata (topic, difficulty) added by this project.