Maths Olympiad Prep

Library / /36 of 61

Algebra Difficulty 6.6 National Olympiad Prove it Canada

Problem:

Let ff be a function with the following properties:
1) f(n)f(n) is defined for every positive integer nn;
2) f(n)f(n) is an integer;
3) f(2)=2f(2)=2;
4) f(mn)=f(m)f(n)f(m n)=f(m) f(n) for all mm and nn;
5) f(m)>f(n)f(m)>f(n) whenever m>nm>n.
Prove that f(n)=nf(n)=n.

Solution

Solution:

Let us analyze the properties of ff.

From property 4, f(mn)=f(m)f(n)f(m n) = f(m) f(n) for all positive integers m,nm, n. This means ff is a multiplicative function.

Let us compute f(1)f(1):

Take m=n=1m = n = 1:
f(1)=f(11)=f(1)f(1)    f(1)2=f(1) f(1) = f(1 \cdot 1) = f(1) f(1) \implies f(1)^2 = f(1)
So f(1)=0f(1) = 0 or f(1)=1f(1) = 1.

Suppose f(1)=0f(1) = 0. Then for any nn,
f(n)=f(n1)=f(n)f(1)=f(n)0=0 f(n) = f(n \cdot 1) = f(n) f(1) = f(n) \cdot 0 = 0
So f(n)=0f(n) = 0 for all nn, but this contradicts f(2)=2f(2) = 2. Therefore, f(1)=1f(1) = 1.

Now, f(2)=2f(2) = 2 is given.

Let us try to find f(2k)f(2^k) for k1k \geq 1.

By induction:
- f(21)=f(2)=2f(2^1) = f(2) = 2
- f(22)=f(22)=f(2)f(2)=22=4f(2^2) = f(2 \cdot 2) = f(2) f(2) = 2 \cdot 2 = 4
- f(23)=f(222)=f(2)f(22)=24=8f(2^3) = f(2 \cdot 2^2) = f(2) f(2^2) = 2 \cdot 4 = 8

So f(2k)=2kf(2^k) = 2^k for all k1k \geq 1.

Now, let us consider f(3)f(3).

Since ff is strictly increasing (property 5), f(3)>f(2)=2f(3) > f(2) = 2 and f(3)f(3) is an integer.

Let us compute f(3k)f(3^k):
- f(31)=f(3)f(3^1) = f(3)
- f(32)=f(3)f(3)f(3^2) = f(3) f(3)
- f(33)=f(3)f(3)f(3)=f(3)3f(3^3) = f(3) f(3) f(3) = f(3)^3

Similarly, f(6)=f(23)=f(2)f(3)=2f(3)f(6) = f(2 \cdot 3) = f(2) f(3) = 2 f(3).

But f(6)f(6) must also equal f(6)=f(32)=f(3)f(2)=f(3)2=2f(3)f(6) = f(3 \cdot 2) = f(3) f(2) = f(3) \cdot 2 = 2 f(3), which is consistent.

Now, consider f(4)=4f(4) = 4 and f(3)>2f(3) > 2.

But f(4)=4f(4) = 4 and f(3)f(3) is an integer >2> 2 and ff is strictly increasing, so f(3)=3f(3) = 3 (since f(3)<f(4)=4f(3) < f(4) = 4 and f(3)f(3) is an integer >2> 2).

Now, f(5)f(5) must be an integer >f(4)=4> f(4) = 4, so f(5)5f(5) \geq 5.

Let us check f(10)=f(25)=f(2)f(5)=2f(5)f(10) = f(2 \cdot 5) = f(2) f(5) = 2 f(5).
But f(10)=f(52)=f(5)f(2)=f(5)2=2f(5)f(10) = f(5 \cdot 2) = f(5) f(2) = f(5) \cdot 2 = 2 f(5), which is consistent.

Let us try to prove by induction that f(n)=nf(n) = n for all nn.

Base case: f(1)=1f(1) = 1, f(2)=2f(2) = 2, f(3)=3f(3) = 3.

Suppose f(k)=kf(k) = k for all k<nk < n.

If nn is composite, say n=abn = a b with a,b<na, b < n, then
f(n)=f(ab)=f(a)f(b)=ab=n f(n) = f(a b) = f(a) f(b) = a b = n
If nn is prime, then f(n)f(n) is an integer >f(n1)=n1> f(n-1) = n-1, so f(n)nf(n) \geq n.

But if f(n)>nf(n) > n, then f(n)n+1f(n) \geq n+1.

Consider f(2n)=f(2)f(n)=2f(n)f(2 n) = f(2) f(n) = 2 f(n). But 2n2 n is less than 2f(n)2 f(n) if f(n)>nf(n) > n, which would contradict the strictly increasing property, since f(2n)>f(2n1)f(2 n) > f(2 n - 1), but f(2n)=2f(n)2(n+1)=2n+2f(2 n) = 2 f(n) \geq 2(n+1) = 2 n + 2, while f(2n1)=2n1f(2 n - 1) = 2 n - 1 (by induction), so 2n+2>2n12 n + 2 > 2 n - 1, which is always true, but let's check for nn large.

But more precisely, suppose f(n)n+1f(n) \geq n+1, then f(2n)=2f(n)2(n+1)=2n+2f(2 n) = 2 f(n) \geq 2(n+1) = 2 n + 2, but 2n2 n is the argument, so f(2n)2n+2f(2 n) \geq 2 n + 2, but f(2n1)=2n1f(2 n - 1) = 2 n - 1, so the difference is at least 33.

But ff must be strictly increasing by 11 at each step, since f(n)f(n) is an integer and f(n)>f(n1)f(n) > f(n-1), so f(n)f(n1)+1f(n) \geq f(n-1) + 1.

But if f(n)>nf(n) > n, then f(n)n+1f(n) \geq n+1, so f(n)f(n1)2f(n) - f(n-1) \geq 2 for some nn, which is not possible if ff is strictly increasing by 11 at each step.

Therefore, f(n)=nf(n) = n for all nn.

Thus, the only function satisfying all the properties is f(n)=nf(n) = 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.