Banda.'s blog

A proof for why there is at least one perfect square number in the interval [x..2x].
By Banda., history, 20 months ago, In English

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)

  • Vote: I like it
  • +17
  • Vote: I do not like it

Comments Comments (7)
| Write comment?
»
20 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Another proof: 1. Chek basic simples for n=1,2,3; 2. For n>=4: Obviously, in the last inequality, the right side is greater or even 1 for n>=4.

→ Reply
»
20 months ago, # |
← Rev. 2   Vote: I like it +14 Vote: I do not like it

$$$\sqrt{2x} = \sqrt{2} \sqrt{x}$$$, if $$$x \ge 6$$$ then $$$\sqrt{2} \sqrt{x} \ge \sqrt{x} + 1$$$ so there is always an integer in $$$\left[\sqrt{x}, \sqrt{2x}\right]$$$, for smaller $$$x$$$ one can check manually.

→ Reply
»
20 months ago, # |
  Vote: I like it +10 Vote: I do not like it

You can also do this trick. Write out squares $$$3^2, 4^2, 5^2, \ldots$$$ and note that $$$\frac{(k+1)^2}{k^2}$$$ is decreasing. Since $$$\frac{16}{9} < 2$$$ thus all ratios between these consecutive squares is less than two and we cannot have some $$$k^2 < n < 2n < (k+1)^2$$$ for $$$n \geq 9.$$$ For smaller $$$n$$$ you can check directly.

→ Reply
»
20 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I remember proving this intuitively for a recent contest. We just need the fact that the differences between square numbers are the odd numbers. Namely, if $$$n = k^2$$$, then $$$n + (2k+1) = (k+1)^2$$$.

Then, try to find the first interval of the form $$$[x, 2x]$$$ which does not have a square number in it. Imagine we're drawing them on the number line.

 1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16
[x  .] .  .  .  .  .  .  .  .  .  .  .  .  .  .
 . [.  .  x] .  .  .  .  .  .  .  .  .  .  .  .
 .  . [.  x  .  .] .  .  .  .  .  .  .  .  .  .
 .  .  . [x  .  .  .  .] .  .  .  .  .  .  .  .
 .  .  .  . [.  .  .  .  x  .] .  .  .  .  .  .
 .  .  .  .  . [.  .  .  x  .  .  .] .  .  .  .
 .  .  .  .  .  . [.  .  x  .  .  .  .  .] .  .
 .  .  .  .  .  .  . [.  x  .  .  .  .  .  .  x]

We quickly see that this never happens. When we move the interval $$$[x, 2x]$$$ one place to the right, the square numbers that may be inside won't leave the interval unless it is exactly the first number in it -- in other words, when $$$x = k^2$$$. At this point, see that, intuitively, we will always find a square number in the next interval because the distance between them grows linearly on $$$k$$$, yet the size of the intervals grows quadratically.

The formal proof would be that the next square number is exactly $$$2k+1$$$ places to the right, which is inside the next interval $$$[(x+1), 2(x+1)]$$$ because $$$k^2 + 2k + 1 \leq 2(k^2+1) = 2k^2+2$$$ if and only if $$$2k \leq k^2 + 1$$$. This is true because $$$k^2 - 2k + 1 = (k-1)^2 \geq 0$$$.

I liked this approach since it's pretty easy to see visually. Plus, it shows how important it is to have good intuition on how functions grow asymptotically.

→ Reply
»
20 months ago, # |
  Vote: I like it +10 Vote: I do not like it

There's a much tighter bound. Let $$$x = \lceil \sqrt{n} \rceil$$$. Consider $$$x^2$$$. Note that $$$x^2 < (\sqrt{n} + 1)^2 = n + 2 \sqrt{n} + 1$$$. $$$x^2$$$ is an integer, so from this bound, it follows that $$$x^2 \le n + \lceil 2 \sqrt{n} \rceil$$$. So your earlier bound $$$[n, 2n]$$$ can be significantly improved to $$$[n, n + \lceil 2 \sqrt{n} \rceil]$$$.

→ Reply