, 2011

Let us examine the first few natural numbers: $1, 2, 3, 4, 5, 6, 7, 8, 9$. Here we see that $a_n = 1, 2, 3, 2, 2, 3, 3, 4, 3$. We observe that $a_n \le a_{n+1}$ for all $n$ except when $n+1$ is a square in which case $a_n > a_{n+1}$. We prove that this observation is valid in general. Consider the range

$$m^2,\ m^2+1,\ m^2+2,\ \dots,\ m^2+m,\ m^2+m+1,\ \dots,\ m^2+2m.$$

Let $n$ take values in this range so that $n = m^2 + r$, where $0 \le r \le 2m$. Then we see that $\lfloor \sqrt{n} \rfloor = m$ and hence
$$\lfloor \frac{n}{\sqrt{n}} \rfloor = \lfloor \frac{m^2 + r}{m} \rfloor = m + \lfloor \frac{r}{m} \rfloor.$$

Thus $a_n$ takes the values $\underbrace{m, m, m, \dots, m}_{m \text{ times}}, \underbrace{m+1, m+1, m+1, \dots, m+1}_{m \text{ times}}, m+2$, in this range.

But when $n = (m+1)^2$, we see that $a_n = m+1$. This shows that $a_{n-1} > a_n$ whenever $n = (m+1)^2$. When we take $n$ in the set $\{1, 2, 3, \dots, 2010\}$, we see that the only squares are $1^2, 2^2, \dots, 44^2$ (since $44^2 = 1936$ and $45^2 = 2025$) and $n = (m+1)^2$ is possible for only 43 values of $m$. Thus $a_n > a_{n+1}$ for 43 values of $n$. (These are $2^2-1, 3^2-1, \dots, 44^2-1$.)