Pour cette semaine je propose un classique (je donnerais la référence après pour éviter la tentation :p)
Un roi se trouve sur un échiquier infini. Il se déplace comme le roi des échecs, cet à dire va aller à chaque pas de temps sur une des 8 cases directement voisines.
Un démon omniprésent peut à chaque pas de temps détruire définitivement une case de son choix à condition que le roi ne s'y trouve pas. (Bien sur le roi ne pourra pas aller ensuite sur une case précédemment détruite, et roi et démon jouent à tour de rôle.)
Le but du démon est de bloquer le roi, le but du roi est bien sur le contraire: pouvoir bouger indéfiniment.
Qui gagne? (+demo
)
Très gros indice(donc uniquement si nécessaire):
Spoiler : [Afficher le message] Le démon peut bloquer le roi
Solution:
Spoiler : [Afficher le message] Il s'agit du problème de l'ange et du démon de Conway. (google est votre ami)
Ici on dit que l'ange est de "puissance 1" car il à le droit à un mouvement entre chaque action du démon. (ie: puissance k veut dire, k mouvement entre chaque action du démon). Pour un ange de puissance 1 le démon gagne, ce résultat avait été trouvé rapidement je crois par Conway (et est trouvable par nous pauvres mortels pour peu qu'on réfléchisse un peu à la question^^). Pour des puissances supérieures la question étaient restée en suspens pendant des 10aines d'années on sait maintenant qu'à partir de la puissance 2 seulement l'ange gagne!
Pour notre problème (puissance 1 donc):
Ce que vous pouvez remarquer par tentative, c'est qu'il est assez facile d'empêcher le roi de dépasser une ligne imaginaire si vous la placez assez loin de lui. Et il se trouve que "assez loin" n'est pas si gros, simplement 5 cases de distances suffisent si ma mémoire est bonne. (suffit de tenter c'est assez intuitif sur ce point).
Ce qu'il faut remarquer ensuite c'est qu'on se retrouve bloqué par cette précédente méthode car une fois le roi collé à notre ligne imaginaire il va nous faire bosser à plein temps en la longeant et on aura aucun répits aucun coup d'avance gagnable.
Ce qu'il faut donc trouver c'est une astuce pour pouvoir le contenir dans un carré, une astuce qui nous permettrait de gagner des mouvements pour "tourner".
Comme on peut décider d'un carré arbitrairement grand on peut le choisir suffisamment grand pour avoir le temps de construire des charnières aux 4 coins avant que le roi n'arrive à une distance de 5 d'un bord. (Optimalement 3 coups sont suffisants dans un coin pour faire une charnière mais pour vous convaincre imaginez n'importe quel pâté compact ![smile](img/smilies/smile.png)
Ainsi donc une fois les charnières construite et avec la technique antidépassement de ligne sur les 4 bords le roi va se trouver enfermé dans une surface finie et finira par être bloqué.
Félicitation à Looping007 pour avoir trouvé la solution et une démo acceptable!