HMMT November

We first answer the following question. Find the minimum number of colors needed to color the divisors of $m$ such that no two distinct divisors $s, t$ of the same color satisfy $s \mid t$. Prime factorize $m=p_{1}^{e_{1}} \ldots p_{k}^{e_{k}}$. Note that the elements $$\begin{aligned} & 1, p_{1}, p_{1}^{2}, \ldots, p_{1}^{e_{1}}, \\ & p_{1}^{e_{1}} p_{2}, \quad p_{1}^{e_{1}} p_{2}^{2}, \quad \ldots, \quad p_{1}^{e_{1}} p_{2}^{e_{2}} \\ & p_{1}^{e_{1}} p_{2}^{e_{2}} p_{3}, \quad p_{1}^{e_{1}} p_{2}^{e_{2}} p_{3}^{2}, \quad \ldots, \quad p_{1}^{e_{1}} p_{2}^{e_{2}} p_{3}^{e_{3}} \\ & \vdots \\ & p_{1}^{e_{1}} \ldots p_{k-1}^{e_{k-1}} p_{k}, \quad p_{1}^{e_{1}} \ldots p_{k-1}^{e_{k-1}} p_{k}^{2}, \quad \ldots, \quad p_{1}^{e_{1}} \ldots p_{k-1}^{e_{k-1}} p_{k}^{e_{k}} \end{aligned}$$ must be pairwise different colors. Hence, we need at least $1+e_{1}+\cdots+e_{k}$ colors. This is also sufficient: number the colors $1,2, \ldots, 1+e_{1}+\cdots+e_{k}$, and color the divisor $s$ with color $1+\sum_{p \text { prime }} \nu_{p}(s)$. Thus, the answer to the above question is $c(m):=1+e_{1}+\cdots+e_{k}$. Now, we return to the original problem. We wish to find the integer $n$ for which $c((n-24)!)=n$, or $c((n-24)!)-(n-24)=24$. Let $f(k)=c(k!)-k$, so that we want to solve $f(n-24)=24$. Note that $f(1)=0$, while for $k>1$ we have $f(k)-f(k-1)=c(k!)-c((k-1)!)-1=\Omega(k)-1$, where $\Omega(k)$ is the number of prime factors of $k$ with multiplicity. $$\begin{array}{c|cccccccccccccccc} k & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 & 16 \\ \hline \Omega(k) & & 1 & 1 & 2 & 1 & 2 & 1 & 3 & 2 & 2 & 1 & 3 & 1 & 2 & 2 & 4 \\ f(k) & 0 & 0 & 0 & 1 & 1 & 2 & 2 & 4 & 5 & 6 & 6 & 8 & 8 & 9 & 10 & 13 \\ & k & 17 & 18 & 19 & 20 & 21 & 22 & 23 & 24 & 25 & 26 & 27 & \\ & \Omega(k) & 1 & 3 & 1 & 3 & 2 & 2 & 1 & 4 & 2 & 2 & 3 & \\ & & \Omega(k) & 13 & 15 & 15 & 17 & 18 & 19 & 19 & 22 & 23 & 24 & 26 & \end{array}$$ Therefore $n-24=26$ and $n=50$.