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 part (((N+1)^2)/2 — N^2 will 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 is always true for all (N >= 0, C > 0).