Let $S=\{1,2,...,100\}$ . Find number of functions $f: S\to S$ satisfying the following conditions a)$f(1)=1$ b)$f$ is bijective c)$f(n)=f(g(n))f(h(n))\forall n\in S$, where $g(n),h(n)$ are positive integer numbers such that $g(n)\leq h(n),n=g(n)h(n)$ that minimize $h(n)-g(n)$.
Problem
Source: 7-th Hong Kong Mathematical Olympiad 2004
Tags: function, number theory, prime numbers, combinatorics unsolved, combinatorics
21.12.2010 02:24
Trivially, one such function is determined from the values it takes on prime numbers. Suppose $f(n)$ is a prime number. Then, either $f(g(n))$ or $f(h(n))$ equals $1$, but from injectivity we get either $g(n)$ or $h(n)$ equals 1 $\Rightarrow$ $n$ is a prime number. Since $f$ is bijective, this implies $f(p)$ is a prime for all primes $p$. Now, for each prime number $p$, let $\alpha(p)$ be the number of primes $q$ such that $pq \leq 100$. For example, $\alpha(2) = 15$, because $2q \leq 100 \Rightarrow q=2,3,5,7,11,13,17,19,23,29,31,37,41,43,47$. If $p,q$ are prime numbers such that $pq \leq 100$, then $f(pq) = f(p)f(q) \leq 100$. Thus, $\alpha(f(p)) \geq \alpha(p)$. Let us compute the values of $\alpha$: $\alpha(2) = 15$ $\alpha(3) = 11$ $\alpha(5) = 8$ $\alpha(7) = 6$ $\alpha(11) = \alpha(13) = 4$ $\alpha(17) = \alpha(19) = 3$ $\alpha(23) = \alpha(29) = \alpha(31) = 2$ $\alpha(37) = \alpha(41) = \alpha(43) = \alpha(47) = 1$ For all the others: $\alpha(p) = 0$. From these we get $f(2) = 2$, $f(3) = 3$, $f(5) = 5$, $f(7) = 7$. Now, $f(11) = 11$ or $f(11) = 13$, but from $f(99) = f(9)f(11) = 9f(11)$ we get $f(11) = 11$, hence also $f(13) = 13$. Going on, $f(17)$ and $f(19)$ are $17$ and $19$ in some order, and the same thing happens with $23, 29$ and $31$. But, from $f(92) = f(4)f(23) = 4f(23)$ we get $f(23) = 23$, so now we know $f(29)$ and $f(31)$ are $29$ and $31$ in some order. Same thing happens with $37,41,43,47$ and with the set of all primes between $50$ and $100$. Until now, we have $2! \cdot 2! \cdot 4! \cdot 10!$ ways to define the function on the prime numbers. It is not hard to see that each of these gives a function that works. So the answer is $\boxed{96 \cdot 10!}$.