Maths Olympiad Prep

Library / /25 of 62

Algebra Difficulty 5.4 AIME, harder Prove it Ukraine

Let f:NZf: N \to Z be the function that for any two positive integers a,ba, b f(ab)=f(a)+f(b)f(ab) = f(a) + f(b). Find all possible values of f(1000)f(1000).

Solution

Let us look on such an equality:
f(1000)=f(103)=3f(10) f(1000) = f(10^3) = 3 \cdot f(10)
Let us show now that for any integer kk f(1000)f(1000) can equal 3k3k. Let ord(a)\operatorname{ord}(a) be a maximum degree of 22, by what aa is divisible. Let
a=2i(2a0+1),b=2m(2b0+1). Thus a = 2^i(2a_0 + 1), \quad b = 2^m(2b_0 + 1). \text{ Thus}
ord(ab)=ord(2i+m(2a0+1)(2b0+1))=i+m=ord(a)+ord(b). Let f(a)=kord(a), then \operatorname{ord}(ab) = \operatorname{ord}(2^{i+m}(2a_0+1)(2b_0+1)) = i+m = \operatorname{ord}(a)+\operatorname{ord}(b). \text{ Let } f(a)=k \cdot \operatorname{ord}(a), \text{ then}
f(ab)=kord(ab)=k(ord(a)+ord(b))=kord(a)+kord(b)=f(a)+f(b) f(ab) = k \cdot \operatorname{ord}(ab) = k \cdot (\operatorname{ord}(a) + \operatorname{ord}(b)) = k \cdot \operatorname{ord}(a) + k \cdot \operatorname{ord}(b) = f(a) + f(b)
f(1000)=kord(23125)=3k, \Rightarrow f(1000) = k \cdot \operatorname{ord}(2^3 \cdot 125) = 3k,
That is what we had to prove.

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.