Fifteenth IMAR Mathematical Competition

Let $m = \lfloor \log_2 n \rfloor$, and split the set of integers $1$ through $n$ into $m + 1$ pairwise disjoint subsets $J_0, J_1, \dots, J_m$, where $J_k$ consists of all numbers of the form $2^k(2\ell + 1)$, $\ell = 0, \dots, \lfloor n/2^{k+1} - 1/2 \rfloor$.
If $j$ is a member of $J_k$, then $r_j \ge 2^k$, unless $j = 2^k$ in which case $r_j = 0$.
If $k > \lfloor \log_2 \frac{n}{3} \rfloor = m'$, then $J_k$ consists of $2^k$ alone, so it contributes nothing to the sum in question.

Consequently,
$$\begin{align*} \sum_{k=1}^{n} r_k &= \sum_{k=0}^{m'} \sum_{j \in J_k} r_j \ge \sum_{k=0}^{m'} 2^k (|J_k| - 1) = \sum_{k=0}^{m'} 2^k \left\lfloor \frac{n}{2^{k+1}} - \frac{1}{2} \right\rfloor > \sum_{k=0}^{m'} 2^k \left( \frac{n}{2^{k+1}} - \frac{3}{2} \right) \\ &= \frac{n}{2}(m' + 1) - \frac{3}{2}(2^{m'+1} - 1) > \frac{n}{2} \log_2 \frac{n}{3} - n + \frac{3}{2} > \frac{n}{2} \left( \log_2 \frac{n}{3} - 2 \right). \end{align*}$$