4
$\begingroup$

Make a path from one corner of a square grid to the diagonally opposite corner, using horizontal and vertical edges between the grid points. What is the maximum number of times the path can cross itself?

A path "crosses itself" when it has passed through a grid point in a straight line and later passes through the grid point again in a straight line, which is perpendicular to the first line. See example below.

enter image description here

Edges can only be traversed once.

For $N \times N$ grids where $N$ is odd, the problem is easy as shown for $N=5$ below:

enter image description here

The number of crossings here is $C= 16 = (N-1)^2$. This is also the maximum number of crossings because crossings are only possible at interior grid points, i.e. grid points which are not on the perimeter, and all interior grid points here have a crossing. This is obviously true for any grid where $N$ is odd.

But when $N$ is even, I cannot immediately find the answer. If the path were allowed to end at the same corner it started at, the solution would be easy:

enter image description here

The solution would again be $C=(N-1)^2$. But the path must end at the diagonally opposite corner. My best attempt for $N=4$ is shown below:

enter image description here

This has $C=6$ crossings. Is this the maximum possible? What is the maximum possible for even $N$?

$\endgroup$
  • $\begingroup$ One may ask the same question for $N\times M$ grids, in which case you have a problem if either $M$ or $N$ is odd. You may be able to try out smaller cases however. $\endgroup$ – Bob Krueger Jul 11 '18 at 23:47

Your Answer

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

Browse other questions tagged or ask your own question.