12
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Jalex Stark Mar 20 '18 at 17:26
  • 1
    $\begingroup$ imgur.com/PyOZNgR is an example for $n=10$, and I believe such construction generalizes for $n=4k+2$. $\endgroup$ – Hw Chu Mar 20 '18 at 17:33
  • $\begingroup$ "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. $\endgroup$ – saulspatz Mar 20 '18 at 19:35
  • $\begingroup$ 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. $\endgroup$ – Steven Stadnicki Mar 20 '18 at 19:56
6
$\begingroup$

The $n=10$ case can indeed be used to prove that all $n=4k+2$ can be done: enter image description here

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.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.