| Artículos | 01 MAR 1997

Operaciones difíciles de concluir

Tags: Histórico
Eloy Anguiano.

Los problemas que voy a presentar hoy están relacionados con trabajos matemáticos de hace 15 ó 20 años emparentados con los teoremas de ordenación de conjuntos que se remontan a los trabajos sobre números ordinales transfinitos de Cantor. A su vez estos teoremas están íntimamente relacionados con un profundo teorema sobre los conjuntos infinitos de árboles físicos. Más recientemente N. Dershowitz y Z. Manna han utilizado razonamientos similares para demostrar que ciertos programas de ordenador donde aparecen un numero aparentemente ilimitado de operaciones deben forzosamente terminarse. Ejemplos de estos programas son los que usted, amigo lector, podrá programar para simular el comportamiento de cada uno de los problemas que aquí se van a describir.

El primero de estos problemas es el de la hidra de Hércules. Para ello es necesario que se plantee adecuadamente el problema. Partamos con una hidra que ya tiene múltiples cabezas como la de la figura adjunta, la primera vez que cortamos una cabeza, en el nudo inmediatamente inferior a aquel al que estaba unida la cabeza aparece un trozo de hidra idéntico al que queda en ese mismo nudo. En el siguiente corte sucede exactamente lo mismo salvo que en lugar de un trozo idéntico aparecen dos, en el tercer corte tres y así sucesivamente. En general, en el n-ésimo corte aparecen "n" nuevas copias. En la figura adjunta pueden verse los tres primeros cortes. Solo cuando no existe el nudo inmediatamente inferior al que esta unida la cabeza entonces no crece la cabeza.

Aparentemente ésta parece una tarea infinita. ¿Hércules nunca conseguirá acabar con la hidra? Pues tarde o temprano acabará con la hidra. L. Kirby y J. Paris demostraron en 1982 que, independientemente de la complejidad de la hidra, Hércules terminara por eliminarla puesto que según se dan mas cortes, aunque aparecen más, estas son cada vez de igual o menor extensión hasta que terminan partiendo todas de la base, estas pueden ser millones incluso para hidras de partida muy simples. En el momento en que a la hidra le quedan sólo cabezas de extensión 1 a Hércules le basta con irlas cortando de una en una hasta que todas desaparezcan.

Si usted realiza un programa para simular la hidra verá que, el programa, aparentemente no puede tener fin. Cuando lo ejecute verá como el número de cabezas crece muy rápidamente y, en un momento determinado, el número de cabezas empieza a decrecer de forma lenta pero casi constante hasta que la hidra desaparece.

El siguiente ejemplo es el denominado Solitario Búlgaro (tal vez le dieron el nombre los Rumanos). Este solitario esta basado en los números triangulares, es decir en los números que salen de las sucesivas sumas parciales de la serie 1+2+3+... y que forman la serie, 1, 3, 6, 10, 15, 21 ... . Estos números se llaman triangulares porque son el número de elementos sólidos idénticos necesarios para formar un triángulo. Como ejemplo las bolas del billar americano que son 15. Para este juego es necesario utilizar una baraja francesa y coger 45 cartas de entre las 52 totales. Se divide inicialmente estas en tantos montones como se quiera con el un número aleatorio de naipes en cada una. A partir de la situación vamos a repetir constantemente el mismo proceso, cogemos una carta de cada uno de los montones y formamos un nuevo montón. ¡Y ya está!, repitamos constantemente el proceso, ¿llegaremos a obtener una configuración triangular?. Como podrá comprobar, siempre, indefectíblemente llegaremos a una configuración con nueve montones y con una carta en uno de ellos, dos en otro, tres en otro y así sucesivamente disponiéndose en una configuración triangular. Curiosamente este sistema es válido para cualquier cantidad inicial de naipes siempre y cuando su número sea siempre un número triangular.

En el árbol adjunto se muestran todas las configuraciones iniciales posibles con 10 naipes. La evolución de estas configuraciones son los nudos que se encuentran unidos a ellas por debajo hasta llegar a la raíz del árbol que es la configuración final.

Hay una conjetura sobre el número de pasos máximo necesario para obtener la configuración inicial que dice que es k(k-1) donde el número total de naipes viene dado por k(k+1)/2. Esta conjetura está aún sin demostrar y por tanto le animo a que lo intente. Aunque grandes matemáticos le están dedicando mucho tiempo, algunas demostraciones de este estilo necesitan tan sólo una idea feliz.

Otro problema más es el de las bolas de lotería en la bolsa. Este problema es más sencillo de entender que los dos anteriores. Consiste en lo siguiente: tenemos dos bombos con bolas numeradas. En el primer bombo existe una cantidad infinita de bolas y los números de cada una pueden estar repetidos en tantas bolas como se desee. En el segundo bombo tenemos una cantidad finita de bolas en la misma situación. El proceso que se va a seguir es el siguiente: sacamos una bola del bombo finito, miramos su numero y la introducimos en el infinito, ahora podemos sacar tantas bolas como queramos del bombo infinito e introducirlas en el finito con la única condición de que todas las bolas que introduzcamos tengan un número menor que el de la bola que seleccionamos en la primera parte del proceso. La segunda parte del proceso tiene como excepción el que la bola elegida en la primera parte tenga como valor un uno. Como no hay bolas con un valor inferior entonces no se puede extraer ninguna bola del bombo infinito para introducirla en el finito. Se puede demostrar que no hay forma, por mucho que lo intentemos, de hacer esta tarea inacabable. Por fuerza ha de terminar.

La demostración de esta afirmación es sencilla si la hacemos por inducción. Si todas las bolas del bombo finito son unos solo es necesario irlas sacando una a una hasta acabar con ellas. Si hay doses por fuerza tendremos que sacar un dos cuando se nos acaben los unos y al sacar el dos solo podremos introducir unos. Esto sucederá para cada dos hasta que solo queden unos que es un caso ya resuelto. De igual forma, si hay treses, como hemos demostrado, se nos acabaran los doses y unos y deberemos sacar un tres y substituirlo por doses y unos. Esto sucederá hasta eliminar todos los treses. En esa situación sólo tendremos unos y doses que es un caso ya resuelto. Así sucesivamente hasta el número mayor que haya en el bombo finito. Esta tarea podrá ser todo lo larga que uno desee pero deberá terminar forzosamente.

Por supuesto, una de las cosas más interesantes que puede hacer con estos juegos es programarlos con un ordenador y ver sus resultados.

Bibliografía

- J. Kirby y J. Paris, The Bulletin of the London Mathematical Society, vol. 14, 4ª partem, nº 49, pp. 285-293, Julio 1982.

- E.R. Berlekamp y R.L. Graham, Journal of Number Theory, vol 2, nº 2, pp. 152-161, Mayo 1970.

- M. Warmus, Journal of Number Theory, vol 8, nº 3, pp. 260-263, Agosto 1976.

Eloy.Anguiano@ii.uam.es

Contenidos recomendados...

Comentar
Para comentar, es necesario iniciar sesión
Se muestran 0 comentarios
X

Uso de cookies

Esta web utiliza cookies técnicas, de personalización y análisis, propias y de terceros, para facilitarle la navegación de forma anónima y analizar estadísticas del uso de la web. Consideramos que si continúa navegando, acepta su uso. Obtener más información