Snakes (parte I)

Snake, snake, snake, snake, snake, snake, snake, snake, snake, …

Hace unos días, vihart subió un video a youtube en el cual muestra diferentes cosas que hace con unas serpientes para armar.

Ahora, entre todas las cosas que dice, la parte que me interesa aquí está entre 0:45 y 1:30 donde plantea un par de problemas matemáticos relacionados.

El primero de ellos podría describirse así: considera una serpiente formada por 10 segmentos. Cada segmento forma un ángulo de 90º respecto al anterior. ¿Cuantas serpientes (lo que llama slithers) se pueden obtener?

Por ejemplo, si las serpientes están formadas por 4 segmentos, algunas posibles opciones serían las siguientes

Ejemplos de serpientes con 4 segmentos. La flecha indica la posición de la cabeza.

Inmediatamente surge el primer problema. ¿Cuando decir que dos serpientes son iguales? ¿Será cierto que la primera y la tercera serpiente del ejemplo son iguales?

Esa pregunta, al menos, la resolvemos usando un truco clásico, ilustrado en el video: codificar un problema combinatorio mediante palabras.   En el video se muestra que cada serpiente corresponde a una serie de letras indicando su estructura (estando en inglés, pone L para izquierda, R para derecha).

Nosotros indicaremos con la I un giro a la izquierda y con D un giro a la derecha. Así, por ejemplo, las 3 serpientes del ejemplo corresponden a las palabras

IID, IDI, DDI.

En la primera, por ejemplo, al recorrer el primer segmento (horizontal) se hace un giro de 90º hacia la izquierda y por tanto se continúa hacia arriba; después del segundo segmento se gira hacia la izquierda nuevamente, quedando el camino apuntando hacia la izquierda; finalmente se hace un giro hacia la derecha y la cabeza termina apuntando hacia arriba. Esos giros los representamos como IID.

La otra regla implícita es que una serpiente no puede en ningún momento tocarse (por ejemplo, una instrucción III haría que la cabeza toque la cola (se forma un cuadrado), lo cual no es válido.

Para dejar completamente en claro el problema, ilustramos las 6 distintas serpientes que se pueden hacer con 4 segmentos:

 

Las 6 serpientes formadas con 4 segmentos

Observación: nota que la dirección inicial no importa realmente, sólo la forma de la serpiente. Por ello, para simplificar los dibujos, siempre he puesto el primer segmento horizontal y hacia la derecha (piensa en una cuadrícula…).  Esto quiere decir que una serpiente la podemos girar, pero no podemos levantarla y reflejarla. Por eso, la segunda serpiente en ambas figuras es la misma: IDI, mientras que, aunque también es una escalera, la quinta DID es diferente, porque no se puede girar para hacerla coincidir con IDI.

El segundo problema es completamente similar, excepto que no se requiere que cada segmento forme un ángulo de 90º con el anterior, sino que se permite que varios segmentos avancen en la misma dirección; a estas variantes les llama snakes (y que aquí llamaremos víboras). Así, una víbora que no es serpiente podría ser:

Una víbora: derecha-avance-izquierda

En este caso tenemos tres posibilidades para movimiento: Derecha, Izquierda y Avanzar.

Problemas.

Entonces, tenemos los dos problemas planteados:

  1. Determinar el número de serpientes con 10 segmentos.
  2. Determinar el número de víboras con 10 segmentos.

Sin embargo, lo que me llamó la atención de este problema, planteado de pasada en apenas un minuto, es que tiene muchas matemáticas detrás, y es posible plantear muchas preguntas interesantes acerca del problema (algunas de las cuales hasta ahora desconozco la respuesta).

El primer paso siguiente es evidente para cualquiera que tenga sensibilidad para las matemáticas:

  • ¿Cual es el número de serpientes con n segmentos?
  • ¿Cual es el número de víboras con n segmentos?

En caso que no sea posible encontrar una fórmula cerrada ¿hay algún tipo de recurrencia? (Bueno, si la hay es muy probable que se puede encontrar también  una fórmula cerrada usando el método de funciones generadoras)

Un problema intermedio para la resolución anterior es:

  • ¿Cuales son las condiciones necesarias y suficientes para que una palabra sea una serpiente o una víbora? Es decir, encontrar una forma de decidir si una sucesión como IDDIDIDDDII es una serpiente o no (porque podría cruzarse a sí misma. Y de forma similar, una forma para decidir si una sucesión de letras forma una víbora válida.

Por otro lado, aunque son problemas muy parecidos, podría ser posible que uno problema tenga solución sencilla y el otro no.

Al intentar resolver el problema, es natural empezar a realizar casos pequeños. Sin embargo, después de unos cuantos segmentos el problema se hace tedioso manualmente. Esto crea nuevos problemas de otro estilo:

  • Elaborar un programa de computadora que liste (y por tanto cuente) todas las serpientes con n segmentos.
  • Elaborar un programa de computadora que liste (y por tanto cuente) todas las víboras con n segmentos.

Si te tomas unos minutos haciendo dibujos, observarás que puede haber muchísimas direcciones. Por otro lado, que los ángulos sean rectos y que los segmentos todos sean iguales, sugiere que las serpientes en realidad son caminos sobre un plano cartesiano:

Una serpiente es un camino reticular en el plano cartesiano

Inmediatamente se me ocurren dos problemas :

  • Determinar (sin necesidad de un dibujo) la posición de la cabeza a partir de una palabra. Por ejemplo la palabra IDDIDI termina en (4,-1). ¿Cómo se llega a esa conclusión sin dibujar?  Nuevamente, tenemos un problema para serpientes y otro para víboras.
  • ¿Cual es el  menor rectángulo que contiene a la serpiente (víbora)? En la figura anterior es el rectángulo de 2×2 que tiene esquinas (0,0), (2,2). (Piensa en la menor caja en la que cabría la serpiente).

En ambos problemas asumimos que el primer movimiento es de (0,0) a (0,1), es decir, una unidad en la dirección x. (No era tan arbitraria la elección hecha arriba al dibujar las serpientes).

Finalmente, podemos obtener una nueva clase de problemas (y para éstas repetir todos los anteriores) si en vez de 90º indicamos que las serpientes tengan que formar un ángulo que sea múltiplo de 60º. Por ejemplo, una hexaserpiente podría ser algo como:

Una hexaserpiente, moviéndose sobre una retícula triangular

Yo creo que un buen problema matemático no sólo es aquél que es interesante resolver en sí mismo y ya, sino que al mismo tiempo permite formular muchas ideas nuevas, plantear nuevas preguntas, generalizaciones, variantes, etc.

Mucha suerte con las serpientes.

Ah, y ¡feliz día π!

Anuncios

Responder

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s