$\forall x,y\in \mathbb N\ ,\ \exists\ z\in\mathbb N$ that $x+z$ is square but $y+z$ is not square. I am trying to prove this:

$\forall x,y\in \mathbb N$ and $x\neq y,\  \exists\  z\in\mathbb N$ that $x+z$ is
  square but $y+z$ is not square.

$\mathbb N$ is set of natural numbers. 
Can you please suggest a hint?
 A: You know how far apart $x$ and $y$ are.  Look for squares that are further apart than that.
A: Let's suppose that $x > y$ (or swap the labels). 
For any positive integer $n$ greater than $\sqrt{x}$, let $z = n^2 - x$. Then $x+z$ is square. But suppose that $x+z$ and $y+z$ are both square, say 
$$
x+z = n^2\\
y+z = p^2
$$
Evidently $n$ and $p$ are distinct, and both may be taken to be positive. Furthermore, $z$ is positive, and $x+z > y + z$ (because $x > y$), so $n > p > 0$. 
Then 
$$
x - y = (x+z) - (y+z) = n^2 - p^2 = (n+p)(n-p).
$$
Thus the positive number $n + p$ (which is less than $2n$, because $p < n$) is a factor of  $x-y$. If you do this for $n = 1, 2, 4, 8, 16, ...$ you get infinitely many distinct positive factors of the positive number $x-y$, which is impossible. 
[BTW, I prefer Michael's solution, but figured I'd include this one anyhow.]
A: Suppose the contrary; that is, suppose that for each pair $x$, $y$ of distinct natural numbers, the following is true: 
For every natural umber $z$, if $x+z = m^2$ for some natural number $m$, then $y+z = n^2$ for some (other) natural number $n$. 
Obviously, $m \neq n$ since $x\neq y$. 
Then we must have $$z = m^2 - x = n^2 - y,$$ 
and so we must have $$x-y = m^2 - n^2,$$ 
Which is clearly false, for example, when $x=2$ and $y=1$ for the smallest difference (in absolute value) between the squares of two natural numbers is $3$. In any case, there are no natural numbers $m$ and $n$ whose squares differ by $1$. So a contradiction arises, and our assertion is proved. 
