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 itself) 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

Now, if we can prove that this part of the inequality (((N+1)^2)/2 — N^2) is always less 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):

We can see clearly that the maximum value for the function will be 1 when N is equal to 1 and then it will decrease while we increase N.

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)