jueves, 4 de octubre de 2012

Números combinatorios, supercomputadoras y la edad del universo


Tomemos una cuadrícula n x n. ¿De cuántas maneras diferentes podemos atravesarla desde la esquina (0,0) hasta la (n,n) sin pasar por el mismo punto dos veces?

Para n pequeño es posible encontrar a mano todos los caminos. Es fácil convencerse de que en la figura superior están los 2 caminos posibles para el caso n=1 y los 12 caminos posibles para el caso n=2. Más tedioso es el cálculo para valores de n algo más grandes, pero si uno es algo hábil programando no le resultará muy difícil hacer un programa que genere por "fuerza bruta" todas las posibilidades.

Parece fácil ¿verdad? Pues vean en el siguiente vídeo lo que ocurriría si intentásemos usar nuestro programa para calcular el caso n=10, aún usando para ello una potente supercomputadora.



Imágen tomada de: Weisstein, Eric W. "Self-Avoiding Walk." From MathWorld--A Wolfram Web Resource. http://mathworld.wolfram.com/Self-AvoidingWalk.html