Problema del ángel
El problema del ángel es un problema perteneciente a la Teoría de Juegos, propuesto por John Horton Conway 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 y Mathé y Kloster demostraron que un 2-ángel puede ganar.
El problema fue publicado por primera vez en 1982, en el libro Winning Ways (Maneras de ganar), por Berlekamp, Conway y Guy, bajo el nombre de "the angel and the square-eater" (el ángel y el comecasillas). En dos dimensiones, los primeros resultados parciales incluyeron:
En tres dimensiones, se demostró que:
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 (enlace roto disponible en Internet Archive; véase el historial, la primera versión y la última). 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 solo 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).
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.
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 solo 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 través 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 solo 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. Una demostración similar ha sido publicada por Martin Kutz.
Máthé 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.
Brian Bowditch define una variante (juego 2) del juego original con los siguientes cambios en las reglas:
Un camino tortuoso es un camino donde es un arco semi-infinito (un camino que no se corta a sí mismo, con punto inicial pero sin punto final) y son bucles disjuntos dos a dos con la siguiente propiedad:
(Hay que tener en cuenta que para que esté bien definida, debe comenzar y terminar en el punto final de , y debe terminar en el punto inicial de )
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.
