Problem 2327

a) Clearly, $f(1) = 1$. Notice that
$$M(n, k + 1) = \operatorname{lcm}(M(n, k), n - k), \quad 1 \le k < n. \quad (*)$$
Thus, $M(n, k) \le M(n, k+1)$, and equality holds if and only if $n-k$ divides $M(n, k)$. If $m > 1$, then $M(m^2, 2) = m^2(m^2 - 1) = (m^2 - m)(m^2 + m)$, so $M(m^2, 2)$ is divisible by $m^2 - m$, and hence so is $M(m^2, m)$. By $(*)$, $M(m^2, m) = M(m^2, m+1)$, so $f(m^2) \le m$ for all positive integers $m$. With reference again to $(*)$, if $M(n, k) = M(n, k+1)$, then $M(n + \ell, k + \ell) = M(n + \ell, k + \ell + 1)$, so $f(n + \ell) \le f(n) + \ell$ for all positive integers $\ell$ and $n$. Finally, if $m^2 \le n < (m+1)^2$, then $n = m^2 + \ell$ for some non-negative integer $\ell \le 2m$, so $f(n) = f(m^2 + \ell) \le f(m^2) + \ell \le m + \ell \le 3m \le 3\sqrt{n}$, where one of the last two inequalities must in fact be a strict inequality.

b) We show that $f(n) > N$ for all integers $n > N! + N$. Refer again to $(*)$ to write
$$\begin{aligned} M(n, N + 1) &= \operatorname{lcm}(M(n, N), n - N) = \frac{M(n, N) \cdot (n - N)}{\operatorname{gcd}(M(n, N), n - N)} \\ &\ge \frac{M(n, N) \cdot (n - N)}{\prod_{k=1}^{N} \operatorname{gcd}(n - k + 1, n - N)} \ge \frac{M(n, N) \cdot (n - N)}{\prod_{k=1}^{N} (N - k + 1)} \\ &= \frac{M(n, N) \cdot (n - N)}{N!}. \end{aligned}$$
Consequently, if $n > N! + N$, then $M(n, 1) < \dots < M(n, N) < M(n, N + 1)$, so $f(n) > N$.