Indija mo 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 $\underset{m\text{ times}}{\underbrace{m,m,m,\dots ,m}},\underset{m\text{ times}}{\underbrace{m+1,m+1,m+1,\dots ,m+1}},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$.)