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 - 29-05-2012 00:10:42

Vasimolo
Le pâtissier
Enigmes résolues : 49
Messages : 4734

ecjecs 11

Bonsoir à tous smile

Un petit problème pour se détendre ( les non-matheux peuvent y aller sans crainte ) .

On a disposé des robots sur les cases d'un échiquier transformé en labyrinthe . Les robots peuvent se déplacer d'une case vers une case voisine ( partageant un côté ) à condition de ne pas traverser une cloison !!!

Les robots doivent être rangés dans leur hangar ( en gris sur le dessin ) . Au départ chaque robot était animé par sa propre télécommande HBGD qui pouvait le ramener à sa niche de case en case  . Mais il ne reste plus qu'une télécommande qui anime tous les robots en même temps .

Peut-on quand même ranger tous les robots ???

http://img515.imageshack.us/img515/1888/robotsi.jpg

Remarques :

1°) Plusieurs robots peuvent partager la même case .
2°) Un robot bloqué par un bord ou une cloison reste en place .
3°) L'illustration est juste un exemple .

Amusez-vous bien smile

Vasimolo

Petit classement pour ceux qui veulent minimiser le nombre de déplacements avec l'exemple proposé :

1°) Elpafio et ThomasLRG : 34
2°) Morris et The Finder : 35
3°) Gwen et Corsaire : 37
4°) Franky : 42



Annonces sponsorisées :
  • |
  • Répondre

#0 Pub

 #2 - 29-05-2012 10:34:23

MthS-MlndN
Hors d'u-Sage
Enigmes résolues : 49
Messages : 12,414E+3
Lieu: Rouen

Echecs 1

M'est avis que l'on peut toujours se débrouiller pour rassembler tous les robots sur une même case, typiquement (pour des raisons pratiques) un des coins de la grille, tant que le labyrinthe est "connexe", c'est-à-dire qu'il existe un chemin entre deux cases quelconques. Plus qu'à les bouger tous en même temps par la suite, et hop.

J'attends mon eureka (ou bien que tu donnes un indice sur une piste de preuve lol)


Podcasts Modern Zeuhl : http://radio-r2r.fr/?p=298

 #3 - 29-05-2012 15:49:29

w9Lyl6n
Professionnel de Prise2Tete
Enigmes résolues : 26
Messages : 220

rchecs 11

Bonjours,
Je suppose que quand un robot arrive au hangar il disparait et qu'il ne peut plus en sortir (sinon il pourrait y avoir des problèmes de superposition).
On suppose aussi qu'il existe toujours un chemin de la position initiale d'un robot au hangar.
Dans ce cas je vais donner une méthode pour ranger un robot:
On choisi un des robots au hasard, on choisie un chemin menant au hangar, on lui fait suivre ce chemin. Si à une étape il est bloqué par un autre robot, c'est que ce dernier est sur la position suivante du chemin, on échange alors alors le robots à mener à l’objectif avec celui qui bloque.
Par ce procédé, à chaque étape on se rapproche d'une case du hangar, on y mènera donc toujours un robot.

A la fin, il existera encore des chemin menant les robots restant vers le hangar (par exemple le chemin inverse parcourus puis le chemin initiale).
Ainsi, on peut mener un à un des robot vers le hangar.

Il est même très facile de programmer la procédure, si on possède l'algorithme pour trouver un chemin d'un robot au hangar.

Mathieu.

 #4 - 29-05-2012 18:02:48

Vasimolo
Le pâtissier
Enigmes résolues : 49
Messages : 4734

Ehecs 11

@Mathias : Spoiler : [Afficher le message] c'est la bonne méthode , on peut juste expliciter un peu plus la première étape .
@Mathieu : Spoiler : [Afficher le message] non , le hangar est une case de passage comme une autre ( je te rappelle que plusieurs robots peuvent partager la même case ) .

Bon courage à ceux qui cherchent smile

Vasimolo

 #5 - 29-05-2012 18:15:06

gwen27
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 5,474E+3

Ececs 11

A partir du moment où on peut "regrouper" deux robots quelle que soit leur position, on peut en grouper 3 puis 4, et enfin aller les garer.

Il suffit alors de travailler avec les butées.

Dans l'exemple :
G BBBB DDDDDD et le jaune est confondu avec le bleu en bas à droite


Puis
GG H GG HHH D on attrape le rouge

Et
G BB GGG HHH DDDD B on a le vert

Et enfin : H G H Tout le monde est garé. (Enfin, si j'ai bien compris le problème.)

Gwen.

 #6 - 29-05-2012 18:20:24

nodgim
Elite de Prise2Tete
Enigmes résolues : 0
Messages : 2956

Echecs 1

Bon je ne répondrai pas, je connais. Mais c'est bien rigolo ce truc !

 #7 - 29-05-2012 18:25:54

freedomAO
Habitué de Prise2Tete
Enigmes résolues : 49
Messages : 12
Lieu: Vottem; Liège; Belgique.

evhecs 11

oui c'est possible; il suffit d'amener 2 robots sur la même case
puis 3, puis 4, puis les 4 dans le hangars.

 #8 - 29-05-2012 19:08:30

w9Lyl6n
Professionnel de Prise2Tete
Enigmes résolues : 26
Messages : 220

checs 11

Je ne sais pas pourquoi j'avais lu l'inverse de la remarque 1 roll

  Puisque on peut superposer les robots, il serait intéressant de tous les superposer et le problème deviendrait trivial.
Pour superposer deux robots c'est très simple, il suffit de choisir un des deux robots et de l'amener sur l'autre, ça marchera toujours pourvu que le labyrinthe soit borné.

preuve : Considérons le chemin initiale menant du robot choisi au second, comme une liste de déplacement.

Partie 1: décroissance
  A chaque déplacement le premier élément de la liste est retiré et on l’effectue avec la télécommande. Dans le pire des cas il faut rajouter ce déplacement à la fin de la liste pour rejoindre le robot cible, si ce dernier s'est aussi déplacé.
Donc le nombre d'élément de la liste est décroissant.

Partie 2: décroissance stricte
  Considérons le vecteur V de séparation pour passer d'un robot à l'autre  "à vole d'oiseau" (par exemple 3 case vers le bas 2 vers la gauche).
   Quand le robot poursuivant aura atteint la position initiale du robots cible,
il y a deux cas:
  _Soi le robots cible a rencontré un obstacle, auquel cas la liste de déplacement s'est réduite.
  _Sinon le robot cible s'est toujours déplacer comme le poursuivant, le vecteur V de séparation est resté constant.

  Or le labyrinthe est borné donc le robot cible ne pourra pas s'échapper éternellement en parcourant V, 2V, 3V, 4V... il finira par être bloqué par un coin.

Conclusion : la listes des déplacements à effectuer pour rassembler les robots est strictement décroissante, il finiront par se rejoindre. CQFD

Mathieu.

 #9 - 29-05-2012 19:36:05

Vasimolo
Le pâtissier
Enigmes résolues : 49
Messages : 4734

Echecss 11

Que du bon !!!

On peut considérer ça comme un échauffement pour la suite smile

La partie "1 peut rejoindre 2 en le bloquant sur un bord ou dans un coin" mérite quand même ( à mon goût  ) d'être un peu détaillée ( Bravo Mathieu ! ) .

Pour ceux qui cherchent encore , l'idée est simple !

Vasimolo

 #10 - 29-05-2012 20:08:32

elpafio
Expert de Prise2Tete
Enigmes résolues : 42
Messages : 828

Echecs 111

Une illustration d'un rangement de robots en 34 mouvements.
http://www.prise2tete.fr/upload/elpafio-robots.gif
Il est possible qu'on puisse faire plus court car je n'ai pas cherché à optimiser.
Merci pour le challenge smile


Rendez les choses aussi simples que possible, mais pas plus simples. Albert Einstein

 #11 - 29-05-2012 21:29:52

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

Ehcecs 11

Salut!
A l'occasion de celui ci:
Programmation robotique aveugle
Je m’étais posé la question jusqu'à me convaincre que c’était toujours faisable quelque soit le labyrinthe. Seulement vu la difficulté que j'ai eu a retrouver une démonstration juste et propre ça devait être du feeling.

Finalement ce soir j'ai trouvé la démonstration suivante:


On considère deux robots Alice et Bob, Bob voulant se superposer avec Alice (esprit salace s'abstenir)
Bob fait une certaine séquence d'actions S0 pour aller ou se trouvait Alice avant qu'il ne bouge.
Pendant qu'il a fait S0 Alice à réalisé la séquence effective S1 (effectif car on l'a nettoyé des éventuelles actions passives).
Bob va ensuite réaliser lui même S1 (ce qui rejoins la case ou se trouvait Alice juste avant q'uil ne démarre cette manœuvre) et on note S2 la séquence effective réalisée pendant le même temps par Alice.
Etc...
En nombre d'actions on remarque que Actions(S(n+1)) <= Actions(S(n))
Ainsi donc la suite d'entiers positifs Actions(S(n)) converge.
Comme on a S(n+1) inclus dans S(n) ceci veut dire que Bob fini par répéter indéfiniment la même séquence SK.
A vol d'oiseau SK correspond à une translation nulle sinon elle ne pourrait être réalisée indéfiniment au sein d'une enceinte bornée.
Ce qui veut dire qu'au moment ou Bob fait SK il est déjà superposé avec Alice.

A partir de là si on peut superposer deux robots on peut en superposer N et une fois superposés on peut les mettre ou on le désire.
CQFD.

 #12 - 29-05-2012 21:57:17

Franky1103
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 2717
Lieu: Luxembourg

Echecs 111

Bonjour à tous,
On peut ramener un problème à N robots à une partie à 2 robots. En effet, pour passer de N à N-1, il suffit de faire partager la même case à 2 robots. Pour arriver à cela, je dessine le chemin entre ces 2 robots, et, en bloquant l'un ou l'autre sur une cloison, je diminue la distance entre eux jusqu'à ce qu'il se rejoignent.
Bonne soirée.

 #13 - 29-05-2012 22:43:07

langelotdulac
Ange de Prise2Tete
Enigmes résolues : 49
Messages : 2963
Lieu: Paradis

Eches 11

Allez, j'fais ma folle, j'me lance ! lol

http://www.prise2tete.fr/upload/langelotdulac-vasi.png

Avec cette configuration (et d'autres sûrement), les robots qui démarrent en même temps ne se bloqueront jamais. cool

J'ai bon ?! big_smile


Tu es largement assez dingo pour qu'un Minito te semble cohérent \o/ !

 #14 - 29-05-2012 22:57:27

Vasimolo
Le pâtissier
Enigmes résolues : 49
Messages : 4734

Ececs 11

Elpatio : Chapeau pour l'animation !!!!!
Langelot : L’essentiel est de participer smile

Bravo aux autres .

Un petit challenge pour les amateurs : le minimum de manip pour ranger tous les robots avec l'exemple proposé ???

Vasimolo

 #15 - 29-05-2012 23:22:32

irmo322
Professionnel de Prise2Tete
Enigmes résolues : 36
Messages : 198

checs 11

Proposition: Quelque soit le labyrinthe (fini), s'il existe un chemin allant du robot rouge au robot vert, alors on peut avec une seule télécommande faire rejoindre les deux robots.

Corollaire: Quelque soit le labyrinthe, quelque soit le nombre (fini) de robot, s'ils sont connectés, alors on peut avec une seule télécommande les faire rejoindre.

Corollaire: Quelque soit le labyrinthe, quelque soit le nombre (fini) de robot, s'ils sont connectés à la case hangar, alors on peut les amener avec une seule télécommande à la case hangar.


J'ai toujours eu envie d'écrire des trucs comme ça... tongue

 #16 - 29-05-2012 23:31:30

Franky1103
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 2717
Lieu: Luxembourg

EEchecs 11

J'ouvre les "hostilités":
- GBBBB: bleu et jaune sont en bas,
- DDDDDD: bleu a rejoint jaune,
- GGGHHGGHHHGG: bleu/jaune a rejoint rouge,
- DDBBGGGHHHDDDDHH: bleu/jaune/rouge a rejoint vert,
- BGH: bleu/jaune/rouge/vert est au garage.
J'en suis à 42 coups: qui dit mieux ?
A+

 #17 - 30-05-2012 17:50:27

Vasimolo
Le pâtissier
Enigmes résolues : 49
Messages : 4734

zchecs 11

J'ai ajouté , dans le message initial , un palmarès pour le minimum de déplacements avec la position proposée .

Vasimolo

 #18 - 30-05-2012 22:42:26

Moriss
Professionnel de Prise2Tete
Enigmes résolues : 37
Messages : 460

Ehcecs 11

En 35 mvts.
1) Je fusionne Bleu et Jaune :
← ↓↓↓↓ → → → → → →
Rouge est donc descendu en bas de sa colonne, Vert est tout à droite de son couloir.

2) Je fusionne Bleu/jaune avec Rouge :
← ← ↑ ← ↑ ← ↓↓↓
Vert est alors tout à gauche de son couloir.

3) Je les fusionne avec Vert :
↑ ← ← ← ↑↑↑ → → → → ↓

4) Je range tout le monde dans le hangar :
↑ ← ↑

5) et maintenant, je cherche où j'ai rangé ces foutues télécommandes !
smile

 #19 - 30-05-2012 23:16:27

langelotdulac
Ange de Prise2Tete
Enigmes résolues : 49
Messages : 2963
Lieu: Paradis

Echec s11

Langelot : L’essentiel est de participer

Ca sent pas bon ça ! lol


Tu es largement assez dingo pour qu'un Minito te semble cohérent \o/ !

 #20 - 30-05-2012 23:17:27

Vasimolo
Le pâtissier
Enigmes résolues : 49
Messages : 4734

Echecs 1

@Morris : Spoiler : [Afficher le message] il me semble que tu as zappé quelques touches

Vasimolo

 #21 - 30-05-2012 23:17:32

Moriss
Professionnel de Prise2Tete
Enigmes résolues : 37
Messages : 460

rchecs 11

J'ai édité mon message : je n'ai trouvé qu'une touche manquante (désolé).

 #22 - 31-05-2012 10:54:16

Corsaire
Amateur de Prise2Tete
Enigmes résolues : 27
Messages : 7

echexs 11

37 en faisant:

mettre le bleu en bas à droite, le jaune le rejoint, on les fait remonter vers le rouge, qui les rejoints tout à gauche, un fusionne avec le vert et les 4 vont se ranger:

GAUCHE
BAS
DROITE 6
BAS 3
GAUCHE 2
HAUT
GAUCHE 2
HAUT 1
GAUCHE
BAS 2
GAUCHE 3
HAUT 5
BAS 2
DROITE 4
HAUT
GAUCHE
HAUT

Premier essai à chaud.. j'y réfléchi plus longtemps.. :p

 #23 - 31-05-2012 11:05:44

Corsaire
Amateur de Prise2Tete
Enigmes résolues : 27
Messages : 7

Echec s11

Autre méthode, jaune et rouge descendent, jaune rejoint par le bleu, puis rejoignent le rouge qui rejoignent le vert.. mais tjs 37 mouvements.. sad

Bas 4
Gauche 2
Bas 1
DROITE 6
Gauche 2
HAUT 2
GAUCHE
BAS 3
GAUCHE
HAUT
GAUCHE 3
HAUT 3
DROITE 2
HAUT
DROITE 2
HAUT
GAUCHE
HAUT

 #24 - 31-05-2012 11:38:40

ThomasLRG
Habitué de Prise2Tete
Enigmes résolues : 41
Messages : 31

EEchecs 11

Je trouve 34 aussi :

G Bx4 Dx6 Gx2 Hx2 G Bx2 G H Gx3 Hx3 Dx4 B H G H

 #25 - 31-05-2012 15:07:38

thefinder
Amateur de Prise2Tete
Enigmes résolues : 31
Messages : 4

Ecehcs 11

Bonjour en 35 coups
1 gauche 4 bas 6 droite (jaune et bleu confondus)
2 gauches 2 haut 1 gauche 1 bas 1 gauche 2 bas (3 confondus)
1 haut 3 gauche 3 haut 3 droite 1 haut (vert dans la zone grise)
1 droite 1 haut 1 gauche 1 haut (fini).
Je ne vois pas comment on peut faire 34 coups?

Réponse rapide

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

Répondez à la devinette suivante : 

Le père de toto a trois fils : Pif, Paf et ?

Sujets similaires

Sujet Date Forum
P2T
Echecs 1 par Vasimolo
08-08-2010 Enigmes Mathématiques
P2T
Echecs 17 ( lombrics ) par Vasimolo
09-10-2012 Enigmes Mathématiques
P2T
'123' '10 11 12' ... par stefben
25-09-2009 Enigmes Mathématiques
P2T
Echecs 3 (bis) par gasole
08-03-2011 Enigmes Mathématiques
16-09-2010 Enigmes Mathématiques
P2T
Echecs 21 par Vasimolo
14-11-2012 Enigmes Mathématiques
P2T
Echecs 19 bis par Vasimolo
02-11-2012 Enigmes Mathématiques
26-10-2007 Enigmes Mathématiques
30-09-2008 Enigmes Mathématiques
P2T
Echecs 9 par Vasimolo
15-03-2011 Enigmes Mathématiques

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