# Floor function: Maths Olympiad problem

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?

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?

• Where does the $(m+1)^2 - 1$ come from? – ar0bx Aug 24 '16 at 8:44
• For $n=m^2,m^2+1,\dots,(m+1)^2-2$, we already have $q(n)\leq q(n+1)$, by the argument that you wrote. – pi66 Aug 24 '16 at 8:45
• Maybe an example would help. Consider $m=2$, so the interval $[4,8]$. For $n=4,5,6,7$, we already know that $q(n)\leq q(n+1)$. So we only need to check $n=8$, i.e., whether $q(8)>q(9)$ or not. – pi66 Aug 24 '16 at 8:48
• Well $q(n) = \lfloor \frac{m^2 + 2m}{m} \rfloor = m+2$ and $q(n+1) = \lfloor \frac{(m+1)(m+1)}{(m+1)} \rfloor = m+1$ – ar0bx Aug 24 '16 at 8:53
• Right, exactly! – pi66 Aug 24 '16 at 8:54

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:

• Can you tell me please what have you plot ? – chaviaras michalis Aug 24 '16 at 9:34
• @chaviarasmichalis I plotted $q(n)$ with $n$ from $1$ to $40$. The red points are the values of the sequence. – rubik Aug 24 '16 at 10:40
• I see ... and how you calculate $$q(m^2 +1 )=\floor{\frac{m^2 -1 }{\floor{\sqrt(m^2 -1) } } }$$ at the formula which you wrote ? – chaviaras michalis Aug 24 '16 at 18:56
• @chaviarasmichalis Assuming you mean $q(m^2 - 1)$, we have: $$q(m^2 - 1) = \left\lfloor\frac{m^2 - 1}{\lfloor\sqrt{m^2 - 1}\rfloor}\right\rfloor = \left\lfloor\frac{m^2 - 1}{m - 1}\right\rfloor = \left\lfloor\frac{(m + 1)(m - 1)}{m - 1}\right\rfloor = m + 1$$ – rubik Aug 24 '16 at 20:16
• Yeah that's what i meant . So can you explain how you figure out that $\lfloor \sqrt{m^2 -1} \rfloor = m-1$ – chaviaras michalis Aug 25 '16 at 19:00