Waste less time on Facebook — follow Brilliant.
×

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, 2 months ago

No vote yet
1 vote

  Easy Math Editor

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold

- bulleted
- list

  • bulleted
  • list

1. numbered
2. 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 1

paragraph 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} \)

Comments

Sort by:

Top Newest

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)\).

Prasun Biswas - 1 year, 2 months ago

Log in to reply

+2

Abhishek Alva - 1 year, 2 months ago

Log in to reply

Brilliant Solution!+1

Ayush Rai - 1 year, 2 months ago

Log in to reply

Comment deleted Oct 15, 2016

Log in to reply

Comment deleted Oct 15, 2016

Log in to reply

Ok @Svatejas Shivakumar.Iam deleting the solution

Ayush Rai - 1 year, 2 months ago

Log in to reply

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

Brilliant Member - 1 year, 2 months ago

Log in to reply

@Brilliant Member how to solve the problem

Abhishek Alva - 1 year, 2 months ago

Log in to reply

×

Problem Loading...

Note Loading...

Set Loading...