ANGE PROBLÈME DE L'

Carte mentale

Élargissez votre recherche dans Universalis

Certains problèmes de jeux possèdent des énoncés si simples que ce sont de véritables problèmes de mathématiques pures. C'est le cas du « problème de l'ange » qui appartient à une catégorie d'énigmes inventée par David Silverman et Richard Epstein à la fin des années 1940. Ce problème a été résolu en 2006-2007 simultanément par quatre chercheurs : Oddvar Kloster d'Oslo en Norvège, András Máthé de Melbourne en Australie, Brian Bowditch de Southampton en Grande-Bretagne et Peter Gacs de Boston aux États-Unis. Ils ont proposé des solutions différentes et indépendantes, mais arrivent tous à la même conclusion : un ange de force 2, s'il se comporte intelligemment, ne se fera jamais coincer par un démon. Qu'est-ce que cela signifie ?

Un ange de force 1 est un pion qui se déplace sur un échiquier infini à cases carrées et qui à chaque fois qu'il doit jouer se comporte comme un roi du jeu d'échecs : il peut donc passer de la case où il est posé à n'importe laquelle des 8 cases voisines. Un ange de force N est un pion qui à chaque fois qu'il joue opère N fois comme un ange de force 1. Un ange de force 2 peut donc atteindre en un coup n'importe laquelle des 24 cases les plus proches situées autour de lui : 8 cases juste autour de lui, et 16 autres entourant ces 8 cases.

Le démon, quant à lui, dispose à chaque coup du pouvoir de détruire une case autre que celle où se trouve l'ange. Son but est de bloquer l'ange sur une case cernée par des cases détruites. Le but de l'ange est d'échapper au démon. Le problème de l'ange est donc le problème le plus élémentaire de poursuite sur un tableau qu'on puisse imaginer.

On sait qu'un ange de force 1 perdra toujours face à un démon intelligent, car celui-ci, en construisant une sorte de grand fossé assez loin de la position initiale de l'ange, trouvera le temps d'encercler ce dernier avant qu'il ait pu s'échapper. La méthode de jeu du démon n'est pas très compliquée, mais il faut quand même être attentif pour la découvrir. Le lecteur, en jouant contre un adversaire humain, comprendra au bout de quelques parties comment jouer s'il est le dé [...]


1  2  3  4  5
pour nos abonnés,
l’article se compose de 2 pages




Écrit par :

Classification

Pour citer l’article

Jean-Paul DELAHAYE, « ANGE PROBLÈME DE L' », Encyclopædia Universalis [en ligne], consulté le 12 décembre 2019. URL : http://www.universalis.fr/encyclopedie/probleme-de-l-ange/