Floor function: Maths Olympiad problem

Question

Hey I started working on the following problem:

For any real number $x$ let $\lfloor x \rfloor$,denote the greatest integer, which is less than or equal to $x$. Define $q(n) = \lfloor \frac{n}{\lfloor \sqrt{n} \rfloor} \rfloor $ for $n = 1,2,3,...$. Determine all positive integers $n$ for which $q(n)>q(n+1)$.

My attempt:

So I realised that $q(n)$ 'jumps' whenever $n$ moves from a number just below a perfect square to the next perfect square.

This gave me the idea to focus on values of $n$, between $m^2$ and $(m+1)^2$, in order to find out more about the function.

From $m^2 \le n < (m+1)^2$, we can deduce that $\lfloor \sqrt{n} \rfloor = m$. However now I am stuck on how to continue with $q(n) = \lfloor \frac{n}{m} \rfloor$.

It seems to me that the function is increasing, but if yes then wouldn't there be no values for $n$ at all?

Can anyone help me on how to continue please?

Answer 1

You are correct that the function is increasing in the interval $[m^2,(m+1)^2-1]$, so there are no values of $n$ in any interval $[m^2,(m+1)^2-1)$ which satisfies $q(n)>q(n+1)$, for any $m$. This means you only need to check $n=(m+1)^2-1$, for any $m$, because this is where $\lfloor\sqrt{n}\rfloor$ "jumps" when you move from $n$ to $n+1$.

For $n=(m+1)^2-1$, you have $q(n)=\lfloor\frac{m^2+2m}{m}\rfloor$ and $q(n+1)=\lfloor\frac{m^2+2m+1}{m+1}\rfloor$. Can you compare the two?

Answer 2

The function $q(n)$ is piecewise increasing (but not strictly) in every interval $[m^2, {(m + 1)}^2 - 1]$, since if $a, b$ are in that interval (with $a < b$), then $$\left\lfloor\frac a m \right\rfloor = q(a) \leq q(b) = \left\lfloor \frac b m \right\rfloor.$$

Therefore we only need to check where all those intervals "join", and that happens between a perfect square and the preceding number. Indeed we have $q(n) > q(n + 1)$ in this case: $$q(m^2) = \left\lfloor\frac{m^2}m\right\rfloor = m$$ while $$q(m^2 - 1) = \left\lfloor\frac{m^2 - 1}{m - 1}\right\rfloor = m + 1$$

We conclude that the only values of $n$ for which $q(n) > q(n + 1)$ are $$\{m^2 - 1 \mid m \in \mathbb N\} = \{3, 8, 24, \ldots\}$$

I find that plotting the sequence really helps in visualizing the proof: