How Many Self-Avoiding Walks are there in a 3x8 Grid of Nodes where all nodes must be traversed.

Question

You must start from the bottom left corner of the grid and end at the top right corner. From my research, most solutions focus on all possible self-avoiding walks but not the specific case where every single node is passed through. I understand simpler cases where the movement is restricted to right and up moves but not the general case where you can move down and left. I am trying to look for an invariant in the question and I think that there must always be 23 moves but that doesn't really get me anywhere. Any hints to do this question? The solution seems to be 64.

Answer 1

You will find that from experimentation for small $n$ that for a grid with $3$ rows and $n$ columns with $n>1$,

• the number of acceptable routes from bottom left to top right is $t(n)=2^{n-2}$
• the number of acceptable routes from bottom left to bottom right $b(n) =2^{n-2}$ too.

In discovering this, you should be able to see that $t(n)=1+\sum\limits_{i=2}^{n-1} b(i)$ and $b(n)=1+\sum\limits_{i=2}^{n-1} t(i)$, justified with diagrams like this

and so the proof of the result can use strong induction.