×

# Help, RMO sample question

Define $$\displaystyle q(n) = \lfloor \frac{n}{\lfloor \sqrt{n} \rfloor}\rfloor$$ for $$n=1,2,3,\ldots$$. Find all $$n$$ satisfying $$q(n) > q(n+1)$$.

Notation: $$\lfloor \cdot \rfloor$$ denotes the floor function.

Note by Abhishek Alva
1 week, 6 days ago

Sort by:

The solutions are the natural numbers one less than a perfect square, i.e., the solution set is $$S=\{k^2-1\mid k\in\Bbb N\setminus\{1\}\}=\{3,8,15,\ldots\}$$

To prove this, you need to prove that $$q(n)\gt q(n+1)$$ when $$n\in S$$ and $$q(n)\leq q(n+1)$$ otherwise.

For the first part, note that when $$n=k^2-1$$, since the square root function is strictly increasing, we have $$\lfloor\sqrt n\rfloor=k-1$$ which implies that $$q(n)=k+1$$ whereas we have $$\lfloor\sqrt{n+1}\rfloor=k$$ which implies that $$q(n+1)=k$$ which shows that $$q(n)=k+1\gt k=q(n+1)$$ when $$n\in S$$.

Now, for the second part, when $$n\notin S$$, we note that when $$k^2\leq n\lt (k+1)^2-1$$, we have $$\lfloor\sqrt n\rfloor=\lfloor\sqrt{n+1}\rfloor=k$$ which implies that $$q(n)=\lfloor\frac nk\rfloor$$ and $$q(n+1)=\lfloor\frac{n+1}k\rfloor$$. Now, since $$\frac nk\lt\frac {n+1}k$$, applying the floor function on both sides of the inequality, we have $$\lfloor\frac nk\rfloor\leq\lfloor\frac{n+1}k\rfloor$$ from which we conclude that $$q(n)\leq q(n+1)$$. · 1 week, 5 days ago

+2 · 1 week, 5 days ago

Brilliant Solution!+1 · 1 week, 5 days ago

Comment deleted 1 week ago

Comment deleted 1 week ago

Ok @Svatejas Shivakumar.Iam deleting the solution · 1 week, 6 days ago

I meant $$[\dfrac x {\left([a] \right)}]$$. · 1 week, 6 days ago