Maths Olympiad Prep

Track / Stage 7 / 247 of 300 #1647 of 1964

Problem 1647

National Olympiad second round; IMO P1/P4
Number theory Difficulty 7.5 Find the answer

A function f:N→Nf:\mathbb{N} \to \mathbb{N} is given. If a,ba,b are coprime, then f(ab)=f(a)f(b)f(ab)=f(a)f(b). Also, if m,km,k are primes (not necessarily different), then f(m+k−3)=f(m)+f(k)−f(3).f(m+k-3)=f(m)+f(k)-f(3). Find all possible values of f(11)f(11).

A number or a short expression. Fractions can be typed as 3/2, and spacing doesn't matter.

Next problem →

Official solution

1. Initial Conditions and Definitions:
- Given f:N→N f: \mathbb{N} \to \mathbb{N} .
- If a a and b b are coprime, then f(ab)=f(a)f(b) f(ab) = f(a)f(b) .
- For primes m m and k k , f(m+k−3)=f(m)+f(k)−f(3) f(m+k-3) = f(m) + f(k) - f(3) .

2. Base Case:
- Assume f(1)=1 f(1) = 1 .

3. **Define f(2) f(2) and f(4) f(4) :**
- Let f(2)=a f(2) = a .
- Let f(4)=b f(4) = b .

4. **Using the given functional equation with m=k=2 m = k = 2 :**
f(3)=f(2+2−3)=f(2)+f(2)−f(3)  ⟹  f(3)=2a−1 f(3) = f(2+2-3) = f(2) + f(2) - f(3) \implies f(3) = 2a - 1

5. **Using the given functional equation with m=5 m = 5 and k=2 k = 2 :**
f(5)=f(5+2−3)=f(5)+f(2)−f(3)  ⟹  f(5)=f(4)+f(3)−f(2)=b+(2a−1)−a=a+b−1 f(5) = f(5+2-3) = f(5) + f(2) - f(3) \implies f(5) = f(4) + f(3) - f(2) = b + (2a - 1) - a = a + b - 1

6. **Using the given functional equation with m=k=5 m = k = 5 :**
f(7)=f(5+5−3)=2f(5)−f(3)  ⟹  f(7)=2(a+b−1)−(2a−1)=2a+2b−2−2a+1=2b−1 f(7) = f(5+5-3) = 2f(5) - f(3) \implies f(7) = 2(a + b - 1) - (2a - 1) = 2a + 2b - 2 - 2a + 1 = 2b - 1

7. **Using the given functional equation with m=k=7 m = k = 7 :**
f(11)=f(7+7−3)=2f(7)−f(3)  ⟹  f(11)=2(2b−1)−(2a−1)=4b−2−2a+1=4b−2a−1 f(11) = f(7+7-3) = 2f(7) - f(3) \implies f(11) = 2(2b - 1) - (2a - 1) = 4b - 2 - 2a + 1 = 4b - 2a - 1

8. **Using the given functional equation with m=11 m = 11 and k=2 k = 2 :**
f(10)=f(11+2−3)=f(11)+f(2)−f(3)  ⟹  f(10)=4b−2a−1+a−(2a−1)=4b−3a f(10) = f(11+2-3) = f(11) + f(2) - f(3) \implies f(10) = 4b - 2a - 1 + a - (2a - 1) = 4b - 3a
- Also, since 10=2×5 10 = 2 \times 5 , we have:
f(10)=f(2)f(5)=a(a+b−1) f(10) = f(2)f(5) = a(a + b - 1)
- Equating the two expressions for f(10) f(10) :
4b−3a=a(a+b−1) 4b - 3a = a(a + b - 1)

9. **Using the given functional equation with m=13 m = 13 and k=2 k = 2 :**
f(12)=f(13+2−3)=f(13)+f(2)−f(3)  ⟹  f(12)=5b−3a−1+a−(2a−1)=5b−4a f(12) = f(13+2-3) = f(13) + f(2) - f(3) \implies f(12) = 5b - 3a - 1 + a - (2a - 1) = 5b - 4a
- Also, since 12=3×4 12 = 3 \times 4 , we have:
f(12)=f(3)f(4)=(2a−1)b f(12) = f(3)f(4) = (2a - 1)b
- Equating the two expressions for f(12) f(12) :
5b−4a=b(2a−1) 5b - 4a = b(2a - 1)

10. Solving the system of equations:
- From 4b−3a=a(a+b−1) 4b - 3a = a(a + b - 1) :
4b−3a=a2+ab−a 4b - 3a = a^2 + ab - a
- From 5b−4a=b(2a−1) 5b - 4a = b(2a - 1) :
5b−4a=2ab−b 5b - 4a = 2ab - b
- Simplifying the second equation:
5b−4a=2ab−b  ⟹  5b−b=2ab−4a  ⟹  4b=2ab−4a  ⟹  4b=2a(b−2)  ⟹  b=2a3−a 5b - 4a = 2ab - b \implies 5b - b = 2ab - 4a \implies 4b = 2ab - 4a \implies 4b = 2a(b - 2) \implies b = \frac{2a}{3 - a}
- Substituting b=2a3−a b = \frac{2a}{3 - a} into the first equation:
4(2a3−a)−3a=a2+a(2a3−a)−a 4\left(\frac{2a}{3 - a}\right) - 3a = a^2 + a\left(\frac{2a}{3 - a}\right) - a
8a3−a−3a=a2+2a23−a−a \frac{8a}{3 - a} - 3a = a^2 + \frac{2a^2}{3 - a} - a
8a−3a(3−a)3−a=a2+2a2−a(3−a)3−a \frac{8a - 3a(3 - a)}{3 - a} = a^2 + \frac{2a^2 - a(3 - a)}{3 - a}
8a−9a+3a23−a=a2+2a2−3a+a23−a \frac{8a - 9a + 3a^2}{3 - a} = a^2 + \frac{2a^2 - 3a + a^2}{3 - a}
−a+3a23−a=a2+3a2−3a3−a \frac{-a + 3a^2}{3 - a} = a^2 + \frac{3a^2 - 3a}{3 - a}
−a+3a2=3a2−3a -a + 3a^2 = 3a^2 - 3a
−a=−3a -a = -3a
2a=0  ⟹  a=1 2a = 0 \implies a = 1
- Substituting a=1 a = 1 into b=2a3−a b = \frac{2a}{3 - a} :
b=2⋅13−1=22=1 b = \frac{2 \cdot 1}{3 - 1} = \frac{2}{2} = 1
- Therefore, (a,b)=(1,1) (a, b) = (1, 1) .

11. Checking the other solution:
- Solving a2−3a+2=0 a^2 - 3a + 2 = 0 :
(a−1)(a−2)=0  ⟹  a=1 or a=2 (a - 1)(a - 2) = 0 \implies a = 1 \text{ or } a = 2
- If a=2 a = 2 :
b=2⋅23−2=41=4 b = \frac{2 \cdot 2}{3 - 2} = \frac{4}{1} = 4
- Therefore, (a,b)=(2,4) (a, b) = (2, 4) .

12. **Finding f(11) f(11) :**
- For (a,b)=(1,1) (a, b) = (1, 1) :
f(11)=4b−2a−1=4⋅1−2⋅1−1=4−2−1=1 f(11) = 4b - 2a - 1 = 4 \cdot 1 - 2 \cdot 1 - 1 = 4 - 2 - 1 = 1
- For (a,b)=(2,4) (a, b) = (2, 4) :
f(11)=4b−2a−1=4⋅4−2⋅2−1=16−4−1=11 f(11) = 4b - 2a - 1 = 4 \cdot 4 - 2 \cdot 2 - 1 = 16 - 4 - 1 = 11

Conclusion:
- Both values are possible for functions f(n)=1 f(n) = 1 or f(n)=n f(n) = n .

The final answer is 1 or 11 \boxed{1 \text{ or } 11}

Source: NuminaMath-1.5, licensed Apache-2.0. Statement reproduced verbatim; metadata (topic, difficulty, ordering) added by this project.