Maths Olympiad Prep

Library / Iranian Mathematical Olympiad /64 of 270

Iranian Mathematical Olympiad

Number theory Difficulty 6.0 National Olympiad Prove it Iran

Does there exist a non-identity function f:N→Nf: \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={n∈N∣d(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 pk−1∈Akp^{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 n≥4n \ge 4, suppose that f(k)f(k) is defined for 1≤k≤n−11 \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 m∈Nm \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,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.