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.
Asked
Active
Viewed 51 times
1
-
What have you tried? Have you found results on smaller grids? – Chris Lewis Sep 07 '23 at 11:41
-
i've tried taking cases but it just seems way too complicated. i haven't found a systematic way of counting cases, ik for a 2x2 grid it would be 2 cases, 3x3 grid would also be two cases but then for non-square grids it becomes a lot more challenging – weekly5112 Sep 07 '23 at 11:50
-
There's a formula here (but not a derivation): https://mathworld.wolfram.com/Self-AvoidingWalk.html – Chris Lewis Sep 07 '23 at 13:36
1 Answers
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.
Henry
- 157,058
-
For a more general point of view (that you don't need for your exercise), see here – Jean Marie Sep 07 '23 at 13:01
-
1@JeanMarie $3$ is a special case (so too are $1$ and $2$ in different ways) and I suspect it becomes much harder with $4$ – Henry Sep 07 '23 at 13:03