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
9 months, 1 week ago

No vote yet
1 vote

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 · 9 months, 1 week ago

Log in to reply

@Prasun Biswas +2 Abhishek Alva · 9 months, 1 week ago

Log in to reply

@Prasun Biswas Brilliant Solution!+1 Ayush Rai · 9 months, 1 week ago

Log in to reply

Comment deleted 9 months ago

Log in to reply

Comment deleted 9 months ago

Log in to reply

@Svatejas Shivakumar Ok @Svatejas Shivakumar.Iam deleting the solution Ayush Rai · 9 months, 1 week ago

Log in to reply

@Svatejas Shivakumar I meant \([\dfrac x {\left([a] \right)}]\). Svatejas Shivakumar · 9 months, 1 week ago

Log in to reply

@Svatejas Shivakumar how to solve the problem Abhishek Alva · 9 months, 1 week ago

Log in to reply

×

Problem Loading...

Note Loading...

Set Loading...