Dgdrxrt

Let consider a square $10times 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?

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.]

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 $10times 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.