Don't Drop to the Floor

Number Theory Level 5

How many distinct integers can be expressed in the form $\left\lfloor \frac {n^2}{2015} \right\rfloor ,$ where $n$ is an integer satisfying $1 \leq n \leq 4030?$

The answer is 3527.

3 solutions

Akshat Sharda
Nov 23, 2015

Let, $a_{n}=\left \lfloor \frac{n^2}{2015} \right \rfloor$

Because $44^2=1936<2015<45^2=2025$ we can conclude that $a_{1}, a_{2}, a_{3},\ldots, a_{44}=0$ .

For positive integers $n\geq 1007$ , since $\frac{(n+1)^2}{2015}-\frac{n^2}{2015}=\frac{2n+1}{2015}\geq 1$ , it follows that $a_{n}<a_{m+1}$ . Hence $a_{1007}, a_{1008},\ldots, a_{4030}$ take distinct values.

For positive integers $n<1007$ , since $\frac{(n+1)^2}{2015}-\frac{n^2}{2015}=\frac{2n+1}{2015}<1$ , it follows that $a_{n+1}\leq a_{n}+1$ . Note that this sequence is clearly non-decreasing. We can conclude that all positive integer values less than $a_{1006}$ have been taken.

Finally we compute that $a_{1006}=502$ .

Therefore, our answer is answer = $503+3024=\boxed{3527}$ (namely, the values $0, 1, 2, \ldots, 502, a_{1007}, a_{1008},\ldots, a_{4030}$ ).

Excellent solution, Akshat. Very well written.

Andrew Ellinor - 5 years, 6 months ago

why do you take 1007?

Dev Sharma - 5 years, 6 months ago

Solve $\frac{(n+1)^2}{2015} - \frac{n^2}{2015} \geq 1 \implies n \geq 1007$ Thus every number after 1007 has a distinct value.

Alan Yan - 5 years, 6 months ago

Excellent solution.

Dipanjan Chowdhury - 5 years, 6 months ago

This solution is not complete as yet. Can you find the gap?

FYI I added the word positive in "all positive integer values less than $a_{1006}$ .

Calvin Lin Staff - 5 years, 6 months ago

What's the gap? Actually I also took the same procedure so I have some gaps too in solving.

Shyambhu Mukherjee - 5 years, 6 months ago

Hm, if I recall correctly. I think the third paragraph previously stated $a_n \leq a_{n+1}$ instead of $a_{n+1} \leq a_n + 1$ .

With $a_{n+1} \leq a_n + 1$ , the proof works with the additional clarification of why $a_n = a_{n+1}$ or $a_{n+1} - 1$ , which would explain why we have that $a_i$ is a sequence that contains 1 to 502.

I believe that he had all of these ideas in his head, but they were just not written down in the solution.

Calvin Lin Staff - 5 years, 6 months ago

@Calvin Lin – Thanks for your reply.

Shyambhu Mukherjee - 5 years, 6 months ago

Lu Chee Ket
Dec 10, 2015

Since the n increment verification is ever increasing or staying, consecutively in an ascending order:

     n:=1.0;
     count:=1;
     Z:
       p:=INT(SQR(n)/2015.0);
       n:=n+1.0;
       q:=INT(SQR(n)/2015.0);
       IF ABS(p-q)>5E-6 THEN
       BEGIN
          INC(count);
          WRITELN(count, ' ', n:1:0, ' ', p:1:0, ' ', q:1:0)
       END;
       IF n>=4030.0 THEN
          GOTO V;
     GOTO Z;
     V:

Initial count is 1. Total change determined = 3526. Therefore, total distinct = 3527.

Answer: $\boxed{3527}$

Dhiraj Agarwalla
Nov 29, 2015

Till n=1008 the function will assume all numbers from 0 to 504. after that all other n will generate a distinct number. Therefore the answer must be [505+(4030-1008)]= 3527. We might arrive at the above conclusion by noticing that till [ (n+1)^2 - (n^2)] is less than equal to 2015 the function will generate all numbers because the difference of [{(n+1)^2}/2015] and [{n^2}/2015] will be less than 1 and hence no number will be skipped. Now by putting the obtained value "1008" in the function we get the value "504". After n=1008 the difference between consecutive terms will be greater than 1 and hence each time a new number will be generated.

Here {}, [] signify normal brackets.

Don't Drop to the Floor

The answer is 3527.

3 solutions

0 pending reports