Combinatorics – Hamiltonian Path for NxN Grid with All Possible Ending Points

combinatoricsgraph theoryhamiltonian-path

On a $3\times3$ grid, draw a path that starts in the center of a square in the corner of the grid,
and repeatedly moves from the center of one square to the center of an adjacent square,
without visiting any squares twice, and such that every square in the grid is included.
For example, the following is a path that meets these conditions:

(a) What are the possible ending positions for a path drawn according to these rules? What
if you started from an edge square or the center square of the grid? Explain.
(b) Repeat the above problem for a $4\times4$ grid.
(c) Can you describe what happens in general for an n×n grid where n is a positive integer?

My work:

For the $3\times3$ grid, I tested all possible combinations and I found that the when starting from a corner square: All other corner squares and the center square was reached.
When I started from the center square, I reached all corner squares.

Question:
For a $4\times4$ grid, and a $N\times N$ grid, what are the possible ending points?

Here is a diagram for reference. This is a valid path for a $3\times3$ grid.

This is a valid path for a 3x3 grid

Best Answer

Observation: Color the squares of the grid such as in a chessboard. Assume that the starting corner of the board is white. Show that the final square must be white/black when $n$ is odd/even respectively. Thus, the final square must be a different square of an appropriate color.

Prove that the above condition is sufficient to be a final square.

Hint: One way to do this is using induction. The base case $n = 2$ is easy to verify. For any $n = k + 1$ where $k \geqslant 2$, observe that if you start in the top-right corner, go all the way down to the bottom-left corner, all the way right to the bottom-right corner, and one step up, you will land on a corner of the $k \times k$ board on the top-right. Using the induction hypothesis, any square of the appropriate color in this $k \times k$ board, except the starting corner (if it is the appropriate color), can be reached. The same can be said for the bottom-left $k \times k$ board. It suffices to show that the final corner can be the bottom-right corner if $n$ is odd or the two squares adjacent to the bottom-right corner if $n$ is even. Show this explicitly.

Related Question