|
#1 - 07-08-2012 21:48:22
- Clydevil
- Expert de Prise2Tete
- Enigmes résolues : 29
- Messages : 914
- Lieu: Seahaven island
Dans la peau de Dédal
Bonjour!
Amis Dédales en herbe le moment de faire travailler vos méninges pour me construire un beau labyrinthe est arrivé! On se trouve dans le plan, en 2D donc, notre labyrinthe est constitué de salles carré unité. Si deux salles se touchent par un coté on peut passer de l'une à l'autre. Il n'y a pas de sortie c'est juste un beau labyrinthe dans lequel on peut se promener. Dans une salle se trouve le Jeune Icare, dans une autre salle se trouve le Minotaure. Pour changer, les deux ont une vision omnisciente du labyrinthe, chacun sachant à tout instant ou il se trouve et ou se trouve l'autre et connaissant par cœur la forme totale du labyrinthe. Nos deux compères se déplacent au tour par tour, Icare, puis le minotaure, puis Icare, puis le minotaure, etc... :p. A leur tour ils peuvent décider de ne pas bouger, ou d'aller dans une salle voisine. Si à un moment le minotaure se trouve dans la même salle qu'Icare, ce dernier se fait bouffer, même si c’était à lui de jouer ensuite.
Il est assez facile de concevoir un labyrinthe dans lequel avec les règles précédentes Icare peut éternellement échapper au minotaure. Une petite boucle de salle suffit:
En tournant toujours dans le même sens que le minotaure Icare est sauf.
Mais seriez vous capable de me construire un labyrinthe permettant à Icare de survivre éternellement lorsqu'il y a deux minotaures? Précisions: - Le placement initial des minotaures et d'Icare fait partie de la conception du labyrinthe. - Le minotaure1 joue, le minotaure2 joue, Icare joue, et on recommence. - Les minotaures peuvent parfaitement se trouver dans la même salle et donc se croiser. - Il faut évidemment pouvoir survivre quelle que soit la stratégie des minotaures (parce que si c'était des quiches évidemment la question n'aurait pas d’intérêt) Pour les hommes de peu de foi, ayant besoin de courage, voulant savoir si c'est au moins possible: Spoiler : [Afficher le message] Oui c'est possible.
Ajout d'un indice/aide: Spoiler : [Afficher le message] La contrainte des salles carrées est plus polluante qu'autre chose, il est plus facile de commencer par chercher un graphe (les joueurs se déplaçant sur les nœuds de celui ci, les mouvements autorisés étant symbolisés par les arêtes). Dans un second temps on peut adapter avec des salles carrées.
(Une image pour faire joli parce que c'est mieux les énigmes avec des images)
Bonne chance!
Solution: Spoiler : [Afficher le message] Voici quelques remarques autour de la question initiale (j'ai été inspiré), ainsi que la solution de l’énigme originelle. Il est assez commode au départ de ne pas se contraindre à utiliser des salles carrées unité mais à utiliser un objet mathématique beaucoup plus souple: les graphes. Rappel: Un graphe c'est juste un ensemble de nœuds, dont certaines paires sont reliées par des arrêtes. Un nœud symbolisera une salle, une arrête entre deux nœuds symbolisera un déplacement possible de l'un à l'autre. Un graphe est dit planaire lorsqu'on peut le dessiner sur une feuille sans se faire croiser des arrêtes.
A) Quelques remarques avec des graphes A.1) Sans se forcer à être planaire Le graphe de Petersen:
La figure est trompeuse, ce graphe est parfaitement symétrique, tous les nœuds jouent le même rôle, toutes les arrêtes également. C'est certainement le plus petit graphe dans lequel Icare pourrait échapper aux minotaures. Démonstration: Chaque nœud a 3 voisins qui ne sont pas voisins entre eux, ni par l’intermédiaire d'un seul autre nœud. Ainsi donc lorsqu'il est menacé Icare à toujours une échappatoire valide car inoccupée, non menacée.
Les graphes issue des sommets/arrêtes d'un tore à facette: Selon certaines conditions ils assurent également la survie d'Icare. C'est le cas par exemple du tore à 5 sections triangulaires, du tore à 3 sections pentagonales, du tore à 4 sections carrées (Validés par programme), et des tores strictement plus gros.
Les graphes des hyper-cubes: Rappel: pour construire le graphe d'un hyper-cube en dimension N à partir du graphe d'un hypercube en dimension N-1 vous clonez ce dernier, puis vous reliez chaque nœud à son clone. Ainsi donc la famille de ces graphes commence par: un seul nœud, un segment de 2 nœuds, un carré, un cube, etc... Un hyper-cube en dimension 3 c'est simplement un cube. Cette famille est intéressante car elle donne une solution quelque soit le nombre de minotaures! S'il y a k minotaures, Icare peut éternellement leur échapper sur un hyper-cube de dimension 2*k (Démontré. Même genre d'argument que pour Petersen) Le tesseract, (l'hyper-cybe de dimension 4) assure la survie d'Icare dans le cas deux minotaures.
A.2) Avec la contrainte planaire Le graphe du dodécaèdre (trouvé grâce à Moriss):
Le graphe issue des sommets/arrêtes du dodécaèdre est planaire. C'est certainement le plus petit graphe planaire dans lequel Icare pourrait échapper aux minotaures. Démonstration: Chaque nœud a 3 voisins qui ne sont pas voisins entre eux, ni par l’intermédiaire d'un seul autre nœud. Ainsi donc lorsqu'il est menacé Icare à toujours une échappatoire valide car inoccupée, non menacée.
Une famille de graphe à moi:
C'est celle qui m'a permis de trouver la solution de l'énigme originelle. Il s'agit de toute une famille de graphes qu'on peut obtenir en faisant varier certains paramètre de la figure ci dessus. Ça ressemble à une toile d’araignée, composé de 3 orbites. On peut changer, le nombre de secteurs K, le nombre de nœuds intermédiaires d'une orbite à l'autre J, ainsi que les nombres de nœuds intermédiaires S et L. Vous remarquerez que l'orbite interne et l'orbite externe joue le même rôle. Dans cette famille, Icare s'en sort lorsque les paramètres sont biens choisis, ma conjecture: K >= 5, L > S, J >= L-S assure la vie éternelle. Sur la figure à droite, le plus petit graphe de la famille qui assure longue vie à Icare (Validé par programme). Dans cette famille de graphes certains graphes se dessinent bien avec des salles carrées unité.
B) Version originelle de l'énigme avec des salles carrées unité. Il est moins dur qu'on ne croit de passer d'un graphe planaire à la version salle carrée. D'une part on dispose de la possibilité de transformer des arrêtes du graphe en une succession de K nœuds. A priori faire ceci sur chaque arrête avec le même K ne change pas ses propriétés pour Icare. On ne peut certes pas rallonger les distances mais on peut raccourcir en faisant des circonvolutions avec des chaînes de salles. Une solution avec des salles carrés unité (Validée par programme): (le graphe de ma famille de graphe avec les paramètres K=6 S=21 L=23 J=2.)
(image zoomable)
C) Validation par programme Avec un problème de ce genre on se demande bien ce qu'on peut faire comme validation par programme, qui ne prennent pas 3 ans et soit correcte. Étonnamment il y a un argument très abordable: Sur un graphe donné, pour une position donnée des minotaures on va appeler "death zone" l'ensemble des nœuds ou même si Icare joue le premier les minotaures peuvent finir par le capturer. (Si nos deux minotaures sont sur une chaîne de nœuds sans échappatoire, la death zone contient au moins les nœuds entre eux par exemple). A notre grande surprise il y a une relation récursive entres les death zones: La death zone d'une position des minotaures c'est l'union des death zones des positions voisines à laquelle on retire les nœuds qui touchent au moins un nœud qui ne soit pas dans cette union (on retire la surface), je vous laisse comprendre pourquoi, ce n'est pas si dur. Après il suffit d'initialiser les death zones aux couples de cases ou se trouve les minotaures, puis a appliquer la relation ci dessus entre toutes les death zones jusqu'à ce que plus rien n'évolue. Si après la death zone d'une position quelconque des minotaures est tout le graphe, alors toutes les death zone sont tout le graphe et le graphe ne convient pas pour faire survivre Icare, dans le cas contraire, rock-n-roll!
Le bouton spoileur pour afficher la solution est plus haut
#2 - 07-08-2012 23:37:15
- Moriss
- Professionnel de Prise2Tete
- Enigmes résolues : 37
- Messages : 460
Dans l apeau de Dédale
J'ai retourné le problème dans tous les sens, même en renonçant à n'utiliser que des carrés unité, et même en renonçant au carré, je ne trouve pas de solution (sauf en 3D évidemment). En effet, j'ai eu l'idée de faire un labyrinthe où toutes les cases sont reliées à au moins 3 cases non adjacentes (et non adjacentes elles-mêmes à une case en commun), ce qui ne semble pas possible dans le plan... Peut-être la position initiale des joueurs est-elle importante, mais j'en doute franchement.
Conclusion : faut-il démontrer l'impossibilité de la solution ? A moins que la solution de l'énigme soit de recourir à un plan non euclidien. Dans ce cas, un ballon de football pourrait servir de modèle...
Edit : si on accepte un labyrinthe infini, le plan euclidien fait tout aussi bien l'affaire.
#3 - 08-08-2012 14:12:18
- Clydevil
- Expert de Prise2Tete
- Enigmes résolues : 29
- Messages : 914
- Lieu: Seahaven island
dans la peau de sédale
@Moriss: J'ai répondu en PM pour ne pas tenter les spoilerivores.
#4 - 08-08-2012 17:43:34
- nodgim
- Elite de Prise2Tete
- Enigmes résolues : 0
- Messages : 3802
Dans al peau de Dédale
T'es sûr que c'est Icare dans le labyrinthe ? Je croyais que c'était Thésée.
#5 - 08-08-2012 17:49:29
- Clydevil
- Expert de Prise2Tete
- Enigmes résolues : 29
- Messages : 914
- Lieu: Seahaven island
Dans la peau dee Dédale
T'es sûr que c'est Icare dans le labyrinthe ? Je croyais que c'était Thésée.
L'un n’empêche pas l'autre. j'ai mis les liens wiki. Les deux y sont passés, pour différentes raisons.
#6 - 08-08-2012 18:16:35
- nodgim
- Elite de Prise2Tete
- Enigmes résolues : 0
- Messages : 3802
Dasn la peau de Dédale
C'est Thésée qui combat et tue Minotaure. Sinon, un simple réseau à 2 sommets et 3 branches devrait faire l'affaire: les sommets diagonalement opposés, 2 branches qui font le pourtour, la 3ème en diagonale (en escalier pour la même longueur que les 2 autres). Comme ce sont les M qui commencent, I adopte son comportement en conséquence, en empruntant la branche libre.
#7 - 09-08-2012 00:26:18
- Clydevil
- Expert de Prise2Tete
- Enigmes résolues : 29
- Messages : 914
- Lieu: Seahaven island
Daans la peau de Dédale
@Nodgim: Ce n'est évidemment pas aussi simple :p Avec ta proposition les minotaures n'auraient qu'à se positionner sur un sommet chacun puis à venir prendre en sandwich le pauvre Icare sur la branche ou il se trouverait.
#8 - 09-08-2012 08:55:06
- gwen27
- Elite de Prise2Tete
- Enigmes résolues : 49
- Messages : 5,985E+3
dans ma peau de dédale
Sur un plateau de trivial pursuit , ça me parait pas mal avec plus de 2 cases par côté.
#9 - 09-08-2012 09:59:26
- Clydevil
- Expert de Prise2Tete
- Enigmes résolues : 29
- Messages : 914
- Lieu: Seahaven island
Dasn la peau de Dédale
@gwen: Spoiler : [Afficher le message] A priori un premier minotaure va se placer au milieu d'un des rayons de ta structure et aura pour mission d’empêcher Icare de passer par la case centrale et de l’empêcher également de passer par la case à l'autre extrémité du rayon. L'autre minotaure va le rabattre, Icare ne pourra pas faire un tour (serait pris en sandwich sur le dernier morceau de la périphérie), ni emprunter un rayon ou il serait également pris en sandwich.
#10 - 09-08-2012 11:05:38
- gwen27
- Elite de Prise2Tete
- Enigmes résolues : 49
- Messages : 5,985E+3
fans la peau de dédale
Si j'acolle, 3 plateaux , il peut toujours courir, non ?...
#11 - 09-08-2012 11:26:36
- Clydevil
- Expert de Prise2Tete
- Enigmes résolues : 29
- Messages : 914
- Lieu: Seahaven island
Dans la epau de Dédale
Cool, première proposition pertinente! (Les autres dorment? Trop difficile pour vous? *smilley troll face*)
@Gwen27: Il y a de l’idée. Mais je maintiens qu'il se fait bouffer par les minotaures sur un tel plateau notre pauvre Icare
#12 - 09-08-2012 11:44:11
- rivas
- Elite de Prise2Tete
- Enigmes résolues : 48
- Messages : 1106
- Lieu: Jacou
#13 - 09-08-2012 12:28:46
- nodgim
- Elite de Prise2Tete
- Enigmes résolues : 0
- Messages : 3802
Dans a peau de Dédale
Oui j'ai vu, j'ai répondu sans faire d'essais, et il est clair que ça ne tient pas longtemps. J'en viens donc, après réflexion, à me dire qu'il n'y a pas de solutions....
#14 - 10-08-2012 18:53:12
- Clydevil
- Expert de Prise2Tete
- Enigmes résolues : 29
- Messages : 914
- Lieu: Seahaven island
Dans la epau de Dédale
Pour les hommes de peu de foi, ayant besoin de courage, voulant savoir si c'est au moins possible: Spoiler : [Afficher le message] Oui c'est possible.
#15 - 11-08-2012 07:52:04
- Franky1103
- Elite de Prise2Tete
- Enigmes résolues : 49
- Messages : 3221
- Lieu: Luxembourg
Dans la peau dde Dédale
Bonjour, J'ai essayé de m'inspirer d'un plateau "pacman" (avec son "passage secret" en 2D), mais je n'arrive pas à concrétiseer une réponse correcte. Bonne journée.
#16 - 11-08-2012 15:21:19
- Promath-
- Elite de Prise2Tete
- Enigmes résolues : 18
- Messages : 1416
- Lieu: Au fond de l'univers
Dans la peau de Déadle
Une feuille quadrillée infinie fait l'affaire?
J'ai trouvé! OOOOOOOOO OXX XOXXXO OXOOOOOXO OOOXXXOOO OXOOOOOXO OXX XOXXXO OOOOOOOOO Les 2 minotaures en bas à droite. Icare en haut à gauche J'ai essayé je pense que ça marche.
Un promath- actif dans un forum actif
#17 - 11-08-2012 16:14:59
- Clydevil
- Expert de Prise2Tete
- Enigmes résolues : 29
- Messages : 914
- Lieu: Seahaven island
Dans la peauu de Dédale
@promath: La remarque infinie: non mais bon quoi voila ça doit être nécessairement fini sinon c'est trivial :p La proposition: Très intéressante! mais ça ne marche pas pendant longtemps j'ai aussi cru que ce genre la marchait.
#18 - 12-08-2012 00:46:06
- elpafio
- Elite de Prise2Tete
- Enigmes résolues : 43
- Messages : 1015
Dans la peau de Ddale
Vais essayer de proposer ce labyrinthe-ci:
Spoiler : [Afficher le message] Spider-cochon essayant d'échapper aux quiches lorraines
Nota bene: je ne suis pas encore sûr que Piggy-babe puisse échapper à son triste sort dans ce labyrinthe, mais je poste quand même au cas où...
Edit:
Clydevil: Quiché le pauvre cochon!
Grouiiiiikkkkk!!!! C'est bien ce que je craignais... Vais chercher encore.
#19 - 12-08-2012 01:04:23
- Clydevil
- Expert de Prise2Tete
- Enigmes résolues : 29
- Messages : 914
- Lieu: Seahaven island
Dans l apeau de Dédale
@Elpafio: Quiché le pauvre cochon!
#20 - 12-08-2012 11:12:38
- elpafio
- Elite de Prise2Tete
- Enigmes résolues : 43
- Messages : 1015
DDans la peau de Dédale
Deuxième tentative: Cette fois, c'est Spoiler : [Afficher le message] Super-spider-cochon
Il espère s'en tirer en évitant de se faire prendre en sand'quich sur la partie extérieure du périphérique. Bonne chance à lui ! Mais je ne suis pas encore sûr qu'il parvienne à sauver ses jambons...
#21 - 12-08-2012 11:48:43
- Clydevil
- Expert de Prise2Tete
- Enigmes résolues : 29
- Messages : 914
- Lieu: Seahaven island
Dans la peaau de Dédale
@Elpafio: Super quiché le pauvre cochon! Spoiler : [Afficher le message] En passant par le centre une quiche peut toute seule le contenir dans 1/4 plateau, l'autre apporter la mort.
#22 - 12-08-2012 16:26:10
- Clydevil
- Expert de Prise2Tete
- Enigmes résolues : 29
- Messages : 914
- Lieu: Seahaven island
Dans la peau d Dédale
Ajout d'un indice/aide: Spoiler : [Afficher le message] La contrainte des salles carrées est plus polluante qu'autre chose, il est plus facile de commencer par chercher un graphe (les joueurs se déplaçant sur les nœuds de celui ci, les mouvements autorisés étant symbolisés par les arêtes). Dans un second temps on peut adapter avec des salles carrées.
#23 - 12-08-2012 19:09:00
- elpafio
- Elite de Prise2Tete
- Enigmes résolues : 43
- Messages : 1015
#24 - 12-08-2012 19:43:34
- Clydevil
- Expert de Prise2Tete
- Enigmes résolues : 29
- Messages : 914
- Lieu: Seahaven island
Dans la pau de Dédale
@Epalfio: Est ce réellement une condition suffisante? . Cherche bien et tu verras qu'assez facilement les quiches mangent encore le cochon sur ce dernier schéma (équivalent à un damier ou le bord de droite serait relié au bord de gauche)!
#25 - 13-08-2012 09:14:16
- Promath-
- Elite de Prise2Tete
- Enigmes résolues : 18
- Messages : 1416
- Lieu: Au fond de l'univers
Dan la peau de Dédale
J'ai trouvé le type de système. Maintenant, je vais essayer de le fabriquer vraiment.
Un promath- actif dans un forum actif
Mots clés des moteurs de recherche
|
|