Let $G$ be a rectangular grid of unit squares with $3$ rows ($3$ rows of squares) and $8$ columns. How many self-avoiding walks are there from the bottom left square of to the top left square of $G$ ?

A self-avoiding walk on a rectangular grid of unit squares is a sequence of moves between horizontally or vertically adjacent squares that does not visit the same square more than once.

Any hints to do this?

  • It looks rather ugly. – Jorge Fernández May 2 '15 at 14:56
  • I think that an extremely intuitive approach would be the easiest. – SalmonKiller May 2 '15 at 14:57

You can solve this by recursion. There is one path straight up. As you move from one column to the next, let $A(n)$ be the number of ways to leave column $n$ on neighboring squares and $B(n)$ the number of ways to leave column $n$ using the top and bottom squares. We have $A(1)=2, B(1)=1.$ If you come in on neighboring squares, you can leave on neighboring squares in one way or on top and bottom squares in one way. If you come in top and bottom, there is one way to leave top and bottom and two ways to leave neighboring, so $A(n+1)=A(n)+2B(n), B(n+1)=A(n)+B(n)$ If the right edge of the path is in column $n$ there are $A(n-1)+B(n-1)$ paths. Our final answer is $1+\sum_{i=1}^7\left(A(i)+B(i)\right)=984$ if my spreadsheet is correct.

$A(n)$ is OEIS A052542 offset by $1$ or twice the Pell numbers and $B(n)$ is A001333. $2B(n)/A(n)$ are convergents to $\sqrt 2$

There are $984$ paths. Suppose you're looking at a vertical cross-section (slice) of the path as it transitions from one column of squares to the next; let's call that a state. There are four possible states: $$\begin{array}{c}\leftarrow\\ \cdot \\ \rightarrow\end{array},\quad \begin{array}{c}\leftarrow\\ \rightarrow \\ \cdot\end{array},\quad \begin{array}{c}\cdot\\ \leftarrow \\ \rightarrow\end{array},\quad\textrm{and}\quad \begin{array}{c}\cdot\\ \cdot \\ \cdot\end{array} $$ where the lines indicate the path crosses at that level, and the dot indicates that the path doesn't cross at that level. Write down the transition matrix between the states -- that is, the number of ways to get from a given state in one column to a given state in the next. With the states ordered as above, the transition matrix is $$A=\pmatrix{ 1 & 1 & 1 & 1 \\ 1 & 1 & 0 & 1 \\ 1 & 0 & 1 & 1 \\ 0 & 0 & 0 & 1 }.$$

We can think of the given path as extending a path which comes in from the left at the bottom, and exits to the left at the top, so the leftmost state is the first one, corresponding to the row vector $(1,0,0,0)$. We have to account for all paths obtainable through $7$ transitions. The four entries in the vector $(1,0,0,0) A^7 = (239,169,169,407)$ thus count all the paths, broken out by what they look like in the rightmost column. Adding them up gives $984$.

No. Squares, $3.8=24$

No. Prime Squares, $8+3.3=17$

Total Squares, $17+24=41$

No. of possible paths, $24.41=984$

  • 1
    Can you please explain your answer a little bit more? – SalmonKiller May 2 '15 at 15:49

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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