×

# 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 year, 5 months ago

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold
- bulleted- list
• bulleted
• list
1. numbered2. list
1. numbered
2. list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1paragraph 2

paragraph 1

paragraph 2

[example link](https://brilliant.org)example link
> This is a quote
This is a quote
    # I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
# I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
MathAppears as
Remember to wrap math in $$...$$ or $...$ to ensure proper formatting.
2 \times 3 $$2 \times 3$$
2^{34} $$2^{34}$$
a_{i-1} $$a_{i-1}$$
\frac{2}{3} $$\frac{2}{3}$$
\sqrt{2} $$\sqrt{2}$$
\sum_{i=1}^3 $$\sum_{i=1}^3$$
\sin \theta $$\sin \theta$$
\boxed{123} $$\boxed{123}$$

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 year, 5 months ago

+2

- 1 year, 5 months ago

Brilliant Solution!+1

- 1 year, 5 months ago

Comment deleted Oct 15, 2016

Comment deleted Oct 15, 2016

Ok @Svatejas Shivakumar.Iam deleting the solution

- 1 year, 5 months ago

I meant $$[\dfrac x {\left([a] \right)}]$$.

- 1 year, 5 months ago

how to solve the problem

- 1 year, 5 months ago