Visto en Resistencia numantina.
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.
Nota del editor del blog: El vídeo está en coreano (creo), pero se pueden poner subtítulos en inglés (si no aparecen automáticamente) en uno de los botones de abajo.