Enigmes

Forum dédié aux énigmes et à toutes formes de jeux de logique.

Déconnexion

Tu n'es pas identifié sur Prise2tete : s'identifier.

accueil Accueil forum Forum
[+]

 #1 - 11-04-2011 15:55:59

Clydevil
Expert de Prise2Tete
Enigmes résolues : 29
Messages : 808
Lieu: Seahaven island

rpi et 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 tongue)

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
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!



Annonces sponsorisées :
  • |
  • Répondre

#0 Pub

 #2 - 11-04-2011 17:24:14

Nombrilist
Expert de Prise2Tete
Enigmes résolues : 10
Messages : 562

Roi et démo.

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 : 4734

roi et démob.

C'est le fameux problème de l'ange de puissance 1 de Conway : le roi perd yikes

Vasimolo

 #4 - 11-04-2011 21:05:35

halloduda
Professionnel de Prise2Tete
Enigmes résolues : 24
Messages : 479
Lieu: Ardèche

RRoi 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,472E+3

rou et 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 : 808
Lieu: Seahaven island

Roi et ddé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 tongue. 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 : 1988
Lieu: Paris

Roi et édmon.

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 : 639

Rooi et 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 smile

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 smile

 #9 - 13-04-2011 17:28:23

Clydevil
Expert de Prise2Tete
Enigmes résolues : 29
Messages : 808
Lieu: Seahaven island

Roi et démoon.

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

Roi et démmon.

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 : 1988
Lieu: Paris

Roi et émon.

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 smile

 #12 - 14-04-2011 00:06:04

Clydevil
Expert de Prise2Tete
Enigmes résolues : 29
Messages : 808
Lieu: Seahaven island

Ri 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

roo et démon.

Je n'ai pas bon ! viens faire un tour sur mon goban, on verra comment ton roi s'en sort lol


http://enigmusique.blogspot.com/

 #14 - 14-04-2011 17:14:22

Clydevil
Expert de Prise2Tete
Enigmes résolues : 29
Messages : 808
Lieu: Seahaven island

Roi et démonn.

@Kosmogol: méfie toi je suis pas mauvais au go tongue.   C'est surtout pas une preuve! simplement un sentiment et il me semble pas correct en plus.  tongue

 #15 - 15-04-2011 21:46:57

Kikuchi
Passionné de Prise2Tete
Enigmes résolues : 46
Messages : 91

Roi et démo.

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 e démon.

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 lollol


eki eki eki pa tang!!

 #17 - 16-04-2011 16:48:20

Clydevil
Expert de Prise2Tete
Enigmes résolues : 29
Messages : 808
Lieu: Seahaven island

Ro et démon.

@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 : 808
Lieu: Seahaven island

Roi ett 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 smile
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!

 

Réponse rapide

Rédige ton message
| | | | Upload | Aide
:) :| :( :D :o ;) :/ :P :lol: :mad: :rolleyes: :cool:
Sécurité

Répondez (numériquement) à la petite énigme suivante : 

Dans une course, vous doublez le 42ème, en quelle position êtes-vous ?

Sujets similaires

Pied de page des forums

P2T basé sur PunBB
Screenshots par Robothumb

© Copyright 2002–2005 Rickard Andersson

Prise2Tete Forum Statistiques Liste des membres Hall of Fame Contact
© Prise2tete - Site d'énigmes et de réflexion.
Un jeu où seules la réflexion, la logique et la déduction permettent de trouver la solution.

Flux RSS de Prise2Tete Forum Jeux & Prise2Tete Test & Prise2Tete Partenariat et Publicité sur Prise2Tete