Is there a Hamiltonian cycle of $m$ x $n$ rectangular lattice points (these are the vertices) in $\mathbb{R}^2$ such that no two edges are parallel?

Question

Let $m,n\geq 2$ and consider the rectangular lattice of $mn$ vertices in $\mathbb{R}^2,\ (i,j);\ i\in \{1,2,\ldots,m\},\ j\in \{1,2,\ldots,n\}.\ $ Call these vertices $X_1, X_2, \ldots, X_{mn}.$ Is there a Hamiltonian cycle of these $mn$ points i.e. vertices such that no two lines (i.e. edges) are parallel? [Edges are allowed to intersect each other and edges are allowed to pass through vertices.] I have tried to find an example for small values of $m$ and $n$ but to no avail. Maybe the answer is no, at least in part due to pigeonhole principle and some induction argument. Alternatively, maybe there are examples for large enough $m,n.$

Answer 1

As discussed in the comments, the length of the $n$-th Farey sequence, that is, the number of irreducible fractions between $0$ and $1$ with denominators up to $n$, is asymptotic to $\frac3{\pi^2}n^2$. Since the differences in an $n\times n$ lattice go up to $n-1$, their possible ratios are given by the $(n-1)$-th Farey sequence and its additive and multiplicative inverses. Thus, asymptotically a square $n\times n$ lattice has $\frac{12}{\pi^2}n^2\approx1.2n^2$ different directions, enough for each of the $n^2$ edges to use a different one.

Here’s Java code that performs an exhaustive search for all solutions. Here’s the number of solutions for all lattices with at most $27$ vertices:

\begin{array}{c|ccc} m\setminus n&3&4&5&6&7&8&9\\\hline 3&❌&16&❌&1800&❌&365128&❌\\ 4&&1880&56120&34669920\\ 5&&&❌ \end{array}

There are no solutions for any of the $2\times n$ lattices (even though they have just enough directions). An ❌ indicates that the lattice has fewer directions than vertices, so there can’t be a solution. Of the remaining lattices, the only one with more directions than vertices is $4\times 6$, which has $26$ directions. This is reflected in the solution count being two orders of magnitude greater than the one for the $3\times8$ lattice, which has the same number of vertices. The enumeration for the $4\times7$ lattice is still running and will take another day or so.

The counts don’t account for symmetry, so for rectangles they include $4$ equivalent copies of each solution, $8$ for the square. These numbers (with or without symmetry reduction) aren’t in OEIS.

Here’s one solution for each of the lattices: