Problem 1926

Let $S = \{1, 2, \dots, 1000\}$. We want to find the number of bijective functions $f: S \to S$ such that $f(i)$ is a multiple of $i$ for any $1 \le i \le 999$. Denote $f^k(i) = \underbrace{f(f(\dots f(i)\dots))}_{k \text{ times}}$.

Consider the sequence $\{1000, f(1000), f^2(1000), \dots\}$. Since $S$ is finite, there exists a pair of positive integers $(i, j)$ with $i < j$ and $f^i(1000) = f^j(1000)$. Since $f$ is injective we have $f^{j-i}(1000) = 1000$, thus there exists a positive integer $m$ such that $f^m(1000) = 1000$. Let $l$ be the smallest such positive integer.

We will show that $f(1000), f^2(1000), \dots, f^l(1000) = 1000$ are distinct. Assume that there exists a pair of integers $(s, t)$ such that $f^s(1000) = f^t(1000)$ and $1 \le s < t \le l$. Then we have $f^s(1000) = f^t(1000) = f^s(f^{t-s}(1000))$ and the injectivity of $f$ shows $f^{t-s}(1000) = 1000$, which contradicts the minimality of $l$ since $0 < t-s < l$. Therefore $f(1000), f^2(1000), \dots, f^l(1000) = 1000$ are distinct. In particular, $f(1000), f^2(1000), \dots, f^{l-1}(1000)$ is not equal to 1000, thus $f^{i+1}(1000)$ is a multiple of $f^i(1000)$ for any integer $i \le l-1$.

Now let $a_1 < a_2 < \dots < a_k$ be all positive integers less than or equal to 1000 which do not appear in $\{1000, f(1000), \dots, f^{l-1}(1000)\}$. Since $f(1000), f^2(1000), \dots, f^l(1000)$ is a permutation of $\{1000, f(1000), \dots, f^{l-1}(1000)\}$, $f(a_1), f(a_2), \dots, f(a_k)$ is a permutation of $\{a_1, a_2, \dots, a_k\}$ by the bijectivity of $f$. Therefore we have

$$f(a_1) + f(a_2) + \dots + f(a_k) = a_1 + a_2 + \dots + a_k. \quad (*)$$

For any positive integers $i \le k$ we have $a_i \ne 1000$, thus $f(a_i)$ is a multiple of $a_i$. In particular $f(a_i) \ge a_i$ holds. This and (*) show that $f(a_i) = a_i$ for any positive integer $i \le k$. It follows that there exists a sequence of positive integers $d_1 < d_2 < \dots < d_l = 1000$ such that $d_{i+1}$ is a multiple of $d_i$ for any $1 \le i \le l-1$ and
$$f(n) = \begin{cases} d_{i+1} & (n = d_i, 1 \le i \le l-1), \\ d_1 & (n = d_l), \\ n & \text{(otherwise)}. \end{cases}$$

Conversely, if there exists such a sequence $d_1 < d_2 < \dots < d_l$, $f$ satisfies the given condition. Therefore the problem is equivalent to count sequences of integers $d_1 < d_2 < \dots < d_l = 1000$ such that $d_{i+1}$ is a multiple of $d_i$ for any $1 \le i \le l-1$.

For a positive integer $n$, let $c_n$ be the number of sequences of positive integers $d_1 < d_2 < \dots < d_l = n$ such that $d_{i+1}$ is a multiple of $d_i$ for any $1 \le i \le l-1$.
It is clear that $c_1 = 1$. Let $n \ge 2$. If $l=1$, such sequence is unique. If $l \ge 2$, $d_{l-1}$ must be a positive divisor of $n$ less than $n$, and for any positive divisor $m < n$ of $n$ there exists $c_m$ sequences satisfying the condition with $d_{l-1} = m$. Hence it follows that
$$c_n = 1 + \sum_{m < n,\ m \mid n} c_m.$$

$$\begin{align*} c_1 &= 1, & c_2 &= 2, & c_4 &= 4, & c_8 &= 8, \\ c_5 &= 2, & c_{10} &= 6, & c_{20} &= 16, & c_{40} &= 40, \\ c_{25} &= 4, & c_{50} &= 16, & c_{100} &= 52, & c_{200} &= 152, \\ c_{125} &= 8, & c_{250} &= 40, & c_{500} &= 152, & c_{1000} &= 504. \end{align*}$$

Hence the answer is $c_{1000} = 504$.