Yesterday I gave my 10-year-old son the following problem:
"Given an arbitrary positive integer, find the nearest perfect square."
This is his solution (pseudocode):
int tal = input("Enter an integer: ")
float x = sqrt(tal)
int a = round(x)
print(a*a)
When I saw the solution I immediately told him it was wrong.
But is it?
His solution is obviously wrong if tal isn't restricted to the positive integers.
However if tal is a positive integer I haven't found any counterexample that proves that my sons algorithm is wrong. In fact I have tested all integers 1 to 10^9. However, I haven't been able to prove that the algorithm is correct, or incorrect.
(This is annoying since my intention was to teach him exactly that the algorithm he came up with is incorrect. The restriction of the domain to the positive integers was to make it easier to parse the input to the program.)
There are two possible perfect squares to consider.
I only consider "rounding up", since the other case is similar.
If tal = x^2 is a positive integer and (x+r) is an integer for some 0 < r < 1/2, then we have (x + r)^2 = x^2 + r^2 + 2xr, which is a perfect square.
The "other" perfect square to consider is, with s = 1-r:
(x – s)^2 = x^2 + s^2 – 2xs
The difference of the differences to x^2 is:
dd(r,x) = d1 + d2 = 1 + 2r^2 + 4xr – 2r – 2x =
= 1 – 2r + 4xr – 2x + 2r^2
-> 1/2 as r -> 1/2, for any x.
However, the limit is a simplifications, and not correct, since in reality x=f(tal) and r = g(x).
Nevertheless if the algorithm is correct then dd < 0.
For 2x(2r -1) it seems that when tal = x^2 is an integer if I try to make r as close to 1/2 as possible x grows "fast" enough to offset (2r – 1) tending to 0, thus making abs(ddb) > r^2 – 2r + 1.
Anyway, if my sons algorithm is correct it must rely on tal being a positive integer (and nothing in my reasoning above is applicable only if tal is a positive integer).
Is the algorithm incorrect or not?
The answer (fixed some typos and added small changes), from @fleablood
For all positive numbers $m$ there is a non-negative integer $n$ such that $n^2 \le m < (n+1)^2= n^2 + 2n + 1$.
If $n^2 \le m \lt n^2 + n + \frac 12$ then the nearest square is $n^2$. If $n^2 + n + \frac 12 < m < n^2 + 2n + 1$ then the nearest square is $(n+1)^2$. Thus for an integer $m$ if $n^2 \le m \le n^2 + n$ the nearest square is $n^2$, and if $n^2 + n + 1 \le m < n^2 + 2n + 1$ the nearest square is $(n + 1)^2$.
Taking square roots: $n \le \sqrt{m} < n+1$.
When we round $\sqrt{m}$ we will get $n$ if $n \le \sqrt{m} \lt n+ \frac 12$ and $n+1$ if $\sqrt{m} > n + \frac 12$.
If $n \le \sqrt{m} \lt n+ \frac 12$ then $n^2 \le m \lt n^2 + n + \frac 14 $. However since $m$ is an integer $m \le n^2 + n$.
Thus for all m where round($\sqrt{m}$) is $n$, $m$ is closer to $n^2$ than to $(n+1)^2$.
If $ n+ \frac 12 < \sqrt{m} < n+1$ then $n^2 + n + \frac 14 < m < (n+1)^2 = n^2 + 2n + 1$. Since $m$ is an integer, $m \ge n^2 + n + 1$.
Thus for all integers m where round($\sqrt{m}$) is $(n + 1)$, $m$ is closer to $(n + 1)^2$ than to $n^2$.
For non integers there is a range from $n^2 + n + \frac 14 < m < n^2 + n + \frac 12$ where the algorithm fails and returns the upper square even though the lower square is closer to m.
Best Answer
As for all positive integers $m$ there is an $n$ so that $n^2 \le m < (n+1)^2= n^2 + 2n + 1$.
If $n^2 \le m \le n^2 + n$ then the nearest square is $n^2$. If $n^2 + n < m < n^2 + 2n + 1$ then then nearest square is $(n+1)^2$.
Taking square roots. $n \le \sqrt{m} < n+1$. When we round:
this will give $n$ if $\sqrt{m} \le n+ \frac 12$ and will give $n+1$ if $\sqrt{m} > n + \frac 12$.
And if $n \le \sqrt{m} \le n+ \frac 12$ then $n^2 \le m \le n^2 + n + \frac 14$. And if $ n+ \frac 12 < \sqrt{m} < n+1$ then $n^2 + n + \frac 14 < m < (n+1) = n^2 + 2n + 1$.
As $m$ is an integer these give precisely the correct nearest perfect squares. (For non integers there is a range from $n^2 + n + \frac 14 < m < n^2 + n + \frac 12$ where this algorithm fails.)
SO your son's algorithm works perfectly. I'm a little perplexed as to why you thought it was wrong.