Problème de l'ange
Cet article est une ébauche concernant les mathématiques et l’informatique.
Vous pouvez partager vos connaissances en l’améliorant (comment ?) selon les recommandations des projets correspondants.
Le problème de l'ange est un jeu mathématique conceptuel inventé par le mathématicien John H. Conway en 1982 dans le livre Winning Ways for your Mathematical Plays[1].
Sur un échiquier de taille supposée infinie, un diable tente de piéger un ange. À chaque coup, le diable élimine l'une des cases du plateau, puis l'ange doit sauter à une case quelconque non éliminée, distante de N cases au maximum, N étant un entier positif fixé au préalable (dénommé « pouvoir » de l'ange). L'ange pouvant « voler », les cases intermédiaires entre sa case de départ et sa case d'arrivée peuvent avoir déjà été éliminées ou non. Seule la distance entre ces deux cases est limitée par le pouvoir de l'ange.
L'objectif du diable est de piéger l'ange sur une « île » située à une distance d'au moins N cases de toute autre case non éliminée du plateau, empêchant ainsi l'ange de se déplacer.
On peut penser a priori que l'ange est beaucoup plus puissant que le diable, car il peut se déplacer tous azimuts sur un plateau de taille infinie, tandis que le diable ne peut éliminer qu'une case à la fois. Toutefois, le diable est lui-même très puissant puisqu'il peut éliminer des cases qui se trouvent à une grande distance de la position actuelle de l'ange et en quelque sorte « piéger le terrain » en prévision du passage de l'ange dans ces régions. Conway et ses collaborateurs avaient ainsi montré très vite qu'un ange de pouvoir 1 perd en moins de 150 coups, et qu'un ange de pouvoir arbitraire, mais qui n'a jamais le droit de reculer (d'aller vers le sud) de plus de 1000 cases, se fait finalement piéger.
La question principale que posait ce jeu a été finalement résolue en 2007 :
- l'ange peut-il échapper indéfiniment au diable, à condition que son pouvoir soit suffisant ?
La réponse est positive, dès que ce pouvoir est supérieur ou égal à 2 : une stratégie gagnante (pour l'ange), due à O. Kloster est décrite ici (en anglais) : [1], et peut être testée à l'adresse suivante : [2]
Références[modifier | modifier le code]
- (en) Elwyn Berlekamp, John Conway et Richard Guy, Winning Ways for your Mathematical Plays, vol. 2 : Games in Particular, New York, Academic Press, (ISBN 0-12-091152-3 et 0-12-091102-7), chap. 19 (« The King and the Consumer »), p. 607-634.
