XXXI 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)+\cdots +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{array}{rlrlr}f(x)& =f\left(\frac{x}{2}\right)+f\left(\frac{x}{3}\right)+f\left(\frac{x}{4}\right)+\cdots +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{array}$$

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{array}{rlr}f(x)& =1+f\left(\frac{x}{2}\right)+f\left(\frac{x}{3}\right)+f\left(\frac{x}{4}\right)+\cdots +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 }+\cdots +{\left(\frac{x}{\lfloor x\rfloor }\right)}^{\alpha }\right)\end{array}$$ So we need $$\begin{array}{rlr}& 1+c(k)x^{\alpha }\left({\left(\frac{1}{2}\right)}^{\alpha }+{\left(\frac{1}{3}\right)}^{\alpha }+{\left(\frac{1}{4}\right)}^{\alpha }+\cdots +{\left(\frac{1}{\lfloor x\rfloor }\right)}^{\alpha }\right)\ge c(k+1)x^{\alpha }⟺& 1+c(k)x^{\alpha }\left(2-1-\sum _{m>x}\frac{1}{m^{\alpha }}\right)\ge c(k+1)x^{\alpha }\end{array}$$ 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 }}+\cdots ={\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 $$\begin{gathered} 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) \\ ⟺\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)}} \end{gathered}$$ We can choose $m_1,m_2$ such that $-m_2+m_2{2}^{\alpha -1}-\beta m_1{2}^{2(\alpha -1)}=0⟺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 }}⟺\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.