2
$\begingroup$

This problem was motivated by the classic phone game Snake.

Consider the square grid graph with vertex set $V := \{1, \dots, N\}^2$, for fixed odd positive integer $N$, and an edge between $(x, y)$ and $(x’, y’)$ iff $|x - x’| + |y - y’| = 1$.

Question: How many paths are there from $(1, 1)$ to $(N, N)$ that do not repeat any vertex but traverse all vertices? Can we get, if not exact results, asymptotics in $N$?

Improve this question
$\endgroup$
5
  • 2
    $\begingroup$ Maybe doi.org/10.1016/0012-365X(95)00330-Y is one paper to start looking at. There is no hope of an exact solution here. Even precise asymptotics are not so easy, I think, and ought to be related to deep questions in statistical mechanics $\endgroup$
    – Sam Hopkins
    Commented Oct 15 at 14:24
  • $\begingroup$ Yes I expect an exact solution to be more or less impossible haha @SamHopkins $\endgroup$
    – Nate River
    Commented Oct 15 at 14:25
  • 3
    $\begingroup$ By a simple parity argument there are none for even $N$, so if you want to talk asymptotics you need to restrict to odd $N$. $\endgroup$
    – Peter Taylor
    Commented Oct 15 at 14:40
  • $\begingroup$ @PeterTaylor Yes that makes sense.. $\endgroup$
    – Nate River
    Commented Oct 15 at 14:43
  • 1
    $\begingroup$ OEIS A001184 doesn't have much other than a few small terms. The cross-referenced sequence A121788 has a couple of links to an archived website by I. Jensen, but the archive is timing out on the page "Series Expansions for Self-Avoiding Walks", and "Crossing Hamiltonian walks" just lists the terms. The name of the non-loading page suggests that it might be similar in content to the paper Sam Hopkins linked above. $\endgroup$
    – Peter Taylor
    Commented Oct 15 at 15:30

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .