 |
#1 - 11-04-2011 15:55:59
- Clydevil
- Expert de Prise2Tete
- Enigmes résolues : 29
- Messages : 914
- Lieu: Seahaven island
roi zt démon.
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 
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!
#2 - 11-04-2011 17:24:14
- Nombrilist
- Expert de Prise2Tete
- Enigmes résolues : 10
- Messages : 568
roi et démpn.
Je dirais le roi, mais sans pouvoir le démontrer. Ou alors la stratégie du démon est très complexe.
#3 - 11-04-2011 17:32:52
- Vasimolo
- Le pâtissier
- Enigmes résolues : 49
- Messages : 5,397E+3
eoi et démon.
C'est le fameux problème de l'ange de puissance 1 de Conway : le roi perd 
Vasimolo
#4 - 11-04-2011 21:05:35
- halloduda
- Professionnel de Prise2Tete
- Enigmes résolues : 24
- Messages : 495
- Lieu: Ardèche
roo et démon.
C'est le "problème de l'ange et du démon" de Conway, "Ange and Devil".
Google donne de nombreuses références, dont celle-ci :
http://fr.wikipedia.org/wiki/Probl%C3%A8me_de_l%27ange
dans laquelle il est affirmé que le démon a une stratégie gagnante en 150 coups,
et esquissé le principe de la stratégie du démon, illustrée ici :
http://www.mpi-inf.mpg.de/~mkutz/slides … g_talk.pdf
Ces documents ne sont pas très faciles à lire.
Si j'ai bien compris,
le démon commence à construire une (assez) grande boîte en pointillés centrée sur le roi. Il commence par quatre points au Nord, Est, Sud, Ouest.
Si le roi s' approche d'un bord de la boîte, le démon augmente la densité du pointillé dans cette zone et n'a plus autant à s'occuper des parties lointaines.
Le processus converge et le roi finit par se faire enfermer.
Le démon n'a plus qu'à terminer le travail...
#5 - 11-04-2011 22:10:22
- gwen27
- Elite de Prise2Tete
- Enigmes résolues : 49
- Messages : 5,906E+3
Ro iet démon.
Le problème de l'ange de Conway... Bon ,au bout de 30 ans il est résolu et je ne comprends pas la solution.
J'ai du mal à résoudre les en 2 coups parfois alors 150 !!! Je ne suis pas à la hauteur.
#6 - 12-04-2011 09:17:30
- Clydevil
- Expert de Prise2Tete
- Enigmes résolues : 29
- Messages : 914
- Lieu: Seahaven island
Roi et démon
@halloduda:
Spoiler : [Afficher le message] Oui c'est bien le probleme de l'ange et du démon mais non pour la réponse tu as mal lu ^^
Pour les autres:
Le problème général auquel vous faite référence est dur, mais la question que je pose n'est pas "impossible" à trouver, ce n'est pas cette question qui a mis du temps à être résolue. Je ne suis pas sadique je ne vous donnerais pas d'énigme infaisable . Avec un peu de méthodologie et d'empirisme on peut trouver.
#7 - 12-04-2011 12:03:57
- L00ping007
- Elite de Prise2Tete
- Enigmes résolues : 49
- Messages : 2010
- Lieu: Paris
oRi et démon.
J'aurais tendance à dire que c'est le roi qui gagne, grâce aux mouvements diagonaux il trouvera toujours un moyen de passer à temps de l'autre côté d'un éventuel blocage du démon.
Mais c'est intuitif seulement !
#8 - 13-04-2011 17:21:18
- godisdead
- Expert de Prise2Tete
- Enigmes résolues : 22
- Messages : 747
Roi te démon.
Le roi gagne !
Pourquoi ? j'ai une chance sur 2 de trouver la bonne réponse, je pense que une bonne justification pour tenter ma chance
Plus sérieusement, j'ai essayé de trouver une tactique pour faire gagner le démon et comme je n'ai pas trouvé, soit je suis un mauvais démon, soit je suis un très bon roi
#9 - 13-04-2011 17:28:23
- Clydevil
- Expert de Prise2Tete
- Enigmes résolues : 29
- Messages : 914
- Lieu: Seahaven island
Ro iet démon.
Très gros indice(donc uniquement si nécessaire):
Spoiler : [Afficher le message] Le démon a une strategie qui bloque le roi dans tous les cas
#10 - 13-04-2011 17:42:39
- kosmogol
- Banni
- Enigmes résolues : 49
- Messages : 11,928E+3
oRi et démon.
en se déplaçant en keima, cela semble suffisant pour bloquer le roi.
http://enigmusique.blogspot.com/
#11 - 13-04-2011 19:26:39
- L00ping007
- Elite de Prise2Tete
- Enigmes résolues : 49
- Messages : 2010
- Lieu: Paris
Roi et démmon.
Bon mon intuition était complètement foireuse, le démon peut stopper le roi.
Il suffit pour cela de le bloquer dans un très grand carré centré sur le roi, dont il va en premier détruire les cases des coins. Puis selon la direction prise par le roi, il le bloquera sur le côté du carré vers lequel il se dirige.
Voici la forme des cases détruites aux coins, le roi étant le point au centre :
________
_| |_
| |
| |
| . |
| |
|_ _|
|________|
La dimensions des 4 renfoncements peut être prise égale à 5. En effet, si le roi s'approche à 5 cases d'un côté, on a toujours moyen de placer une barrière sur le côté du carré qui empêchera le roi de franchir ce côté.
Il faut donc 36 coups pour détruire les cases des renfoncements. Il faut donc choisir de les placer assez loin du roi pour que pendant ces 36 coups il soit toujours à au moins 5 cases d'un côté.
Une fois le roi bloqué dans le carré, il reste un nombre fini de cases à détruire, et le roi sera forcément bloqué.
J'ai lu un peu le début des démos dans le cas d'un ange qui peut se déplacer de 2, voire k cases, ça a pas l'air simple du tout, et je comprends que le problème soit resté non résolu pendant un moment
#12 - 14-04-2011 00:06:04
- Clydevil
- Expert de Prise2Tete
- Enigmes résolues : 29
- Messages : 914
- Lieu: Seahaven island
oi et démon.
Bravo à looping pour cette première solution valide!
#13 - 14-04-2011 01:42:05
- kosmogol
- Banni
- Enigmes résolues : 49
- Messages : 11,928E+3
Rooi et démon.
Je n'ai pas bon ! viens faire un tour sur mon goban, on verra comment ton roi s'en sort 
http://enigmusique.blogspot.com/
#14 - 14-04-2011 17:14:22
- Clydevil
- Expert de Prise2Tete
- Enigmes résolues : 29
- Messages : 914
- Lieu: Seahaven island
roo et démon.
@Kosmogol: méfie toi je suis pas mauvais au go . C'est surtout pas une preuve! simplement un sentiment et il me semble pas correct en plus.
#15 - 15-04-2011 21:46:57
- Kikuchi
- Passionné de Prise2Tete
- Enigmes résolues : 46
- Messages : 91
rou et démon.
Si le démon prend la position initiale du roi comme centre d'un cercle de rayon suffisamment grand, il suffit au démon de détruire la case appartenant au cercle vers laquelle le roi se dirige. Si cette case est déjà détruite, il détruira alors la case (non détruite appartenant au cercle) la plus proche de celle vers laquelle se dirige le roi.
C'est une solution "à l'instinct", je suis bien incapable d'apporter le moindre début de preuve mathématiques et encore moins de calculer quel pourrait être ce fameux rayon.
There's no scientific consensus that life is important
#16 - 16-04-2011 15:48:59
- clementmarmet
- Elite de Prise2Tete
- Enigmes résolues : 34
- Messages : 1329
- Lieu: I'm in spaaaace!!
Roi et démoon.
quand le roi prend une direction, il faut détruire la case qu'il utiliserait s'il allait dans la même direction au coup suivant: à force de contourner, le roi formerait tout seul un cercle dans lequel il serait enfermé...
MOUHAHAHAH
eki eki eki pa tang!!
#17 - 16-04-2011 16:48:20
- Clydevil
- Expert de Prise2Tete
- Enigmes résolues : 29
- Messages : 914
- Lieu: Seahaven island
Roi et démn.
@clementmarmet:
Spoiler : [Afficher le message]
Tente ta méthode sur un échiquier ou n'importe quel support suffisant, tu verras que tu ne formera certainement qu'une ligne et que ton roi se déplacera indéfiniment!
#18 - 16-04-2011 17:07:20
- Clydevil
- Expert de Prise2Tete
- Enigmes résolues : 29
- Messages : 914
- Lieu: Seahaven island
Rio et démon.
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
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!
Mots clés des moteurs de recherche
|
 |
Accueil
