Tanto el triángulo de Sierpinski como el triángulo de Pascal y las Torres de Hanoi son bastante conocidos para cualquiera que haya visitado con deleite el mundo de las matemáticas. Quizá no sea tan conocido el nexo que une el primero con los otros dos. Eso es lo que intentaré mostrar en este post.
El triángulo de Sierpinski es un fractal que surge de repetir el mismo proceso, hasta el infinito, a partir de un triángulo equilátero. El proceso consiste en dividir el triángulo de partida en 4 semejantes uniendo los puntos medios de los lados del triángulo inicial. Luego eliminamos el triángulo central y volvemos a repetir el proceso con cada uno de los otros triángulos equiláteros que nos han quedado. Así una y otra vez, y otra más, y otra, hasta el fin de los tiempos y más allá. En la imagen puedes observar las primeras seis iteraciones:
Este triángulo, como todos los fractales, tiene curiosas características. Sólo nos vamos a detener en el área, porque la vamos a necesitar para más tarde. Aunque en un primer momento parezca que no, es relativamente fácil calcularla sin más que fijarnos en lo que ocurre en las primeras etapas de la construcción y generalizar. Digamos que el triángulo inicial tiene área 1. Después de la primera etapa hemos eliminado un triángulo con área ¼, así, nos quedamos con ¾. En la segunda etapa, nos quedamos con 9 triángulos de los doce que quedan (¾), es decir, el área es ahora de ¾ x ¾. Observando un poco podemos generalizar sin problema y llegar a la conclusión de que en la etapa n tendremos un área de (3/4)n y, por lo tanto, cuando n tiende a infinito, el área tiende a cero.
Pero, de la misma forma que pasa con cualquier espécimen, el mundo (en este caso el matemático) sería bastante aburrido si sólo existieran triángulos de Sierpinski, de ahí que haya surgido una generalización de ese triángulo. ¿Cómo? Sólo tenemos que dividir cada lado del triángulo inicial en k partes iguales y luego trazar paralelas a los lados para formar triángulos equiláteros del mismo tamaño. Luego eliminamos los triángulos que tienen un vértice mirando hacia abajo (para entendernos). Repetimos el mismo proceso con cada triángulo que nos ha quedado, y así una y otra vez. En el dibujo se muestra el triángulo obtenido en la segunda etapa con k = 5.
Ya estamos en condiciones de asomar la cabeza por el Triángulo de Pascal y las Torres de Hanoi.
Sierpinski y Pascal
Primero, para el que no lo conozca, haré una breve descripción del Triángulo de Pascal. Es éste una disposición triángular (como no podía ser de otro modo) de números, cuyos lados derecho e izquierdo son todos números 1 y donde cada número es la suma de los dos inmediatamente superiores, como se muestra en el dibujo.
El Triángulo de Pascal tiene muchísimas propiedades interesantes (pero eso para otro post). Para lo que ahora tenemos entre manos sólo nos interesa reconocer qué números son pares y cuáles impares. Para ello ni siquiera es necesario saber qué números tenemos que colocar en cada casilla. Basta con saber que la suma de dos números impares o dos números pares siempre da un número par y que la suma de un número impar con uno par (y al revés, lógicamente) es siempre impar. Así, podemos pintar los números pares de nuestro triángulo de color blanco y los impares de negro. Entonces comenzamos pintando los laterales (que sabemos que valen 1) de negro. Luego sólo tenemos que colorear con cuidado de no equivocarnos (y si somos niños pequeños de no salirnos). El resultado es el siguiente (desde luego, esto sólo es una parte del triángulo, que se supone que puede tener infinitas filas):
Se parece al ya conocido triángulo de Sierpinski, ¿no? Si quieres que el parecido sea mayor sólo tienes que tirar a la basura la distribución triangular estándar del Triángulo de Pascal y cambiarla por un triángulo equilátero diseccionado en múltiples triángulos equiláteros de igual tamaño (como hacíamos para la generalización del triángulo de Sierpinski). Luego sólo tenemos en cuenta los triángulos que están “boca arriba”, es decir, solamente esos triángulos se corresponderán con las casillas del Triángulo de Pascal convencional; a los otros los ignoramos. Prueba a pintar ahora y dime si no te parecen gemelos gemelos (clones, diría yo).
Mas… ¿más? Sí, hay más. No creas que lo que te comenté antes del Triángulo de Sierpinski era sólo porque me apetecía. La ventaja del parecido de los dos triángulos es que nos permite transformar un problema difícil de resolver en el mundo de Pascal en uno más sencillo en el de Sierpinski… Por todos es sabido que si escogemos un número natural al azar, la probabilidad de que sea par (o impar, si lo prefieres) es de ½. Puede parecerle a nuestra intuición que lo mismo sucede en un Triángulo “pascaliano”, pero ahí está nuestra parte más racional para pararle las alas. Cogemos de nuevo nuestro triángulo blanco-negreado y nos percatamos de que la parte blanca se corresponde con los números pares y con los triángulos que vamos quitando del “Triángulo Sierpinskiano” y la parte negra… (dejo al lector que complete la oración). Así, la probabilidad de obtener al azar un número impar se corresponde más o menos con el área del Triángulo de Sierpinski, que ya vimos más arriba (esto será más fiable cuanto más filas cojamos del Triángulo de Pascal, es decir, cuanto más filas cojamos, más cerca estaremos de la probabilidad cero de obtener un número impar).
Aún nos queda otra idea curiosa, aunque aquí nos tenemos que meter en otro paraje matemático: la aritmética modular… No, no te preocupes, no voy a hablar con tecnicismos… Hemos coloreado el Triángulo de Pascal atendiendo a los números pares e impares o, lo que es lo mismo, atendiendo a si el número deja resto 0 ó 1 al dividirlo entre dos (lógicamente, estos son los dos únicos restos posibles). Pues bien, ¿por qué no generalizar? Por ejemplo, podemos pintar, al igual que antes, de blanco cada casilla cuyo número deje resto 0 al dividirlo por 3 (donde pongo 3, pongamos también k) y de negro el resto de los restos. ¿Qué ocurre ahora? Sí, lo has adivinado, obtenemos unos triángulos bastante parecidos a los triángulos generalizados del Triángulo de Sierpinski, sobre todo cuando k es un número primo. ¡Y no sólo eso! ¡Las “ks” se corresponden, es decir, un Triángulo fractal generalizado k (con k divisiones iguales del lado) se parece mucho al Triángulo de Pascal coloreado para un k determinado.
Y ahora sólo queda que tú te pongas en acción y empieces a buscar variantes, por ejemplo:
-
Modificando la regla para colorear: colorear de negro solamente las casillas que dejan resto 1. Colorear cada resto de un color diferente…
-
Modificar el Triángulo de Pascal: construir un “Triángulo de Pascal” en el que cada número sea la diferencia de los dos de arriba o la suma del de la izquierda y del doble del de la derecha…
Sierpinski y Hanoi
La Torre de Hanoi es un juego inventado por Édouard Lucas. Si aún no lo conoces te recomiendo que visites esta página, en la que también podrás encontrar varios algoritmos de resolución y el enlace a simuladores disponibles en Internet. Me gustaría citar aquí de esa misma página la leyenda que este juego trae consigo (leyenda también inventada por Lucas):
Según una leyenda india, en el Templo de Benarés, bajo el domo que marca el centro del mundo, hay una placa de latón con tres agujas de diamante. Durante la creación, Dios puso sesenta y cuatro discos de oro puro de distinto tamaño en una de las agujas, formando una torre. Los bramanes llevan generaciones cambiando de lugar, uno a uno, los discos de la torre entre las tres agujas de forma que en ningún momento un disco mayor descanse sobre otro más pequeño. Cuando hayan conseguido trasladar todos los discos a otra aguja su trabajo estará terminado, y la torre y el templo se derrumbarán, y con un gran trueno, el mundo se desvanecerá.
Puede parecer que esta tarea no requeriría mucho tiempo, sin embargo, unos pocos cálculos (que no vamos a hacer aquí, pero que puedes visitar en la página ya varias veces mencionada) nos llevan a la conclusión de que para una Torre de n discos se necesitan, al menos, 2n -1 movimientos, lo que en el caso de 64 discos se convierte en:
[…] 18.446.744.073.709.551.615. Si los bramanes de Benarés cambiaran un disco de sitio cada segundo necesitarían más de quinientos ochenta mil millones de años para terminar su tarea, unas cuarenta veces la edad del Universo.
El lector observador se habrá dado cuenta de que “al menos” lo he puesto con negrita. Esto se debe a que ese es el número mínimo de movimientos pero, ¿quién dice que no podamos hacer más movimientos? Es más, cabe preguntarse, ¿habrá alguna manera de conseguir pasar del estado inicial al final pasando por todos los estados intermedios y sin repetir ninguno? Sí, sí que la hay, pero para hallarla vamos a necesitar crear un grafo que llamaremos grafo de Hanoi. Los vértices de este grafo lo forman los estados (por si no queda claro, un estado es una disposición válida de los diferentes discos en la Torre) y los lados unen aquellos estados que estén separados por un único movimiento. Cada estado queda definido por el poste en el que está cada disco, llamando a los discos 1, 2 y 3 empezando de izquierda a derecha y formando un número de n cifras (donde n se refiere al número de discos que hay) de tal manera que las unidades indican el poste donde se encuentra el disco más pequeño, las decenas el disco que le sigue en tamaño al pequeño… y así sucesivamente. Por ejemplo, para una Torre de Hanoi de tres discos, el número 221 indica que tanto el disco grande como el mediano se encuentran en el poste 2 (hay que fijarse que sólo hay una manera de colocarlos, porque el disco grande no puede ir encima del mediano) y el disco pequeño en el poste 1. No hay ningún disco en el poste 3. Además, esta notación nos permite calcular fácilmente el número de estados posibles, que es siempre de 3n (dejo al lector la tarea de ver por qué).
Bien, pues echa una ojeada a la figura de abajo para fijarte en la relación del grafo de Hanoi de orden 2 (representado en naranja) con el Triángulo de Sierpinski.
Lo bueno es que cada grafo de Hanoi de orden n se puede representar a través de tres grafos de Hanoi de orden n-1 conectados por tres líneas correspondientes a movimientos del disco más grande. Es eso precisamente lo que le da esa apariencia sierpinskiana. Así, los grafos de orden 3 (los dos primeros) y de orden 4 (el último) quedarían:
Pero no hemos respondido aún a la pregunta de qué movimientos hay que realizar para pasar por todos los estados. Invito al lector a que lo intente con los grafos que ya se han mostrado, es decir, tiene que crear un camino que pase por todos los vértices sin repetir ninguno. Luego puede buscar en esta página el grafo de orden 5 siguiente y pasar el cursor por encima para descubrir en morado el camino para dicho grafo.
Al lector todo esto le puede parecer meras curiosidades, sin embargo, esta sintonía existente entre el grafo de Hanoi y el Triángulo de Sierpinski ha ayudado a descubrir una característica de este último (al igual que antes ocurrió entre los dos triángulos, el de Sierpinski y el de Pascal): se trata del cálculo de la distancia promedio entre dos puntos cualesquiera del Triángulo cuyo lado mide 1, y que es de 466/885. No vamos a ver aquí cómo. Para una explicación algo más detallada te remito a este magnífico documento en formato pdf (página 7).
Y, para terminar, me gustaría decir que todo esto es una pequeña muestra de las relaciones insospechadas que muchas veces nos podemos encontrar dentro del paisaje matemático. Para mí es una de las razones de que los paseos por este paisaje me resulten tan gratos. Ya está. Para más información sobre todo esto te remito a las referencias que aparecen aquí debajo.
Referencias:
- Sierpinski y Pascal
BERNAL, O.: La conexión Sierpinski [pdf]
MORENO, J. C. (2003): Triángulos y tetraedros fractales [pdf]. Suma, nº 44, 13-24.
STEWART, I. (2007): Ingeniosos encuentros entre juegos y matemática. RBA. Biblioteca Desafíos Matemáticos.
- Sierpinski y Hanoi
BERNAL, O.: La conexión Sierpinski [pdf]
VALEIRAS, R.: La Torre de Hanoi y La Torre de Hanoi (continuación)
VALEIRAS, R; SANTOS, J (2006): Orden en el Caos. Almuzara.
Fuentes de las imágenes:
1.- http://topologia.wordpress.com/2008/12/19/el-conjunto-de-cantor-y-el-triangulo-de-sierpinski/
2.- http://www.revistasuma.es/index.php?option=com_docman&task=doc_download&gid=64&Itemid=33&mode=view
3.-http://www.disfrutalasmatematicas.com/triangulo-pascal.html
4.- http://www.revistasuma.es/index.php?option=com_docman&task=doc_download&gid=64&Itemid=33&mode=view
5.- http://ciencias.uniandes.edu.co/pdf/siespinski.pdf
6.- http://blog.tuwebdecursos.es/2008/02/20/ingenijuego-torres-de-hanoi/
7.- http://ciencias.uniandes.edu.co/pdf/siespinski.pdf
matemaTICs 
[…] escribí este post. Bien, pues el caso es que una mosca cojonera no paraba de molestarme en la mente. Esa mosca […]
Hola Sara, hay una aproximación xula-xula al tema y que se puede hacer con peques o medianos como yo en http://www.uam.es/otros/hojavol/hoja12/fractales12.html, gracias por tu artículo,
maki
Hola, maki.
Aunque conocía el artículo que me enlazas, te lo agradezco. Así, si algún lector o lectora se pasa por aquí y le apetece ponerse manos a la obra y contruirse un triángulo de Sierpinski de papel, no tiene nada más que pinchar en el enlace.
Salu2