Hello Codeforces,

This is mathematical proof that the GCD between the sum of even indices and the sum of odd indices of a consecutive set of integers is always greater than one.

Note: A special case for this problem is when the size of the set is <= 2 then the GCD will be equal to 1, So I assume that the given set size is greater than 2.

And also We assume X >= 1.

First let's define our problem:

Given a consecutive set of integers: X, X + 1, X + 2, X + 3,.....

We want to prove that if we took the sum of the even indices (assuming zero-based indexing): sumOfEven = X + X + 2 +.... And took the sum of the odd indices: sum of odd = X + 1 + X + 3 +...

Then GCD(sum of even, sum of odd) > 1 always.

So let's assume C1 will be the number of even indices in our set and C2 will be the number of odd indices in our set.

sum of even = C1*X + C1*(C1 - 1) = C1*X + C1^2 - C1

sum of odd = C2*X + C2^2

Now we have two cases:

First if C1 = C2:

sum of even = C1*X + C1^2 - C1 = C1(X + C1 - 1)

sum of odd = C1*X + C1^2 = C1(X + C1)

We can notice that the GCD will be C1 and since the size of the set size is > 2 then C1 >= 2, the GCD will always be greater than one.

Second if C1 != C2:

Then we can notice that C1 = C2 + 1 because if the size is even then C1 must be equal to C2 otherwise C1 will be odd and will be equal to C2 + 1.

sum of even = C1(X + C1 - 1)

sum of odd = (C1 - 1)(X + C1 - 1)

We can notice that both of the sums are divisible by X + C1 - 1 then we know that the GCD will be at least X + C1 - 1 and because if C1 != C2 and the size of the set is > 2 then C1 >= 2 and because X >= 1 then X + C1 - 1 >= 2 which implies that GCD between the two sums will be always > 1.

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)