Recientemente he visto un video divertido de algunas serpientes compone de módulos y cómo podemos pensar acerca de la forma en que están organizados de la siguiente manera.
- Tenemos una "serpiente", compuesto de $n$ módulos, incluyendo la cabeza y la cola. Que es:
- Cada articulación (?) es flexible, de modo que podemos pasar bien $0º$ o $90º$ grados, tanto a la derecha o a la izquierda. Por ejemplo, con un $3-\text{snake}$ podemos realizar los siguientes (entre otros):
- Supongamos que vamos a empezar en el punto negro y ponemos la serpiente, la codificación de cada una de las $n$ colocaciones en una cadena de letras. Tenemos primero el código de la dirección del primer módulo, como $N$, $E$, $W$ o $S$, y a partir de ahí, se nota si nos va a colocar el módulo en $0º$ (en línea recta), $90º$ (hacia la izquierda) o $-90º$, (rightwards). Como ejemplo, vamos a código de las cuatro configuraciones de arriba (de izquierda a derecha, de izquierda a derecha)
$$E:SS$$ $$E:RR$$ $$E:SR$$ $$E:RL$$
- Supongamos también, que la serpiente no se puede ejecutar en sí misma, es decir: de $n\geq4$, no podemos tener una cadena compuesta de $n-1$ $R$s o $n-1$ $L$s, ya que significa que nuestra serpiente se ejecutará en sí mismo.
Dada esta reglas, podemos combinatoria encontrar una manera de calcular las posibles configuraciones de un $n-\text{snake}$? Supongo que puede dejar sólo la orientación de un lado y luego se multiplica por $4$. Como ejemplo, os dejo las configuraciones para $n=3$ e iniciando $E:$, los cuales son:
Esto significa que hay un total de $4 \times 9 = 36$ configuraciones para $n=3$ si no estoy equivocado.
Parece más fácil de calcular $\mathcal{S}(4)$ si utilizamos la codificación. Esto le da
$$\eqalign{ & SSS - SSR - SSL \cr & SLR - SLS - SLL \cr Y SRR - SRL - SRS \cr} $$
$$\eqalign{ & RR - RRL - \color{red}{RRR} \cr Y RSS - RSL - RSR \cr Y RLR - RLS - RLL \cr} $$
$$\eqalign{ Y LLR - LLS - \color{red}{LLL} \cr Y LRI - LRR - LRS \cr Y LSR - LSL - LSS \cr} $$
Voy a escribir algunos de los valores, sin multiplicar por $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$$
Podemos decir que
$$\mathcal{S}(n)=3^n-\mathcal{R}(n)$$
El recordatorio de que en realidad es lo importante aquí. Tenemos que para los primeros 5 casos
$$\mathcal{R} = 0,0,0,2,10$$
El recordatorio de $n=5$ se construye desde el caso de $n=4$ ya que acabamos de considerar el siguiente paso. En el primero ponemos aparte
$$RRR$$ $$LLL$$
Así que ahora tenemos que considerar los siguientes "productos":
$$\{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$$
Así tenemos que
$$\mathcal{R}(4)\times 5 = \mathcal{R}(5)$$
La próxima resto será
$$\mathcal{R}(6)=54$$
Por qué? Tomamos $\mathcal{R}(5)$ como base, y la preocupación acerca de los palíndromos, los cuales son
$$L???L$$ Donde rellenamos con una tríada. Así tenemos
$$\eqalign{ Y RRRR \cr Y RRRL \cr Y RRRS \cr} $$
$$\eqalign{ Y RLLL \cr Y SLLL \cr & LLLL \cr} $$
$$\eqalign{ Y SRRR \cr Y LRRR \cr} $$
$$\eqalign{ Y LLLR \cr Y LLLS \cr} $$
Aplicamos $\{R,L,S\}\times$ a la izquierda y consigue $30$ más de casos. Y para el derecho, aplicamos $\{R,L,S\}\times$ sobre el derecho a aquellos que no pueden ser convertidas en un plaindrome, para obtener el $4$ más de casos, además de a $2\times$ $6$ posible palíndromos. Tenemos un total de
$$10\times 3+3 \times 4 +2\times6 = 54$$
Así
$$\mathcal{S}(6)=3^5-54=189$$
