Problema de l'àngel
El problema de l'àngel és un problema pertanyent a la Teoria de Jocs, propost per John Horton Conway[1] El joc se sol conéixer pel nom Àngels i Dimonis. El joc té dos jugadors, cridats l'àngel i el diable. Es juga sobre una tauler d'escacs infinit (o lo que és lo mateix, els punts d'una cuadrícula bidimensional). L'àngel té poder k (un número natural major o igual que 1), el qual és fixat ans que el joc comence. El tauler està inicialment buit, en l'àngel en l'orige. En cada tanda, l'àngel bota a una atra casella buida, la qual podria ser alcançada per un màxim de k moviments corresponents als del rei en escacs; és dir, la distància a partir de la casella inicial no és major que k en la norma infinit). El diable, en la seua tanda, pot bloquejar una casella qualsevol en la que no estiga l'àngel. L'àngel pot botar sobre caselles bloquejades, pero no pot terminar la seua tanda en elles. El diable guanya si l'àngel no pot moure's. L'àngel guanya si pot sobreviure indefinidament.
El problema de l'àngel consistix en: ¿Pot un àngel en poder suficientment alt guanyar?
Deu existir una estratègia guanyadora per a un dels jugadors. Si el diable pot forçar una victòria, llavors pot fer-ho en un número finito de moviments. Si el diable no pot forçar una victòria, llavors sempre hi ha un moviment que l'àngel pot fer per a evitar perdre, i una estratègia guanyadora per a ell seria triar sempre este moviment. A un nivell més abstracte, el "conjunt de guanys" (és dir, el conjunt de totes els jocs en els que l'àngel guanya) és un conjunt tancat (en la topología natural dels conjunts de tots els jocs), i se sap que estos jocs són determinats.
Conway va oferir una recompensa per una solució general a este problema (100 dólars per a una estratègia guanyadora en un àngel de poder suficientment alt, i 1000 dólars per a una demostració de que el diable pot guanyar qualsevol que siga el poder de l'àngel). Es va progressar primer en dimensions majors que 2, en algunes belles demostracions. A finals de 2006, el problema es va resoldre quan varen aparéixer demostracions independents, provant que un àngel pot guanyar. Bowditch va demostrar que un 4-àngel pot guanyar[2] i Mathé[3] i Kloster[4] varen demostrar que un 2-àngel pot guanyar.
Història
[editar | editar còdic]El problema va ser publicat per primera volta en 1982, en el llibre Winning Ways (Maneres de guanyar), per Berlekamp, Conway i Guy,[5] baixe el nom de "the angel and the square-eater" (l'àngel i el comecasillas). En dos dimensions, els primers resultats parcials varen incloure:
- Si l'àngel té poder 1, el diable té una estratègia guanyadora (Conway, 1982). (Segons Conway, este resultat és en realitat per Berlekamp.)
- Si l'àngel mai disminuïx la seua coordenada I, llavors el diable té una estratègia guanyadora (Conway, 1982).
- Si l'àngel sempre aumenta la seua distància des de l'orige, llavors el diable té una estratègia guanyadora (Conway, 1996).
En tres dimensions, es va demostrar que:
- Si l'àngel sempre aumenta la seua coordenada I, i el diable solament pot jugar en un pla, llavors l'àngel té una estratègia guanyadora.
- Si l'àngel sempre aumenta la seua coordenada I, i el diable solament pot jugar en dos plans, llavors l'àngel té una estratègia guanyadora.
- L'àngel té una estratègia guanyadora si té poder major o igual que 13.
- Si tenim un número infinit de diables, cada u d'ells jugant a distància d_1, llavors l'àngel encara pot guanyar sempre que tinga poder suficient. (Per "jugar a distància s'entén que al diable no se li permet jugar a esta distància de l'orige).
Per últim, en 2006, no molt despuix de la publicació del llibre de Peter Winkler Mathematical Puzles (Rompecabezas matemàtics), el qual va contribuir a la difusió del problema de l'àngel, varen sorgir quatre demostracions independents i casi simultànees de que l'àngel té una estratègia guanyadora en dos dimensions. La demostració
- Archivat el 17 de abril de 2007 archivat en Wayback Machine. de Brian Bowditch funciona per al 4-àngel, mentres que la demostració de Oddvar Kloster i la demostració
- Archivat el 3 de octubre de 2009 archivat en Wayback Machine. de András Mathé funcionen per al 2-àngel. La demostració
- Archivat el 4 de març de 2016 archivat en Wayback Machine. de Péter Gács solament funciona per a una constant molt major. Les demostracions de Bowditch i de Mathé han segut publicades en Combinatorics, Probability and Computing (Combinatoria, Provabilitat i Computació, editat per Béla Bollobás i Imre Leader).
Atres qüestions sense resoldre
[editar | editar còdic]En 3 dimensions, suponent que l'àngel sempre aumenta la seua coordenada I, i que el diable està llimitat a tres plans, es desconeix si el diable té una estratègia guanyadora.
Vore també
[editar | editar còdic]- El Joc del chofer homicida, un atre joc matemàtic que enfronta a un adversari poderós i àgil contra un enemic en molts recursos pero menys poderós.
Referències
[editar | editar còdic]- ↑ [0] ^ John H. Conway, The angel problem, in: Richard Nowakowski (editor) Games of No Chance, volume 29 of MSRI Publications, pages 3–12, 1996.
- ↑ [1] ^ Brian H. Bowditch, The angel game in the plane, Combin. Probab. Comput. 16 (3) :345-362, 2007.
- ↑ [2] ^ András Máthé, The angel of power 2 wins, Combin. Probab. Comput. 16 (3) :363-374, 2007
- ↑ [3] ^ O. Kloster, A solution to the angel problem. Theoretical Computer Science, vol. 389 (2007), no. 1-2, págs. 152-161
- ↑ [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.
Referències
[editar | editar còdic]
- Este artícul conté una traducció derivada de «Problema del ángel» de Wikipedia en castellà publicada baix la Llicència de documentació lliure de GNU i la Llicència Creative Commons Reconeiximent-CompartirIgual 4.0 Internacional.