6
$\begingroup$

Imagine an $n \times n$ grid, we start on one corner of the grid in square $A$, and need to reach the opposite corner to square $B$. The rules are, you can only move to an adjacent square, you can't move diagonally and you must pass every square exactly once. How many possible routes are there in an $n \times n$ grid?

It is always $0$ if $n$ is even, and I know that the answer is $2$ for $n = 3$. I have a couple of ways of approaching this problem but no general formula.

$\endgroup$
1
$\begingroup$

As Joriki correctly points out in his answer, this has already been researched, and there is no closed form known. Instead, there are asymptotic estimates given. However, it would be nice to have something elementary here on this site, so I'll share a really basic lower-bound argument which I'll call the "snake" argument.

Consider an $n \times m$ grid, with $n$ odd. One way to construct such a path in this grid is to snake as follows:

$$(0, 0) \rightarrow (0, 1) \dots \rightarrow (0, m) \rightarrow \\ (1, m) \rightarrow (1, m - 1) \dots \rightarrow (1, 0) \rightarrow \\ \dots \rightarrow \\ (n, 0) \rightarrow (n, 1) \rightarrow dots \rightarrow (n, m)$$

But if you "zoom out", and consider the entire $n \times m$ rectangle as a single column of length $n$, then we can repeat the snake process i.e. we can move along this rectangle of size $n \times m$, then back along another of possibly a different size $n \times m'$, and so forth.

Now, any sequence of numbers $m_1, m_2, \dots, m_h$ such that $\sum_{k =1}^h m_k = n$ corresponds to exactly one such snaking path. So we have a lower bound on the number of paths is the number of numbers that sum up to our number in question. By stars and bars, this number is simply $2^{n -1}$, which is a lower bound on the number of paths for square size $n$. Obviously this is pathetic compared to the known bound $\tau^{O(n^2)}$, but at least the derivation is elementary and not completely trivial: it's at least an exponential bound in $n$.

I feel like this idea could be carried a good deal further as I have only considered a very restricted subset of these "snaking" structures. Also, this very easily generalises from a square to a rectangle.

Example Image for Snaking Below

Rough Sketch of the Snake Idea


A rough argument as to why this function grows as $\tau^{n^2}$ is as follows. Let $A_n$ be the number of such paths from the bottom left corner of a square of side length $n$ to its top right corner. Now consider a square of side length $n^2$, i.e. $n^4$ cells in total.

Now, we can "zoom out" from this square and notice that it has $n^2$ sub-squares each of side length $n$. It is then possible to construct a path in this large square by combining paths in each of these subsquares. So we have the recurrence inequality $A_{n^2} \geq (A_n)^{n^2}$. From here we can reason inductively. Assuming $A_n \geq C \tau^{n^2}$ then $A_{n^2} \geq C \tau^{n^4}$. And so on for $n^8, n^{16}, n^{32}, \dots, n^{2^k}, \dots$ So that's intuitively why it grows at that rate.

$\endgroup$
  • $\begingroup$ thanks for the answer, but I didn't understand the second half of your argument. Could you please explain what it means by 'repeat the snake process' and the corresponding sums part? $\endgroup$ – Dis-integrating Sep 4 '15 at 14:42
  • $\begingroup$ @gebra, I'll just draw a picture, hold on to your horses. $\endgroup$ – Colm Bhandal Sep 4 '15 at 14:55
  • 1
    $\begingroup$ OK that was a quick pic, and the individual cells are not shown, but as you can see from the bottom left corner the "snake" starts from left to right, moving up and down within its sub-rectangle, then it goes right to left, then left to right etc. Note that I've purposely added rows $3$ and $6$ with width $1$ to show the special case of the snake being just a straight line. $\endgroup$ – Colm Bhandal Sep 4 '15 at 15:03
  • 1
    $\begingroup$ Note that any division of the large square into such rectangles gives a unique snake. So there are at least that many solutions. Now, also note that each solution corresponds to the height of the square being cut into a number of pieces, in this case $6$. We can cut into any number of pieces we like- by the well known stars and bars method (see en.wikipedia.org/wiki/Stars_and_bars) the number of ways to paritition a number like this is just $2^{n - 1}$, assuming all numbers are non-zero. $\endgroup$ – Colm Bhandal Sep 4 '15 at 15:06
  • 1
    $\begingroup$ Great. I've added another little thought explaining the factor of $n^2$ in the exponent. Bit messy due to nested exponents, but hopefully the main point is clear enough. $\endgroup$ – Colm Bhandal Sep 5 '15 at 18:42
4
$\begingroup$

I wrote this code to find the counts $104$ for $n=5$ and $111712$ for $n=7$. That leads to OEIS sequence A001184 (authored by Don Knuth in $1995$), which in turn leads to OEIS sequence A121788, which in turn leads to this paper, Self-avoiding walks crossing a square by M. Bousquet-Mélou, A. J. Guttmann and I. Jensen.

No closed form seems to be known; the paper states (on p. $24$) that the number of these Hamiltonian paths for odd $n$ grows as $\tau^{n^2}$ with $\tau\approx1.472$.

$\endgroup$
  • $\begingroup$ Nice research! And for even $n$? $\endgroup$ – Colm Bhandal Sep 4 '15 at 11:40
  • 1
    $\begingroup$ @ColmBhandal: The OP correctly stated that there are no such Hamiltonian paths for even $n$. You can show this with a checkerboard argument: For even $n$, the start and end square have the same colour. $\endgroup$ – joriki Sep 4 '15 at 11:41
  • 1
    $\begingroup$ Checkerboard argument: fantastic. I had seen the OPs conjecture but was looking for a proof of it. $\endgroup$ – Colm Bhandal Sep 4 '15 at 11:46
  • $\begingroup$ I'm not quite sure what L refers to in the paper. In table 6 p. 25 it seems to be $n+1$. Could someone please explain? $\endgroup$ – Dis-integrating Sep 4 '15 at 12:04
  • 1
    $\begingroup$ @gebra: There are two sources of confusion here. One is that they use $L$ with two different meanings in Section $9$. The other is that they consider walks between nodes along edges whereas you consider walks from square to square. An $L\times L$ lattice in their notation corresponds to an $(L+1)\times(L+1)$ grid in yours, with $n=L+1$, so when they talk about $2L\times2L$ lattices, that corresponds to $(2L+1)\times(2L+1)$ grids in your setup, with $n=2L+1$. $\endgroup$ – joriki Sep 4 '15 at 12:09

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.