2009/10 AHSMC Part 1 Problem 5

Observe that $x^2 - y^2 = (x - y)(x + y)$ is the product of two integers of same parity. Hence $x^2 - y^2$ is either odd or divisible by $4$. Thus a number which is neither odd nor divisible by $4$ cannot be expressed as a difference of two squares. On the other hand, if $n$ is odd, then $n = 2k + 1 = (k + 1)^2 - k^2$. If $n$ is divisible by $4$, then $n = 4k = (k + 1)^2 - (k - 1)^2$. Between $1$ and $2009$ inclusive, there are $1005$ numbers that are odd and $502$ that are divisible by $4$. The answer is (D).