**Hello Codeforces,**↵
↵
This is a mathematical proof for why there is at least one perfect square number in the interval [x..2x] for all integers x.↵
↵
**First let's define our problem:**↵
↵
We want to prove that for any interval **[x..2x]** there is at least one perfect square number.↵
↵
(A perfect square number is a number which is the product of an integer with it self)↵
X is said to be a perfect square number if there is another integer Y and this equation holds↵
↵
~~~~~↵
Y * Y = X↵
~~~~~↵
↵
↵
↵
So, now to begin the proof we will look at all perfect square numbers:↵
↵
↵
~~~~~↵
0 1 4 9 16 25 36 and so on...↵
~~~~~↵
↵
↵
↵
let's visualize other integers like this:↵
↵
for an integer X it will be equal to a perfect square number which we will call P + some constant which we will call C↵
So, this equation will hold:↵
↵
↵
~~~~~↵
X = P + C↵
~~~~~↵
↵
↵
↵
↵
So, now if we can prove that 2X will be bigger than or equal to the next perfect square number after P then we can prove that in this interval there will be at least one perfect square number which will be the next perfect square number after P.↵
↵
Let's look to an example:↵
↵
let's assume X = 5, P = 4, C = 1↵
↵
then X = P + C is true↵
↵
now 2X = 10 which is bigger than or equal to 9 and 9 is the next perfect square number after P↵
↵
So, now how to prove this?↵
↵
Since we know that P is the product of an integer with itself we will call that integer N.↵
↵
Now:↵
↵
↵
~~~~~↵
X = N*N + C↵
~~~~~↵
↵
~~~~~↵
↵
X = N^2 + C↵
~~~~~↵
↵
↵
↵
So, now we need to prove that this inequality holds:↵
↵
↵
~~~~~↵
2(N^2 + C) >= (N+1)^2↵
~~~~~↵
↵
Here (N+1)^2 is the next perfect square number after P.↵
↵
Now we need to prove that inequality for N >= 0 and C > 0 only because when C is zero we know that this is already a perfect square number (N^2 + 0 is N^2 and it is a perfect square number).↵
↵
So, back to the inequality:↵
↵
~~~~~↵
2(N^2 + C) >= (N+1)^2↵
~~~~~↵
↵
~~~~~↵
N^2 + C >= ((N+1)^2)/2↵
~~~~~↵
↵
~~~~~↵
C >= ((N+1)^2)/2 - N^2↵
~~~~~↵
↵
~~~~~↵
((N+1)^2)/2 - N^2 - C <= 0↵
~~~~~↵
↵
And since the first partNow, if we can prove that this part of the inequality (((N+1)^2)/2 — N^2 will) is always be <= 0 because if we assumed N^2 is equal to R then (R+1)/2 is always less than or equal to R then (R+1)/2 — R will always be <= 0) and we are subtracting C (where C > 0) from that part then the inequality isless than C for all (N >= 0 and C > 0) then we can prove that the inequality holds for all (N >= 0 and C > 0).↵
↵
And by plotting the following function (((N+1)^2)/2 — N^2):↵
/predownloaded/ec/46/ec46ee0ba849b1eff152676d1778840923eb28a1.png↵
↵
We can see clearly that the maximum value for the function will be 1 when N is equal to 1 and then it will be decreasing while N is bigger than 1.↵
↵
And because C is always bigger than 0 then:↵
↵
~~~~~↵
((N+1)^2)/2 - N^2 - C <= 0↵
~~~~~↵
↵
Will always be true for all (N >= 0, and C > 0).↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
This is a mathematical proof for why there is at least one perfect square number in the interval [x..2x] for all integers x.↵
↵
**First let's define our problem:**↵
↵
We want to prove that for any interval **[x..2x]** there is at least one perfect square number.↵
↵
(A perfect square number is a number which is the product of an integer with it
X is said to be a perfect square number if there is another integer Y and this equation holds↵
↵
~~~~~↵
Y * Y = X↵
~~~~~↵
↵
↵
↵
So, now to begin the proof we will look at all perfect square numbers:↵
↵
↵
~~~~~↵
0 1 4 9 16 25 36 and so on...↵
~~~~~↵
↵
↵
↵
let's visualize other integers like this:↵
↵
for an integer X it will be equal to a perfect square number which we will call P + some constant which we will call C↵
So, this equation will hold:↵
↵
↵
~~~~~↵
X = P + C↵
~~~~~↵
↵
↵
↵
↵
So, now if we can prove that 2X will be bigger than or equal to the next perfect square number after P then we can prove that in this interval there will be at least one perfect square number which will be the next perfect square number after P.↵
↵
Let's look to an example:↵
↵
let's assume X = 5, P = 4, C = 1↵
↵
then X = P + C is true↵
↵
now 2X = 10 which is bigger than or equal to 9 and 9 is the next perfect square number after P↵
↵
So, now how to prove this?↵
↵
Since we know that P is the product of an integer with itself we will call that integer N.↵
↵
Now:↵
↵
↵
~~~~~↵
X = N*N + C↵
~~~~~↵
↵
~~~~~↵
↵
X = N^2 + C↵
~~~~~↵
↵
↵
↵
So, now we need to prove that this inequality holds:↵
↵
↵
~~~~~↵
2(N^2 + C) >= (N+1)^2↵
~~~~~↵
↵
Here (N+1)^2 is the next perfect square number after P.↵
↵
Now we need to prove that inequality for N >= 0 and C > 0 only because when C is zero we know that this is already a perfect square number (N^2 + 0 is N^2 and it is a perfect square number).↵
↵
So, back to the inequality:↵
↵
~~~~~↵
2(N^2 + C) >= (N+1)^2↵
~~~~~↵
↵
~~~~~↵
N^2 + C >= ((N+1)^2)/2↵
~~~~~↵
↵
~~~~~↵
C >= ((N+1)^2)/2 - N^2↵
~~~~~↵
↵
~~~~~↵
((N+1)^2)/2 - N^2 - C <= 0↵
~~~~~↵
↵
↵
And by plotting the following function (((N+1)^2)/2 — N^2):↵
/predownloaded/ec/46/ec46ee0ba849b1eff152676d1778840923eb28a1.png↵
↵
We can see clearly that the maximum value for the function will be 1 when N is equal to 1 and then it will be decreasing while N is bigger than 1.↵
↵
And because C is always bigger than 0 then:↵
↵
~~~~~↵
((N+1)^2)/2 - N^2 - C <= 0↵
~~~~~↵
↵
Will always be true for all (N >= 0
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
