Maths Olympiad Prep

Library / Team Selection Test for IMO /32 of 55

Team Selection Test for IMO

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:Z∗→N0f:\mathbb{Z}^* \to \mathbb{N}_0 for which the following two conditions hold:

(1) for each a,b∈Z∗a,b \in \mathbb{Z}^* such that a+b∈Z∗a+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,b∈Z∗a,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 f≡0f \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 a∈Z∗a \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(1⋅1)=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 a∈Z∗a \in \mathbb{Z}^*; namely, for each prime q≠pq \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)=c≠0 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,604 problems in a working order, from Junior Challenge level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.