Brazilian Math Olympiad

Extend the definition of $f$ to real numbers, that is, $f(x)$ is the number of $k$-uples whose product is at most $x$, $x \in \mathbb{R}$. If the last number in a $k$-uple is $m$, then we obtain a product that doesn't exceed $x/m$. Conversely, given a number $m$ and a product that doesn't exceed $x/m$ we obtain a $k$-uple whose last number is $m$. Adding the empty $0$-uple, we obtain
$$f(x) = 1 + f\left(\frac{x}{2}\right) + f\left(\frac{x}{3}\right) + f\left(\frac{x}{4}\right) + \dots + f\left(\frac{x}{\lfloor x \rfloor}\right)$$

a. Induct on $n$. We don't need to worry about all real numbers because $f(x) = f(\lfloor x \rfloor)$. Suppose $f(x) \le K \cdot x^{\alpha}$, $\alpha$ defined as in the problem statement, $x < n$. One can find a suitable $K$ for $n = 1$ (for instance, $K = 1$). Then
$$\begin{align*} f(x) &= f\left(\frac{x}{2}\right) + f\left(\frac{x}{3}\right) + f\left(\frac{x}{4}\right) + \dots + f\left(\frac{x}{\lfloor x \rfloor}\right) \ &< K \left(\frac{x}{2}\right)^{\alpha} + K \left(\frac{x}{3}\right)^{\alpha} + K \left(\frac{x}{4}\right)^{\alpha} + \dots \ &= K x^{\alpha} \left( \left(\frac{1}{2}\right)^{\alpha} + \left(\frac{1}{3}\right)^{\alpha} + \left(\frac{1}{4}\right)^{\alpha} + \dots \right) \ &= K x^{\alpha} \left( \sum_{m=1}^{\infty} \frac{1}{m^{\alpha}} - 1 \right) = K x^{\alpha} \end{align*}$$

b. Suppose that $f(n) \ge c(k) \cdot n^{\alpha}$ for all $n < 2^k$. We will find a recurrence relation for $c(k)$ and prove that $c(k)$ tends to a positive constant. Let $c(1) = 2$ and, since $x < 2^{k+1} \Rightarrow x/j < 2^k$ for $j \ge 2$,
$$\begin{align*} f(x) &= 1 + f\left(\frac{x}{2}\right) + f\left(\frac{x}{3}\right) + f\left(\frac{x}{4}\right) + \dots + f\left(\frac{x}{\lfloor x \rfloor}\right) \ &\ge 1 + c(k) \left( \left(\frac{x}{2}\right)^{\alpha} + \left(\frac{x}{3}\right)^{\alpha} + \left(\frac{x}{4}\right)^{\alpha} + \dots + \left(\frac{x}{\lfloor x \rfloor}\right)^{\alpha} \right) \end{align*}$$
So we need
$$\begin{align*} & 1 + c(k)x^{\alpha} \left( \left(\frac{1}{2}\right)^{\alpha} + \left(\frac{1}{3}\right)^{\alpha} + \left(\frac{1}{4}\right)^{\alpha} + \dots + \left(\frac{1}{\lfloor x \rfloor}\right)^{\alpha} \right) \ge c(k+1)x^{\alpha} \ \iff & 1 + c(k)x^{\alpha} \left( 2 - 1 - \sum_{m>x} \frac{1}{m^{\alpha}} \right) \ge c(k+1)x^{\alpha} \end{align*}$$
Since $m > x > 2^k$, by substituting every number between $2^t$ and $2^{t+1}$ by $2^t$ we obtain $\sum_{m>x} \frac{1}{m^{\alpha}} < 2^k \cdot \frac{1}{2^{k\alpha}} + 2^{k+1} \cdot \frac{1}{2^{(k+1)\alpha}} + \dots = \sum_{t \ge k} \frac{1}{2^{(\alpha-1)t}} = \frac{1}{2^{(\alpha-1)(k-1)}}$. So it's sufficient to have
$$c(k+1) \le x^{-\alpha} + c(k) \left(1 - \frac{1}{2^{(k-1)(\alpha-1)}(2^{\alpha-1}-1)}\right)$$
Since $x < 2^{k+1}$, we can actually have
$$c(k+1) \le \frac{1}{2^{(k+1)\alpha}} + c(k) \left(1 - \frac{1}{2^{(k-1)(\alpha-1)}(2^{\alpha-1} - 1)}\right)$$
Let $\beta = \frac{1}{2^{\alpha-1}-1}$. Let's try, then, to find constants $m_1, m_2$ such that $c(k) = m_1 + \frac{m_2}{2^{k(\alpha-1)}}$. Substituting, we find
$$m_1 + \frac{m_2}{2^{(k+1)(\alpha-1)}} \le \frac{1}{2^{(k+1)\alpha}} + \left(m_1 + \frac{m_2}{2^{k(\alpha-1)}}\right) \left(1 - \frac{\beta}{2^{(k-1)(\alpha-1)}}\right) \\ \iff \frac{\beta m_2}{2^{(2k-1)(\alpha-1)}} \le \frac{1}{2^{(k+1)\alpha}} + \frac{-m_2 + m_2 2^{\alpha-1} - \beta m_1 2^{2(\alpha-1)}}{2^{(k+1)(\alpha-1)}}$$
We can choose $m_1, m_2$ such that $-m_2 + m_2 2^{\alpha-1} - \beta m_1 2^{2(\alpha-1)} = 0 \iff 2^{2(\alpha-1)}m_1 = (2^{\alpha-1} - 1)^2 m_2$. Then the inequality reduces to
$$\frac{\beta m_2}{2^{(2k-1)(\alpha-1)}} \le \frac{1}{2^{(k+1)\alpha}} \iff \frac{\beta m_2}{2^{(k-1/2)(2\alpha-2)}} \le \frac{1}{2^{(k+1)\alpha}}$$
which holds for many positive constants $\beta, m_2$. So $c(k) = m_1 + \frac{m_2}{2^{k(\alpha-1)}}$ tends to a positive $m_1$ as $k$ goes to infinity, and, since $f(n) \ge c(k) \cdot 2^{\alpha} > m_1 \cdot 2^{\alpha}$ we are done.