13
$\begingroup$

I've recently watched a fun video about some snakes made up of modules and how we can think about the way they are arranged as follows.

  1. We have a "snake" composed of $n$ modules, including head and tail. That is:

enter image description here

  1. Each joint (?) is flexible so that we can turn it either $0º$ or $90º$ degress, both right or left. For example, with a $3-\text{snake}$ we can make the following (among others):

enter image description here

  1. Suppose we start at the black dot and we place the snake, coding each $n$ placements in a string of letters. We first code the direction of the first module, as $N$, $E$, $W$ or $S$, and from there on, we note wether we're placing the module at $0º$ (straight), $90º$ (leftwards) or $-90º$, (rightwards). As an example, let's code the four configurations above (left to right, left to right)

$E:SS$ $E:RR$ $E:SR$ $E:RL$

  1. Suppose also, that the snake can't run into itself, that is: from $n\geq4$, we can't have a string composed of $n-1$ $R$s or $n-1$ $L$s, since that will mean our snake will run into itself.

Given this rules, can we combinatorially find a way of computing the possible configurations of an $n-\text{snake}$? I guess we can just leave the orientation aside and then multiply by $4$. As an example, I leave the configurations for $n=3$ and starting $E:$, which are:

enter image description here

This means there are a total of $4 \times 9 = 36$ configurations for $n=3$ if I'm not wrong.


It seems easier to compute $\mathcal{S}(4)$ if we use the coding. This gives

$\eqalign{ & SSS - SSR - SSL \cr & SLR - SLS - SLL \cr & SRR - SRL - SRS \cr} $

$\eqalign{ & RRS - RRL - \color{red}{RRR} \cr & RSS - RSL - RSR \cr & RLR - RLS - RLL \cr} $

$\eqalign{ & LLR - LLS - \color{red}{LLL} \cr & LRL - LRR - LRS \cr & LSR - LSL - LSS \cr} $

I'll write some values, without multiplying by $4$:

$\mathcal{S}(1)=3^0=1$ $\mathcal{S}(2)=3^1=3$ $\mathcal{S}(3)=3^2=9$ $\mathcal{S}(4)=3^3-2=25$ $\mathcal{S}(5)=3^4-10=71$

We can say that

$\mathcal{S}(n)=3^n-\mathcal{R}(n)$

The reminder is actually the important thing here. We have that for the first 5 cases

$\mathcal{R} = 0,0,0,2,10$

The reminder of $n=5$ is built up from the case $n=4$ since we just consider the next step. In the first one we set apart

$RRR$ $LLL$

So now we consider the following "products":

$\{R,S,L\} \times RRR= RRRR , SRRR, LRRR$

$\{R,S,L\} \times LLL= RLLL , SLLL, LLLL$

$ LLL \times \{R,S\} = LLLR , LLLS$

$ RRR \times \{L,S\} = RRRL, RRRS$

Thus we have that

$\mathcal{R}(4)\times 5 = \mathcal{R}(5)$

The next remainder will be

$\mathcal{R}(6)=54$

Why? We take $\mathcal{R}(5)$ as a base, and worry about the palindromes, which are

$L???L$ Where we fill in with a triad. So we have

$\eqalign{ & RRRR \cr & RRRL \cr & RRRS \cr} $

$\eqalign{ & RLLL \cr & SLLL \cr & LLLL \cr} $

$\eqalign{ & SRRR \cr & LRRR \cr} $

$\eqalign{ & LLLR \cr & LLLS \cr} $

We apply $\{R,L,S\}\times$ to the left side and get $30$ more cases. And for the right, we apply $\{R,L,S\}\times$ on the right to those that can't be turned into a plaindrome, to get $4$ more cases, plus $2\times$ the $6$ posible palindromes. We get a total of

$10\times 3+3 \times 4 +2\times6 = 54$

Thus

$\mathcal{S}(6)=3^5-54=189$

  • 0
    To peter: The picture is not shown on my computer!2012-03-10

1 Answers 1

10

Although this might feel very simple and playful, this is an unsolved problem that has been considered. In particular, this is equivalent to the following problem:

Start at the origin in the plane. How many self-avoiding 'walks' are there on the integer lattice of prescribed length? Some results include this paper, which relates the number of walks in a strip with fibonacci numbers. Equivalently, the number of snakes that are 'very tall' (so that they're in a strip) is related to the fibonacci numbers.

Madras and Slade have a book, The Self-Avoiding Walk dedicated largely to this problem.

  • 2
    +1: That was quick! Thanks for the link and the name of the book.2012-03-03