Bueno, resulta que, el aparentemente simple e inocente problema de las serpientes en realidad es un problema abierto en el área de combinatoria enumerativa.
Antes de plantear el problema que me interesa ahora, primero tengo que platicar cómo no se resuelve el problema de las serpientes.
Lo más natural al intentar resolver el problema es hacer algunos casos pequeños para darse una idea del comportamiento de la sucesión.
Como se sugirió en la entrada anterior, cada serpiende queda codificada por una sucesión de letras, indicando hacia dónde se hacen los giros. Tabulando las cantidad de serpientes para cada longitud tenemos:
1, 2, 4, 6, 10, 16, 26,…
Salvo los dos primeros términos, cada uno es igual a la suma de los dos anteriores, como en los números de Fibonacci. De hecho, salvo el primero todos son el doble de un número de Fibonacci. Vamos a denotar por el número de serpientes de longitud n y por
al n-ésimo número de Fibonacci. Conjeturamos entonces:
.
Fijándonos en las palabras que codifican cada serpiente, si I es un giro hacia la izquierda y D un giro para la derecha, entonces la lista de serpientes comienza como:
. Sólo hay una palabra, vacía.
. Hay 2 palabras, indicando los dos posibles giros: I, D.
. Las palabras posibles son II, ID, DI, DD.
. Las palabras válidas son IID, IDI, IDD, DII, DID, DDI. Nótese que III, DDD no son palabras váldias pues hacer 3 giros consecutivos en la misma dirección regresa al punto inicial y por tanto la serpiente se tocaría a sí misma.
. Las palabras aquí son IIDI, IIDD, IDII, IDID, IDDI, DIID, DIDI, DIDD, DDII, DDID.
Unos casos más podrían convencernos que las serpientes corresponden a palabras donde no hay 3 símbolos consecutivos iguales.
Ahora, antes de seguir hay que aclarar que la descripción anterior sólo es corecta hasta n=11, porque a partir de entonces hay serpientes no válidas que no tienen 3 símbolos seguidos. Por ejemplo:
- IDIIDIIDIID no es una serpiente válida, pues termina en el punto inicial y por tanto se corta a sí misma.
Esto quiere decir que la descripción simple que conjeturamos para las serpientes no es la correcta. De hecho, tampoco es cierta la conjetura de que el número de serpientes siempre es el doble de un número de Fibonacci (y precisamente a partir de n=12 falla la conjetura.
¿Cual es entonces la sucesión real de número de serpientes? ¿Porqué los primeros términos de la sucesión están relacionados con los números de Fibonacci?
Para calcular los valores reales de la sucesión usamos la computadora para generar todos los caminos hasta cierta longitud. El siguiente programa, en el lenguaje de programación Ruby genera todas las posibles serpientes y muestra la sucesión asociada.
#! /usr/bin/ruby # coding: utf-8 def dir(q,p) # dirección de p-->q v=[q[0]-p[0],q[1]-p[1]] if v == [0,1] return :N elsif v==[0,-1] return :S elsif v==[1,0] return :E elsif v==[-1,0] return :W end end def mueve(x, d) if d == :N return [x[0], x[1]+1] elsif d == :S return [x[0], x[1]-1] elsif d == :E return [x[0]+1,x[1]] elsif d == :W return [x[0]-1,x[1]] end return [x[0],x[1]] end def gira(d, c) #puts "girando #{d}" if c == 1 # giro positivo if d == :N return :W elsif d == :W return :S elsif d == :S return :E elsif d== :E return :N end elsif c== -1 #giro negativo if d == :N return :E elsif d == :E return :S elsif d == :S return :W elsif d == :W return :N end end end def recorre(s) # Esta función "recorre" una cadena y regresa falso si se corta a sí misma puntos=[[0,0],[1,0]] s.downcase! s.each_char{ |c| p=puntos[-2] q=puntos[-1] diractual = dir(q,p) if c == "d" newdir=gira(diractual, -1) elsif c=="i" newdir=gira(diractual, 1) elsif c=="a" newdir = diractual end a=puntos[-1] b=mueve(a,newdir) if puntos.include?(b) return false break else puntos << b end } return s end def main #Aquí generamos todas las serpientes levels=[""] print "1" 0.upto(20){ |n| #Iteramos sobre todas las longitudes past=levels new=[] past.each{ |s| # Y para cada una de longitud n-1, intentamos extenderla if recorre(s+"i") then new << s+"i" end if recorre(s+"d") then new << s+"d" end #if recorre(s+"a") then new << s+"a" end # Activar esta línea para permitir avanzar sin girar #puts "level #{n} genera #{new}" } print ", #{new.length}" # Finalmente mostramos cuántas hubo en ese nivel levels = new } end main
El resultado de correr el programa es
1, 2, 4, 6, 10, 16, 26, 42, 68, 110, 178, 282, 452, 724, 1160, 1842, 2936, 4688, 7480, 11844, 18826, 29956
que difiere de la sucesión de dobles de Fibonacci a partir de la posición 12.
1, 2, 4, 6, 10, 16, 26, 42, 68, 110, 178, 288, 466, 754, 1220, 1974, 3194, 5168, 8362, 13530, 21892, 35422
Podemos consultar datos sobre la segunda sucesión en la base de datos OEIS