Sum of the numbers in the corner cells of every square in the table is perfect square In every cell of $100 \times 100$ table, there is a natural number.
The numbers in the same row or the same column are all distinct.
Is it possible that sum of the numbers in the corner cells of every square in the table 
is perfect square ?
Example : coordinates of corner cells of one $3\times3$ square is $(1,1), (1,3), (3,1), (3,3)$.
Source : St Peterburg Olympiad 2012, Grade 9

My attempt :
Let $S$ be sum of the number in all cells of the table.
Divide $100 \times 100$ table into $2500$ $\;2\times2$ squares.
Since sum of numbers in each $2\times2$ square is perfect square, we have
$S = a_1^2 + a_2^2 + \ldots + a_{2500}^2$ where $a_1, a_2, \ldots, a_{2500} \in \mathbb{N}$ 
Could someone please help ?
 A: A good place to start would've been to try filling in a $2 \times 2$ or $3 \times 3$ or $4 \times 4$ table before thinking about the $100 \times 100$. This could end in a number of ways:


*

*If you get stuck filling in the $4 \times 4$, say, then you'll get stuck filling in the $100 \times 100$ as well, and you have a proof.

*If the small tables force you to a specific pattern, you can try to see if that pattern extends to $100 \times 100$.


But in fact, what we learn from the small examples is that this problem is underconstrained: it is not terribly hard to complete the tables, even if we make lots of arbitrary decisions. At the same time, it's not a "just-do-it" type of problem: it's possible to make bad decisions that will cause you to get stuck later.
What this type of problem calls for is making some sort of structural assumption: adding additional constraints of your own that might make the solution either unique or at least more likely to follow a pattern. Some desirable features in these additional constraints would be:


*

*They could reduce the complexity of specifying the entire $100 \times 100$ table. After all, you don't want a solution that specifies all $10000$ entries one at a time.

*They could make many of the squares look identical, so we also have fewer squares to check.


In this problem, an additional assumption that turns out to work is that the table follows the pattern
\begin{array}{cccccc}
   a_1 & a_2 & a_3 & \cdots & a_{99} & a_{100} \\
   a_2 & a_3 & a_4 & \cdots & a_{100} & a_{101} \\
   a_3 & a_4 & a_5 & \cdots & a_{101} & a_{102} \\
   \vdots & \vdots & \vdots &\ddots & \vdots & \vdots \\
   a_{99} & a_{100} & a_{101} & \cdots & a_{197} & a_{198} \\
   a_{100} & a_{101} & a_{102} & \cdots & a_{198} & a_{199}
\end{array}
That is, the $(i,j)$ entry is labeled with $a_{i+j-1}$ for some sequence $a_1, a_2, \dots, a_{199}$ that we have yet to determine. This has the nice feature that every group of corner cells looks like
\begin{array}{ccc}
   a_m & \cdots & a_{m+n}\\
   \vdots &  & \vdots \\
   a_{m+n} & \cdots & a_{m+2n}
\end{array}
so all you have to do is make sure that $a_m + 2a_{m+n} + a_{m+2n}$ is a perfect square for any $m$ and $n$.
I'm going to stop the solution here, with the assurances that there is such a sequence, and that it can be found easily if you follow the same problem-solving strategies I outlined above.
