# Arranging numbers from $1$ to $n^2$ in a $n\times n$ board

Can the numbers $1,2,...,n^2$ be written in the cells of an $n\times n$ board in such a way that any two consecutive numbers are in adjacent cells (sharing a side), and all perfect squares are in the same column?

Note: The original problem comes from All-Russian Mathematical Olympiad 1995 (fourth round, question 8) for the special case where $n=11$.

By counting the number of cells in the left and right side of that column we know that for an odd number $n$, there's not an arrangement satisfying those conditions. So we only have to consider the case where $n$ is even.

For $n=4k+2$ we can make explicit construction, but writing it down clearly may be difficult. For $n=4k$, it seems that there's no arrangement. However, I have no idea how to prove it.

Can someone solve the case completely where $n$ is even?

• What's your intuition for your idea that there is no arrangement for $n=4k$? Can you attempt to write down your construction for $n=4k+2$? Can you tell us any specific properties of the construction, at least? – Jalex Stark Mar 20 '18 at 17:26
• imgur.com/PyOZNgR is an example for $n=10$, and I believe such construction generalizes for $n=4k+2$. – Hw Chu Mar 20 '18 at 17:33
• "By counting the number of cells in the left and right side of that column we know that for an odd number n, there's not an arrangement satisfying those conditions." I don't understand what you mean. Please add a few details. – saulspatz Mar 20 '18 at 19:35
• I think $n=4$ can be shown impossible through pretty straightforward enumeration: there are four places for the $1$ modulo symmetry, but the corner location fails trivially and it's easy to show that 'edge' locations fail after placing the $4$; this means that there's only one place the $1$ can go. But now there are - again modulo symmetry - only four paths for $1-2-3-4$ to take, and whichever one is used, it's possible to show that one 'runs out of room' for $9$ and $16$ in the appropriate places. I'm not sure how that generalizes to $4k$ in general, though, since there's more freedom there. – Steven Stadnicki Mar 20 '18 at 19:56

The $n=10$ case can indeed be used to prove that all $n=4k+2$ can be done: The line that follows the numbers in ascending order just sweeps back and forth in a repeating big letter 'C' pattern, and after the last sweep to the right bottom it 'snakes' up, and then goes left to end at $n^2$. I realize this picture is not a rigorous mathematical proof, but can easily be made into one by induction. Oh, and by the way, this pattern works for $n=6$ as well, and I assume that if we express the pattern in a clever way, we might even find $n=2$ an instance of that pattern, though that case is in itself trivial.
As far as the $4k$ goes: I am pretty sure that the above is really the only way to make this work (modulo symmetries of course) for the $4k+2$; before you posted your picture of the $n=10$ I had already come to the conclusion that that was the only way to do it. The $4k$ case is going to be likewise restricted in how to proceed the line, and I am convinced that indeed it's not going to work out there. If I have some more time, I may actually try and generate the argument.