14
$\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$
6
  • 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$ Feb 2, 2017 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, 2017 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$ Feb 2, 2017 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$ Feb 2, 2017 at 1:55
  • 1
    $\begingroup$ Nice question! Do you have a link to the problem set? $\endgroup$
    – N.S.JOHN
    Feb 2, 2017 at 14:12

1 Answer 1

8
$\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$
1
  • $\begingroup$ Oh, I was using a bad approach. This works, thanks! $\endgroup$ Feb 3, 2017 at 15:59

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .