Maths Olympiad Prep

Track / Stage 7 / 229 of 300 #1629 of 1964

Problem 1629

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

A function f:NNf:\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+k3)=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.

Official solution

1. Initial Conditions and Definitions:
- Given f:NN 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+k3)=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+23)=f(2)+f(2)f(3)    f(3)=2a1 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+23)=f(5)+f(2)f(3)    f(5)=f(4)+f(3)f(2)=b+(2a1)a=a+b1 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+53)=2f(5)f(3)    f(7)=2(a+b1)(2a1)=2a+2b22a+1=2b1 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+73)=2f(7)f(3)    f(11)=2(2b1)(2a1)=4b22a+1=4b2a1 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+23)=f(11)+f(2)f(3)    f(10)=4b2a1+a(2a1)=4b3a 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+b1) f(10) = f(2)f(5) = a(a + b - 1)
- Equating the two expressions for f(10) f(10) :
4b3a=a(a+b1) 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+23)=f(13)+f(2)f(3)    f(12)=5b3a1+a(2a1)=5b4a 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)=(2a1)b f(12) = f(3)f(4) = (2a - 1)b
- Equating the two expressions for f(12) f(12) :
5b4a=b(2a1) 5b - 4a = b(2a - 1)

10. Solving the system of equations:
- From 4b3a=a(a+b1) 4b - 3a = a(a + b - 1) :
4b3a=a2+aba 4b - 3a = a^2 + ab - a
- From 5b4a=b(2a1) 5b - 4a = b(2a - 1) :
5b4a=2abb 5b - 4a = 2ab - b
- Simplifying the second equation:
5b4a=2abb    5bb=2ab4a    4b=2ab4a    4b=2a(b2)    b=2a3a 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=2a3a b = \frac{2a}{3 - a} into the first equation:
4(2a3a)3a=a2+a(2a3a)a 4\left(\frac{2a}{3 - a}\right) - 3a = a^2 + a\left(\frac{2a}{3 - a}\right) - a
8a3a3a=a2+2a23aa \frac{8a}{3 - a} - 3a = a^2 + \frac{2a^2}{3 - a} - a
8a3a(3a)3a=a2+2a2a(3a)3a \frac{8a - 3a(3 - a)}{3 - a} = a^2 + \frac{2a^2 - a(3 - a)}{3 - a}
8a9a+3a23a=a2+2a23a+a23a \frac{8a - 9a + 3a^2}{3 - a} = a^2 + \frac{2a^2 - 3a + a^2}{3 - a}
a+3a23a=a2+3a23a3a \frac{-a + 3a^2}{3 - a} = a^2 + \frac{3a^2 - 3a}{3 - a}
a+3a2=3a23a -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=2a3a b = \frac{2a}{3 - a} :
b=2131=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 a23a+2=0 a^2 - 3a + 2 = 0 :
(a1)(a2)=0    a=1 or a=2 (a - 1)(a - 2) = 0 \implies a = 1 \text{ or } a = 2
- If a=2 a = 2 :
b=2232=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)=4b2a1=41211=421=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)=4b2a1=44221=1641=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 and solution reproduced as published; topic, difficulty and ordering added by this site.