Japan Mathematical Olympiad

Since $(n+1{)}^2-n^2=2n+1$ holds for any positive integer $n$, the difference of any contiguous pair of perfect squares, larger of which is no more than $500^2=250000$, does not exceed $2\cdot 499+1=999$. From this fact it follows that for any positive integer $m$ satisfying $100\le m<250$, there exists a perfect square of 6 digits whose top 3 digits coincide with $m$. For if there is no such perfect square for some such $m$, then the smallest perfect square greater than or equal to $100(m+1)$ and the largest perfect square less than or equal to $1000m$ will constitute a contiguous pair of perfect squares less than or equal to $500^2$ and with difference more than $1000$.

On the other hand, the difference of any contiguous pair of perfect squares, the smaller of which is greater than or equal to $500^2$, is at least $2\cdot 500+1=1001$, the top 3 digits of $500^2,501^2,\dots ,999^2$ are all distinct.

Consequently, the numbers that can appear as the top 3 digits of a 6-digit perfect square are every $m$ satisfying $100\le m<250$ and the top 3 digits of the numbers $500^2,501^2,\dots ,999^2$, and there are exactly $150+500=650$ such numbers.