11
$\begingroup$

For how many integers $1 \leq n \leq 2015$ does the following equation hold? $$\left\lfloor\sqrt{2015(n-1)}\right\rfloor = \left\lfloor\sqrt{2015n}\right\rfloor$$

I have been struggling with this simple-looking problem for a while. What I have done so far:

If $n \leq 504$, we can make use of $\sqrt{2015(n-1)}<\sqrt{2015n}-1$ to write $$\left\lfloor\sqrt{2015(n-1)}\right\rfloor \leq \sqrt{2015(n-1)} < \sqrt{2015n}-1 < \left\lfloor\sqrt{2015n}\right\rfloor,$$ and hence the equation does not hold. For $n>504$, I get stuck. I wrote a MATLAB code to find such $n$ that satisfies the equation. The first few values of $n$ are $544, 565, 581, 595, \dots $ but I can't find a pattern. Can you please give me a hint?

PS. The problem comes from a 27th Chilean 2015-16 mathematical olympiad.

$\endgroup$
  • 1
    $\begingroup$ Hint: suppose it's true. Then there's some $m$ with $m\leq \sqrt{2015(n-1)}\lt\sqrt{2015n}\lt m+1$. Square every piece of this chain (and note that this is legal because all the terms involved are positive and $a\leq b$ iff $a^2\leq b^2$ for positive $a,b$). $\endgroup$ – Steven Stadnicki Feb 2 '17 at 1:35
  • 1
    $\begingroup$ Perhaps one can use a similar method to what's used here: math.stackexchange.com/questions/190605/… $\endgroup$ – Brenton Feb 2 '17 at 1:35
  • $\begingroup$ @StevenStadnicki Your approach is correct, but I don't understand how it helps me solve the problem. As you mentioned, we are looking for $(m,n)$ such that $m^2<2015(n-1)$ and $(m+1)^2>2015n$. But how do we find them? $\endgroup$ – Amir Hossein Feb 2 '17 at 1:54
  • $\begingroup$ @Brenton Thanks for the link, but I don't think that method works here. We would find $$\frac{m^2}{n-1}<2015<\frac{(m+1)^2}{n}$$ and it would be the same approach as what Steven wrote. $\endgroup$ – Amir Hossein Feb 2 '17 at 1:55
  • 1
    $\begingroup$ Nice question! Do you have a link to the problem set? $\endgroup$ – N.S.JOHN Feb 2 '17 at 14:12
4
$\begingroup$

Edit: Directly solving OP's question (using the same idea as below):

$$\sqrt{2015n}-\sqrt{2015(n-1)}\le 1$$ is true for $n\ge 504$ and false for $n\le503$

So when $n=1,2,\ldots,503$ we have $\sqrt{2015n}$ takes only distinct values (as the difference between two consecutive values is greater than $1$), for a total of $503$ values.

For $n=504,505,\ldots,2015$, we have $\sqrt{2015n}$ does not skip any values (as the difference between two consecutive values is less than $1$), so $\sqrt{2015n}$ takes all the values between $\lfloor \sqrt{2015\cdot 504}\rfloor=1007$ and $\lfloor\sqrt{2015\cdot 2015}\rfloor=2015$, a total of $2015-1007+1=1009$ values.

So when $1\le n\le 2015$, we have that $\sqrt{2015n}$ takes $1512$ distinct values; the non-distinct values duplicating the previous values, since they are increasing with $n$.

So the number of solutions of the equation is $2015-1512=503$


The original problem in the link asks to determine the number of different values of $\big\lfloor\frac{n^2}{2015}\big\rfloor$, for $1\le n\le 2015$. I think that your equation is equivalent to the number of duplicates (I will verify when I get a chance)

The solution is to take the difference of two consecutive terms and compare it with $1$:

$$\frac{n^2}{2015}-\frac{(n-1)^2}{2015}=\frac{2n-1}{2015}\le1\iff n\le1008$$

As long as $n\le 1008$, no value will be skipped, so all values between $0$ and $\big\lfloor\frac{1008^2}{2015}\big\rfloor=504$ will be taken ($505$ values).

When $n>1008$ each term will generate a new value, So we have $2015-1008+1=1008$ new values.

The total is $505+1008=1513$ distinct values

The number of duplicates is $2016-1513=503$. So for $502$ values your equation holds.

$\endgroup$
  • $\begingroup$ Oh, I was using a bad approach. This works, thanks! $\endgroup$ – Amir Hossein Feb 3 '17 at 15:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.