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$$

| cite | improve this question | | | | |
$\endgroup$
  • $\begingroup$ To peter: The picture is not shown on my computer! $\endgroup$ – Victor Mar 10 '12 at 21:41
10
$\begingroup$

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.

| cite | improve this answer | | | | |
$\endgroup$
  • 2
    $\begingroup$ +1: That was quick! Thanks for the link and the name of the book. $\endgroup$ – Aryabhata Mar 3 '12 at 0:04

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.