Let consider a square $10$x$10$ and write in the every unit square the numbers from $1$ to $100$

Question

Let consider a square $10\times 10$ and write in the every unit square the numbers from $1$ to $100$ such that every two consecutive numbers are in squares which has a common edge. Then there are two perfect squares on the same line or column. Can you give me an hint? How to start?

Answer 1

We note the following:

1. Write the coordinates of $k$ as $(i_k,j_k)$, where $i_k$ is the column that $k$ is in; $i_k \in \{1,2,\ldots, 10\}$; and $j_k$ is the row that $k$ is in; $j_k \in \{1,2,\ldots, 10\}$. Then if $i_k+j_k$ is even, then $i_{k+1} + j_{k+1}$ must be odd, for each $k=1,2,\ldots, 99$.

2. If $i_{k^2} + j_{k^2}$ is even, then $i_{(k+1)^2} + j_{(k+1)^2}$ must be odd, as $(k+1)^2-k^2$ is an odd integer, for each $k=1,2,\ldots, 9$.

3. We call a square $k^2$ even-even if $i_{k^2}$ and $j_{k^2}$ are both even. and we call a square $k^2$ odd-odd if $i_{k^2}$ and $j_{k^2}$ are both odd. We call a square mixed otherwise. Then if $k^2$ is odd-odd or even-even, then $(k+1)^2$ must be mixed.

So from 3 we have the following:

4. Precisely 5 squares are mixed and precisely 5 squares that are either even-even or odd-odd.

But this is impossible unless a row or column has at least 2 squares:

Indeed: Either at least 3 of the squares $k^2; k=1,2,\ldots, 10$; are even-even, or at least 3 of the squares are odd-odd. LEt us assume that 3 of the squares are even-even. Then if every row and column has exactly one square, then of the 5 mixed squares, only 2 can be in an even column (as 3 of the even columns were already taken by the 3 even-evens and so there are only 2 even columns left). And likewise, only 2 can be in an even row. But this implies that at least one (i.e. $5-2-2$) of the 5 mixed squares is odd-odd after all, which contradicts 4. above. [The likewise holds by the same line of reasoning holds if 3 of the squares are odd-odd.]

Answer 2

Here are several successively more revealing hints, hidden behind spoilers in case you want to try the problem after only reading one or two.

Hint 1:

Color your $10\times 10$ board like a checkerboard. What can you say about the colors of the squares containing perfect squares?

More specifically:

How does the color of square $1$ compare to that of $4$? And how does $4$ compare to that of $9$? Etc.

Hint 2:

In general, show that for any $10$ squares in pairwise different rows and columns, an even number of these squares must be black.

Assuming that a path where the perfect squares are in different rows and columns exists, combine this fact with the conclusion of Hint $1$ to get a contradiction.

Hint 3:

This goes into more detail about how to prove the first sentence of Hint $2$.

Suppose there are $10$ squares in pairwise different rows and columns. A square in row $i$ and column $j$ is black if and only if $i+j$ is even.

Suppose square in row $i$ is in column $\pi_i$, where $\pi$ is a permutation of $\{1,2,\dots,n\}$. Then the summation $\sum_{i=1}^{10}(i+\pi_i)$ is equal in parity to the number of black squares, so you need to prove this summation is even.