We denote the set of all nonzero integers and the set of all nonnegative integers by Z∗ and N0, respectively. Find all functions f:Z∗→N0 for which the following two conditions hold:
(1) for each a,b∈Z∗ such that a+b∈Z∗ it holds that f(a+b)≥min{f(a),f(b)};
(2) for each a,b∈Z∗ it holds that f(ab)=f(a)+f(b).
Solution
One trivial solution is the constant function f≡0. Let f be a nontrivial function for which the conditions (1) and (2) hold. We will show that there exists a natural number c and a prime number p for which it holds that f(a)=cvp(a) for each a∈Z∗, where vp(a):=the exponent of p in the canonical factorization of a:
let us note at first that f(1)=f(−1)=0 (proof: f(1)=f(1⋅1)=f(1)+f(1),f(1)=f((−1)⋅(−1))=f(−1)+f(−1); from this and from (2) it follows that there exists a prime number p for which f(p)=0; for c:=f(p) we will show that f(a)=cvp(a) holds for every a∈Z∗; namely, for each prime q=p there exists nonzero integers a,β for which 1=ap+βq, so that the inequality 0=f(ap+βq)≥min{f(ap),f(βq)} holds; from f(ap)=f(a)+f(p)≥f(p)=c=0 it follows that f(βq)=0 and f(q)=0; let a=±pkqβrγ... be the canonical factorization of a; then f(a)=f(±pk)+f(qβ)+f(rγ)+⋯=f(±1)+f(pk)=kf(p)=cvp(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.