In how many ways can the numbers from $2$ to $2022$ be arranged so that the first number is a multiple of $1$, the second number is a multiple of $2$, the third number is a multiple of $3$, and so on untile the last number is a multiple of $2021$?
Problem
Source:
Tags: number theory
11.12.2022 21:05
Denote $A=\{1,2,\dots,2020,2021\};\;B=\{2,3,\dots,2021,2022\}$. The problem is equivalent to: determine how many functions $f:A\to B$ exist, satisfying the properties: a) $\forall y\in B,\;\exists x\in A$ such that $f(x)=y$; b) $k|f(k),\;\forall k\in A$. A function $f$ with the property $a)$ is bijective: $f$ is surjective with card($A$)=card($B$)=2021. Hence exists and denote $f^{-1}$ the inverse function of $f$. A function with the properties $a)$ and $b)$ has supplementary the properties: 1) $\forall k\in A:\;k|f(k)\Longrightarrow f(k)\ge k$. 2) $\exists a_0\in A$ such that $f(a_0)>a_0$. Proof: $A\ne B\Longrightarrow \exists a_0\in A$ such that $f(a_0)\ne a_0$; using the property $1)$ results $f(a_0)>a_0$. A particular situation: always $f(1)>1$. 3) Let be $a_0\in A$ such that $f(a_0)=a_1>a_0$ and define the sequence $(a_j)$ with the recurrence $a_j=f(a_{j-1}),\;j\in \mathbb{N}$, for the values of $j$ such that $a_{j-1}\in A$. Then exists $m\in\mathbb{N}$ such that $a_0,a_1,\dots,a_{m-1}\in A$ and $a_m=2022$. Proof: $f(a_0)=a_1\ne a_0$ and $f$ is injective $\Longrightarrow f(a_1)\ne a_1\Longrightarrow f(a_1)=a_2>a_1$. We repeat the process and we obtain a strictly increasing sequence. After a finite number of steps $a_{m-1}\in A;\;a_{m-1}|f(a_{m-1})=a_m>2021$. Results: $a_m\notin{A};a_m\in B$. But $B\setminus A=\{2022\}\Longrightarrow a_m=2022$. 4) Let be $b_0\in B$ such that $f^{-1}(b_0)=b_1<b_0$ and define the sequence $(b_i)$ with the recurrence $b_i=f^{-1}(b_{i-1}),\;i\in \mathbb{N}$, for the values of $i$ such that $a_{i-1}\in B$. Then exists $t\in\mathbb{N}$ such that $b_0,b_1,\dots,b_{t-1}\in B$ and $b_t=1$. Proof: in a similar way as above, the sequence $(b_i)$ is strictly decreasing and after a finite number of steps we obtain $b_{t-1}\in B;\;b_t\notin B;\;b_t\in A\Longrightarrow b_t\in A\setminus B\Longrightarrow b_t=1$. 5) $f(1)>1$ and using the properties $1),3)$ results: exists a sequence $a_0=1,f(a_0)=a_1,\dots,f(a_{m-1})=a_m=2022$. 6) Let be $a_0=1,a_1,\dots,a_m=2022$ a sequence defined as above. Then $f(x)=x,\;\forall x\in A\setminus\{1,a_1,\dots,a_{m-1}\}$. Proof: assume by contrary $f(x)\ne x$ for some $x\in A\setminus\{1,a_1,\dots,a_{m-1}\}$. Using the properties $3),4),5)$ results: exists a strictly increasing sequence $c_0=1;c_1=f(c_0);\dots;f(c_{s-1})=c_s=2022;\;s\in\mathbb{N}$ such that $x\in\{c_1,c_2,\dots,c_{s-1}\}$. But $c_0=a_0=1\Longrightarrow f(c_0)=f(a_0)\Longrightarrow c_1=a_1$ and repeating the process results $c_j=a_j,\;\forall j\in\{0,1,\dots,m-1,m\}$, hence doesn't exist $x\in A\setminus\{1,a_1,\dots,a_{m-1}\}$ such that $f(x)\ne x$. From the previous properties results: the number of functions $f:A\to B$, satisfying the properties $a),b)$ is equal to the number of sequences $a_0=1,f(a_0)=a_1,\dots,f(a_{m-1})=a_m=2022$. All terms of the sequence are divisors of $2022$. The decomposition of $a_m$ in prime factors is $2022=2\cdot3\cdot337\Longrightarrow m\le3$. The set of the positive divisors of $2022$ is $D=\{1,2,3,6,337,674,1011,2022\}$. Result the possible cases to construct the sequence $a_0=1,f(a_0)=a_1,\dots,f(a_{m-1})=a_m=2022$: $\textbf{Case 1: }m=1$. $a_0=1;\;a_1=2022;\;n_1=1$ possible sequence. $\textbf{Case 2: }m=2$. Let be $(p_1,p_2,p_3)=(2,3,337)$. The possible sequences are: $a_0=1;\;a_1\in\left\{p_i,\dfrac{2022}{p_i}\right\},\;i\in\{1,2,3\};\;a_2=2022\Longrightarrow n_2=6$ possible sequences. $\textbf{Case 3: }m=3$. The possible sequences are: $a_0=1;\;a_1=p_i,\;i\in\{1,2,3\};\;a_2=p_i\cdot p_j,\;j\in\{1,2,3\},\;j\ne i;\;a_3=2022\Longrightarrow n_3=6$ possible sequences. Results the number of possible arrangements of $B$ with the given conditions: $n=n_1+n_2+n_3=13$.