Problema del ángel

Problema del ángel

Saltar a navegación, búsqueda

La región azul de puntos indica a dónde podría ir un ángel de poder 3.

El problema del ángel es un problema perteneciente a la Teoría de Juegos, propuesto por John Horton Conway.^[1] El juego se suele conocer por el nombre Ángeles y Demonios. El juego tiene dos jugadores, llamados el ángel y el diablo. Se juega sobre una tablero de ajedrez infinito (o lo que es lo mismo, los puntos de una cuadrícula bidimensional). El ángel tiene poder k (un número natural mayor o igual que 1), el cual es fijado antes de que el juego comience. El tablero está inicialmente vacío, con el ángel en el origen. En cada turno, el ángel salta a otra casilla vacía, la cual podría ser alcanzada por un máximo de k movimientos correspondientes a los del rey en ajedrez; es decir, la distancia a partir de la casilla inicial no es mayor que k con la norma infinito). El diablo, en su turno, puede bloquear una casilla cualquiera en la que no esté el ángel. El ángel puede saltar sobre casillas bloqueadas, pero no puede terminar su turno en ellas. El diablo gana si el ángel no puede moverse. El ángel gana si puede sobrevivir indefinidamente.

El problema del ángel consiste en: ¿Puede un ángel con poder suficientemente alto ganar?

Debe existir una estrategia ganadora para uno de los jugadores. Si el diablo puede forzar una victoria, entonces puede hacerlo en un número finito de movimientos. Si el diablo no puede forzar una victoria, entonces siempre hay un movimiento que el ángel puede hacer para evitar perder, y una estrategia ganadora para él sería escoger siempre este movimiento. A un nivel más abstracto, el "conjunto de ganancias" (es decir, el conjunto de todas los juegos en los que el ángel gana) es un conjunto cerrado (en la topología natural de los conjuntos de todos los juegos), y se sabe que estos juegos son determinados.

Conway ofreció una recompensa por una solución general a este problema (100 dólares para una estrategia ganadora con un ángel de poder suficientemente alto, y 1000 dólares para una demostración de que el diablo puede ganar cualquiera que sea el poder del ángel). Se progresó primero en dimensiones mayores que 2, con algunas bellas demostraciones. A finales de 2006, el problema se resolvió cuando aparecieron demostraciones independientes, probando que un ángel puede ganar. Bowditch demostró que un 4-ángel puede ganar^[2] y Mathé^[3] y Kloster^[4] demostraron que un 2-ángel puede ganar.

Historia

El problema fue publicado por primera vez en 1982, en el libro Winning Ways (Maneras de ganar), por Berlekamp, Conway y Guy,^[5] bajo el nombre de "the angel and the square-eater" (el ángel y el comecasillas). En dos dimensiones, los primeros resultados parciales incluyeron:

• Si el ángel tiene poder 1, el diablo tiene una estrategia ganadora (Conway, 1982). (Según Conway, este resultado es en realidad debido a Berlekamp.)
• Si el ángel nunca disminuye su coordenada Y, entonces el diablo tiene una estrategia ganadora (Conway, 1982).
• Si el ángel siempre aumenta su distancia desde el origen, entonces el diablo tiene una estrategia ganadora (Conway, 1996).

En tres dimensiones, se demostró que:

• Si el ángel siempre aumenta su coordenada Y, y el diablo sólo puede jugar en un plano, entonces el ángel tiene una estrategia ganadora.
• Si el ángel siempre aumenta su coordenada Y, y el diablo sólo puede jugar en dos planos, entonces el ángel tiene una estrategia ganadora.
• El ángel tiene una estrategia ganadora si tiene poder mayor o igual que 13.
• Si tenemos un número infinito de diablos, cada uno de ellos jugando a distancia d_1, entonces el ángel todavía puede ganar siempre que tenga poder suficiente. (Por "jugar a distancia d se entiende que al diablo no se le permite jugar a esta distancia del origen).

Por último, en 2006, no mucho después de la publicación del libro de Peter Winkler Mathematical Puzzles (Rompecabezas matemáticos), el cual contribuyó a la difusión del problema del ángel, surgieron cuatro demostraciones independientes y casi simultáneas de que el ángel tiene una estrategia ganadora en dos dimensiones. La demostración de Brian Bowditch funciona para el 4-ángel, mientras que la demostración de Oddvar Kloster y la demostración de András Mathé funcionan para el 2-ángel. La demostración de Péter Gács sólo funciona para una constante mucho mayor. Las demostraciones de Bowditch y de Mathé han sido publicadas en Combinatorics, Probability and Computing (Combinatoria, Probabilidad y Computación, editado por Béla Bollobás e Imre Leader).

Otras cuestiones sin resolver

En 3 dimensiones, suponiendo que el ángel siempre aumenta su coordenada Y, y que el diablo está limitado a tres planos, se desconoce si el diablo tiene una estrategia ganadora.

Esbozo de la demostración de que, en 3 dimensiones, un ángel de poder alto tiene una estrategia ganadora

La demostración hace uso de guardianes. Para cada cubo de cualquier tamaño, hay un guardián que lo vigila. Los guardianes deciden en cada movimiento si el cubo que están vigilando es inseguro, seguro, o casi seguro. Esta decisión se basa únicamente en la densidad de puntos bloqueados en ese cubo y en el tamaño del cubo.

Si al ángel no se le dan órdenes, entonces sólo se mueve hacia arriba. Si algunos cubos en los que el ángel se encuentra dejan de ser seguros, entonces el guardián del mayor de estos cubos se encarga de que el ángel abandone el cubo a traves de un borde.

Si un guardián se encarga de escoltar al ángel fuera de su cubo a través de una cara, el tutor conduce al ángel a la cara por un camino hecho de subcubos seguros. Los guardianes de estos cubos se encargan de escoltar al ángel a través de sus respectivos subcubos.

Puede ser demostrado que la estrategia funciona porque el tiempo que el diablo necesita para convertir un cubo seguro en el camino del ángel en un cubo inseguro es mayor que el tiempo que tarda el ángel en llegar al cubo.

Las definiciones de "seguro" y "casi seguro" tienen que ser elegidos para que esto funcione.

Nota: El camino del ángel en un subcubo dado no se determina hasta que el ángel llega al cubo. Incluso entonces, el camino sólo se determina aproximadamente. Esto garantiza que el diablo no puede elegir un lugar en el camino lo suficiente alejado y bloquearlo.

Esta demostración es de Imre Líder y Béla Bollobás.^[6] Una demostración similar ha sido publicada por Martin Kutz.^[7]

Esbozo de la demostración de Máthé (para el 2-ángel)

Máthé^[3] define el diablo bueno, que nunca destruye una casilla que el ángel pudiera haber elegido ocupar en un turno anterior. Cuando el ángel juega contra el diablo bueno, admite la derrota si el diablo logra confinarlo a una región finita del tablero (de otro modo el ángel podría alternar entre dos casillas y no perder nunca). La demostración de Máthé se divide en dos partes: (1) demuestra que, si el ángel gana contra el diablo bueno, entonces el ángel gana contra el verdadero diablo; (2) da una estrategia ganadora explícita para el ángel contra el diablo bueno.

En términos generales, en la parte (2), el ángel gana contra el diablo bueno pretendiendo que todo el semiplano izquierdo está destruido (además de las casillas destruidas por el diablo bueno), y tratando a las casillas destruidas como las paredes de un laberinto, del cual sale por medio de la técnica de la mano en la pared. Es decir, el ángel mantiene su mano izquierda en contacto con la pared del laberinto y se mueve a lo largo de la pared. Entonces se puede demostrar que el diablo bueno no puede atrapar a un ángel que adopte esta estrategia.

La demostración de la parte (1) es por reducción al absurdo y, por tanto, no proporciona ninguna estrategia ganadora explícita contra el verdadero diablo. Sin embargo, Máthé hace notar que su demostración podría, en principio, ser adaptada para dar una estrategia explícita.

Esbozo de la demostración de Bowditch (4-angel)

Brian Bowditch define^[2] una variante (juego 2) del juego original con los siguientes cambios en las reglas:

1. El ángel puede regresar a cualquier casilla en la que ya haya estado, incluso aunque el diablo después intente bloquearla.
2. Un k-diablo debe visitar una casilla k veces antes de que sea bloqueada.
3. El ángel se mueve arriba, abajo, a la izquierda o a la derecha de una casilla en una (duke move).
4. Para ganar, el ángel debe trazar un camino tortuoso (definido a continuación).

Un camino tortuoso es un camino $\pi = \cup^{\infty}_{i=1} (\sigma_i \cup \gamma_i)$ donde $\sigma = \cup^{\infty}_{i=1} \sigma_i$ es un arco semi-infinito (un camino que no se corta a sí mismo, con punto incial pero sin punto final) y γ_i son bucles disjuntos dos a dos con la siguiente propiedad:

• $\forall i: |\gamma_i|\leq i$ donde | γ_i | es la longitud del i-ésimo bucle.

(Hay que tener en cuenta que para que γ_i esté bien definida, debe comenzar y terminar en el punto final de σ_i, y σ_i debe terminar en el punto inicial de σ_{i + 1})

Bowditch considera una variante (juego 1) del juego con los cambios 2 y 3, con un 5-diablo. A continuación, muestra que una estrategia ganadora en este juego proporciona una estrategia ganadora en el juego original para un 4-ángel. A continuación pasa a demostrar que un ángel jugando contra un 5-diablo (juego 2) puede ganar mediante un algoritmo bastante simple.

Bowditch afirma que un 4-ángel puede ganar la versión original del juego imaginando que un ángel-fantasma juega contra un 5-diablo en el juego 2.

El ángel sigue el camino el fantasma tomaría, pero evitando los bucles. Por lo tanto, como el camino σ es arco semi-infinito, el ángel no vuelve a ninguna casilla en la que ya ha estado, y por tanto el camino es un camino ganador incluso en el juego original.

Véase también

• El problema del conductor homicida, otro juego matemático que enfrenta a un adversario poderoso y ágil contra un enemigo con muchos recursos pero menos poderoso.

Referencias

1. ↑ [0] ^ John H. Conway, The angel problem, in: Richard Nowakowski (editor) Games of No Chance, volume 29 of MSRI Publications, pages 3–12, 1996.
2. ↑ ^{a b} [1] ^ Brian H. Bowditch, The angel game in the plane, Combin. Probab. Comput. 16 (3) :345-362, 2007.
3. ↑ ^{a b} [2] ^ András Máthé, The angel of power 2 wins, Combin. Probab. Comput. 16 (3) :363-374, 2007
4. ↑ [3] ^ O. Kloster, A solution to the angel problem. Theoretical Computer Science, vol. 389 (2007), no. 1-2, págs. 152-161
5. ↑ [4] ^ Elwyn R. Berlekamp, John H. Conway, and Richard K. Guy, Winning Ways for your mathematical plays, volume 2: Games in Particular, Academic Press, 1982.
6. ↑ [5] ^ B. Bollobás and I. Leader, The angel and the devil in three dimensions. Journal of Combinatorial Theory. Serie A. vol. 113 (2006), no. 1, págs. 176-184
7. ↑ [7] ^ Martin Kutz, The Angel Problem, Positional Games, and Digraph Roots, PhD Thesis FU Berlin, 2004

Enlaces externos

• El problema del ángel por John H. Conway
• Kloster's Angel Problem site

Obtenido de "Problema del %C3%A1ngel"