Estonia — Open Contests

As $a_n = n \cdot a_{\lfloor \frac{n}{2} \rfloor}$, it suffices to show that for each $n \ge 12$ we have $a_{\lfloor \frac{n}{2} \rfloor} \ge n$. By the inequalities $n \le 2\lfloor \frac{n}{2} \rfloor + 1 < 3\lfloor \frac{n}{2} \rfloor$ this reduces to proving that $a_m \ge 3m$ for each $m \ge 6$. By $a_m = m \cdot a_{\lfloor \frac{m}{2} \rfloor}$ the latter reduces to proving $a_l \ge 3$ for $l \ge 3$. This is true, since $a_l = l \cdot a_{\lfloor \frac{l}{2} \rfloor} \ge l$.

<table>
<thead>
<tr><th>n</th><th>1</th><th>2</th><th>3</th><th>4</th><th>5</th><th>6</th><th>7</th><th>8</th><th>9</th><th>10</th><th>11</th><th>12</th><th>13</th><th>14</th><th>15</th></tr>
</thead>
<tbody>
<tr><th>a_n</th><td>1</td><td>2</td><td>3</td><td>8</td><td>10</td><td>18</td><td>21</td><td>64</td><td>72</td><td>100</td><td>110</td><td>216</td><td>234</td><td>294</td><td>315</td></tr>
<tr><th>n^2</th><td>1</td><td>4</td><td>9</td><td>16</td><td>25</td><td>36</td><td>49</td><td>64</td><td>81</td><td>100</td><td>121</td><td>144</td><td>169</td><td>196</td><td>225</td></tr>
</tbody>
</table>
Hence for $12 \le n < 16$ the claim is true.
For bigger numbers note that for each $k \ge 4$ we have
$$a_{2k} = 2^k \cdot 2^{k-1} \cdots 2 \cdot 1 = 2^{k+(k-1)+\cdots+1} = 2^{\frac{k(k+1)}{2}} \ge 2^{2(k+1)}.$$
By simple induction we conclude that $a_n$ increases as $n$ increases. For arbitrary $n \ge 16$ pick $k \ge 4$ such that $2^k \le n < 2^{k+1}$, giving
$$a_n \ge a_{2k} \ge 2^{2(k+1)} = (2^{k+1})^2 > n^2.$$