Maths Olympiad Prep

Library / /41 of 63

Algebra Difficulty 8.4 Shortlist Prove it North Macedonia

We denote the set of all nonzero integers and the set of all nonnegative integers by Z\mathbb{Z}^* and N0\mathbb{N}_0, respectively. Find all functions f:ZN0f:\mathbb{Z}^* \to \mathbb{N}_0 for which the following two conditions hold:

(1) for each a,bZa,b \in \mathbb{Z}^* such that a+bZa+b \in \mathbb{Z}^* it holds that f(a+b)min{f(a),f(b)}f(a+b) \ge \min\{f(a),f(b)\};

(2) for each a,bZa,b \in \mathbb{Z}^* it holds that f(ab)=f(a)+f(b)f(ab)=f(a)+f(b).

Solution

One trivial solution is the constant function f0f \equiv 0. Let ff be a nontrivial function for which the conditions (1) and (2) hold. We will show that there exists a natural number cc and a prime number pp for which it holds that f(a)=cvp(a)f(a)=cv_p(a) for each aZa \in \mathbb{Z}^*, where vp(a):=the exponent of p in the canonical factorization of av_p(a):=\text{the exponent of }p\text{ in the canonical factorization of }a:

let us note at first that f(1)=f(1)=0f(1)=f(-1)=0 (proof:
f(1)=f(11)=f(1)+f(1),f(1)=f((1)(1))=f(1)+f(1); f(1)=f(1 \cdot 1)=f(1)+f(1), \quad f(1)=f((-1) \cdot (-1))=f(-1)+f(-1);
from this and from (2) it follows that there exists a prime number pp for which f(p)0f(p) \ne 0; for c:=f(p)c:=f(p) we will show that f(a)=cvp(a)f(a)=cv_p(a) holds for every aZa \in \mathbb{Z}^*; namely, for each prime qpq \ne p there exists nonzero integers a,βa,\beta for which 1=ap+βq1=ap+\beta q, so that the inequality 0=f(ap+βq)min{f(ap),f(βq)}0=f(ap+\beta q) \ge \min\{f(ap),f(\beta q)\} holds; from
f(ap)=f(a)+f(p)f(p)=c0 f(ap)=f(a)+f(p) \ge f(p)=c \ne 0
it follows that f(βq)=0f(\beta q)=0 and f(q)=0f(q)=0; let a=±pkqβrγ...a=\pm p^kq^\beta r^\gamma... be the canonical factorization of aa; then
f(a)=f(±pk)+f(qβ)+f(rγ)+=f(±1)+f(pk)=kf(p)=cvp(a) f(a)=f(\pm p^k)+f(q^\beta)+f(r^\gamma)+\dots=f(\pm 1)+f(p^k)=kf(p)=cv_p(a)
It remains to note that each such function satisfies the conditions (1) and (2), and therefore it represents a nontrivial solution to the given problem.

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 and solution reproduced as published; topic and difficulty added by this site.