Maths Olympiad Prep

Library / /22 of 92

Number theory Difficulty 6.0 National olympiad Prove it Iran

Does there exist a non-identity function f:NNf: \mathbb{N} \to \mathbb{N} that:
The number of divisors of mm is f(n)f(n), if and only if the number of divisors of f(m)f(m) is nn, for each two natural numbers mm and nn.

Solution

The answer is Yes!
Let d(n)d(n) be the number of divisors of natural number nn. We want to construct ff such that for any positive integer mm, f(d(f(m)))=d(m)f(d(f(m))) = d(m). Let Ak={nNd(n)=k}A_k = \{n \in \mathbb{N} \mid d(n) = k\}. For example, A1={1}A_1 = \{1\} and A2A_2 is the set of prime numbers. Note that AkA_k has an infinite number of elements for every k>1k > 1, because pk1Akp^{k-1} \in A_k for every prime number pp.
To define ff, set f(1)=1f(1) = 1, f(2)=2f(2) = 2, f(3)=5f(3) = 5 and f(5)=3f(5) = 3. For each n4n \ge 4, suppose that f(k)f(k) is defined for 1kn11 \le k \le n - 1. If f(n)f(n) is not defined then let j=f(d(n))j = f(d(n)). jj is well defined because d(n)<nd(n) < n. Let tt be the least element of AjA_j that ff has not been defined on it yet, so we have d(t)=jd(t) = j. Define f(n)=tf(n) = t and f(t)=nf(t) = n.
Therefore, for each natural number nn, these properties are gained inductively:
f(d(n))=j=d(t)=d(f(n)),f(f(n))=n,f(f(t))=t,f(d(t))=f(j)=f(f(d(n)))=d(n)=d(f(t)). \begin{align*} f(d(n)) &= j = d(t) = d(f(n)), \\ f(f(n)) &= n, \quad f(f(t)) = t, \\ f(d(t)) &= f(j) = f(f(d(n))) = d(n) = d(f(t)). \end{align*}
Hence for every mNm \in \mathbb{N}, we have f(d(f(m)))=f(f(d(m)))=d(m)f(d(f(m))) = f(f(d(m))) = d(m).

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.