Longest path in a square grid


Problem

What is the longest path in a square grid from one corner to the diagonally opposite corner?

Edges in the grid may only be traversed once, but grid nodes can be used multiple times (in a square grid that means twice maximum).


Solution

After fiddling with this for a while, you will likely find that:


In a 2x2 grid, the longest path is 8:


In a 3x3 grid, the longest path is 18:


In a 4x4 grid, the longest path is 32:


In a 5x5 grid, the longest path is 50:


Using the method of second differences, it seems that in an nxn grid, the longest path will be \(2n^2.\) Now we aim to prove this:

There are \(2n(n + 1)\) potential edges in the grid, but some of them need to be left out because the grid nodes on the boundary have only \(3\) potential edges meeting, but only \(2\) of them can be in a path.

Additionally, one edge incident to the starting node, and one edge incident to the ending node, must be left out.

The trick to counting these left-out edges, is to think in terms of half-edges. For example, looking at the top row of nodes, the top left node has a half edge reaching towards the second node in the row, and the second node in the row has a half edge reaching left to the top left node. Thus, every node on the boundary, which is not a corner node, is incident to 3 half-edges. Every corner node is incident to 2 half-edges. Now, counting the number of left-out half-edges, we get at least

$$4(n - 1) + 2 = 4n - 2$$

The \(4(n - 1)\) is the number of half-edges left out by the non-corner nodes. The \(2\) is the number of half-edges left out by the start and end nodes. Thus, at least \(2n - 1\) of the \(2n(n + 1)\) edges must be missing. So at most there are

$$2n(n + 1) - (2n - 1) = 2n^2 + 1$$

edges in the path.

However, the length of the path must be even: Color the grid nodes alternately black and white in a checkerboard pattern. Two opposite corners will have the same color, but every move changes the color, so there must be an even number of moves.

This shows that the the length of the path is at most \(2n^2.\)

On the other hand, it should be clear the pattern we've found achieves this number for larger \(n\) too, so it is the actual maximum.


The problem and solution come from here. I modified it here because I felt the term "half-edges" needed a bit of clarification. Also, the expression \(4(n - 1) + 2\) was a bit confusing without a brief explanation.