Adjacent houses

Question

We propose a game that is quite simple:

You choose a house to start (the starting house).

From this square you must move to the adjacent square (left, right, above or below) with the lowest value yet to be traversed.

Going from one house to another, you follow a path that ends when you reach a point where all the adjacent houses have already been covered. If your path has gone through all the $n^2$ squares, we say that the initial square "won" and we paint it green. Otherwise, we say it "failed" and paint it red:

See Figure 1 that the path starting at $15$ failed and starting at $16$ won

In figure 2 we have all the squares painted in green (won) or red (failed) on boards $3 \times 3$ and $4 \times 4$

Show that on a board $n \times n$, the corner squares (numbered by $1, n, (n-1)n+1$ and $n^2$) are always green

Attempt: It is known that for the quadrilateral $2 \times 2$ it works that all the corner squares are green. So for $3 \times 3$ we see that it will preserve the first property and will have to show it to the other corners (where one corner already preserves this property). Then part of you now build another problem which is: If we take squares $2 \times 2$ and we cover our squared $n \times n$ will the property of being green be established for which houses?

Answer 1

I would not try to do induction on the board size, but just use a direct proof. First note that starting from $1$ works even if the board is not square. You go right along the top row, left along the second row, right along the third and so on until you complete all the rows.

Then note that you only care about the order of the numbers in the squares, not on the actual value. If we delete the top row of a board we have a board that is still numbered in rows in the same order. If we start from square $n$ we go left along the top row, then go down one square and continue the alternation like we had started at square $1$. If we delete the left column of a board we have a board that is still numbered in rows in the same order, so we will succeed if we start from the upper left square. If we start on a square board in the lower left, in square $n(n-1)$, we go vertically up the left column, then right one square and solve that board. If we start from $n^2$ we go up the right column, then left along the top row, and start an $(n-1) \times (n-1)$ board from the upper left.

Answer 2

The rules for movement can be stated more simply as follows:

Try to move in all directions in the order $\{\uparrow,\gets,\to,\downarrow\}$, moving in the first direction for which movement is possible.

This is because the sorted order of the four squares around you is always $\{x-n,x-1,x+1,x+n\}$, unless you are on the border and you have to remove some of those.

With this simple description of the rules, it is easy to see what path you will follow when you start in each of the four corners. For example, starting in the lower left corner, you will start by moving to the top row (since moving $\uparrow$ when possible is preferred), and then move right all the way to the right edge (since $\uparrow$ and $\gets$ are impossible, so $\to$ is preferred), and then you will finally move down to the next row, traverse it left, and so on, snaking your way down to the bottom. I think you can give a simple description of the paths starting from the other three corners, and why they cover the whole grid.