Pensez à lire la Charte avant de poster !

$\newcommand{\K}{\mathbf K}$


Les-Mathematiques.net - Cours de mathématiques supérieures
 Les-Mathematiques.net - Cours de mathématiques universitaires - Forum - Cours à télécharger

A lire
Deug/Prépa
Licence
Agrégation
A télécharger
Télécharger
223 personne(s) sur le site en ce moment
E. Cartan
A lire
Articles
Math/Infos
Récréation
A télécharger
Télécharger
Théorème de Cantor-Bernstein
Théo. Sylow
Théo. Ascoli
Théo. Baire
Loi forte grd nbre
Nains magiques
 
 
 
 
 

Démonstration stratégie du labyrinthe

Envoyé par adrien2019 
Démonstration stratégie du labyrinthe
il y a quatre semaines
Bonjour à tous
Je me pose une question que je poste dans le forum algèbre, même si je ne sais pas vraiment de quelle théorie elle relève.

Considérons un labyrinthe dessiné dans le plan, avec exactement deux "entrées" (une par laquelle on entre, l'autre par laquelle on sort). Il est connu qu'une stratégie pour trouver la sortie est de poser sa main sur le mur dès l'entrée, et de suivre ce mur: on tombera alors fatalement à un moment sur la sortie (càd l'autre "entrée").

Je cherche une démonstration rigoureuse de ce résultat, et je pense aussi une formulation plus "mathématique" de l'énoncé de la question (j'ai décrit "avec les mains" ce que j'ai en tête, mais par exemple je ne sais pas comment définir un "labyrinthe" mathématiquement, et encore moins ce que j'appelle "entrées", même si on voit bien à quoi ça correspond sur un dessin).

Je vous remercie d'avance pour votre aide !



Edité 1 fois. La dernière correction date de il y a quatre semaines et a été effectuée par AD.
MrJ
Re: Démonstration stratégie labyrinthe
il y a quatre semaines
Une idée : ce que tu décris reviens à parcourir en profondeur le graphe associé au labyrinthe jusqu'à tomber sur le noeud correspondant à ma sortie.

Avec cet algorithme, tu vas visiter l'ensemble de la composante connexe du noeud de départ.



Edité 1 fois. La dernière correction date de il y a quatre semaines et a été effectuée par MrJ.
Re: Démonstration stratégie du labyrinthe
il y a quatre semaines
@MrJ merci pour votre réponse, mais pourriez-vous préciser un peu plus votre raisonnement? Par exemple, j’ai du mal à voir le lien entre le labyrinthe et un graphe.
Re: Démonstration stratégie du labyrinthe
il y a quatre semaines
avatar
Oh!


Re: Démonstration stratégie du labyrinthe
il y a quatre semaines
avatar
Bonsoir.

Dans le cas envisagé par Soland, l'entrée est aussi la sortie et la sortie est aussi l'entrée.

Du reste, la procédure appliquée permet de parcourir l'entièreté du "labyrinthe", en y entrant et en sortant deux fois avant de revenir à n'importe quel point de départ.

À bientôt.

Cherche livres & objets du domaine mathématique : intégraphes, règles log & engins [électro]méca ou analog



Edité 1 fois. La dernière correction date de il y a quatre semaines et a été effectuée par Dreamer.
Re: Démonstration stratégie du labyrinthe
il y a quatre semaines
Bonsoir,

Effectivement, le dessin de soland montre qu'on peut ressortir par la première entrée (et pas nécessairement par la seconde entrée).

J'ai de plus réfléchi et je ne suis pas certain qu'un graphe soit le bon objet mathématique pour un labyrinthe... quelqu'un pourrait-il par exemple me montrer quel graphe est associé au schéma de soland (nœuds et arrêtes)?

Dans tous les cas je pense qu'il faudrait préciser l'énoncé en termes mathématiques, mais je n'ai aucune idée... quelqu'un aurait-il une idée d'une définition mathématique d'un graphe, et de la notion d'entrée?
Re: Démonstration stratégie du labyrinthe
il y a quatre semaines
avatar
A chaque labyrinthe, tu peux associer un graphe en faisant de chaque "pièce" un noeud et de chaque "porte" une arête.
Pour finir, tu ajoutes un noeud pour l'extérieur du labyrinthe.

Donc, pour le dessin de soland, tu obtiens un graphe à 3 noeuds (les deux pièces Gauche, Droite et l'Extérieur) et deux arêtes (G-E et D-E).
Re: Démonstration stratégie du labyrinthe
il y a quatre semaines
Citation

mais pourriez-vous préciser un peu plus votre raisonnement?

Pour accepter ce que te dit MrJ, il suffit de mettre un ordre sur les voisins (on visite le 1, puis le 2, ..) et ce pour chaque sommet.

Signature: aide les autres comme toi-même car ils SONT toi, ils SONT VRAIMENT toi
MrJ
Re: Démonstration stratégie du labyrinthe
il y a trois semaines
Désolé, j'avais oublié ce fil.

Je pense que ce que j'ai dit est juste, mais j'avoue que je pensais à un gentil labyrinthe quand j'ai posté mon premier message (comme celui-là par exemple).

Si tu pars d'un labyrinthe "quelconque" (mais formellement, comment le définir ?), je pense que passer totalement rigoureusement de la vision géométrique à l'approche avec un graphe est plutôt difficile. Après pour les labyrinthes "classiques", çà se voit assez facilement, au moins de manière intuitive.



Edité 3 fois. La dernière correction date de il y a trois semaines et a été effectuée par AD.
Re: Démonstration stratégie du labyrinthe
il y a trois semaines
Bonjour.

Une heuristique :
A partir de l'entrée, tu traces au milieu du couloir un trait, en rajoutant des traits liés pour chaque nouveau couloir, jusqu'à avoir rempli la partie accessible du labyrinthe (il peut y avoir des parties fermées). Tu as obtenu le tracé des chemins possibles (TCP). En négligeant les parties inaccessibles, la situation géométrique (topographique) est celle-ci : le labyrinthe est un ensemble de murs situés (en gros) à une demi largeur de couloir du TCP. En suivant le mur à main droite, tu te places à gauche du TCP (dans le sens de ta progression). Si tu reviens à un endroit où tu es déjà passé, tu es dans le sens contraire, donc tu es de l'autre côté du TCP, tu ne boucles pas. La longueur de murs étant finie, au bout d'un certain temps (ou souvent un temps certain !) tu auras fait au plus le double de la longueur des murs et tu ressortiras; par l'entrée (Pas de sortie autre que l'entrée, cas de Thésée) ou une sortie.

Cette heuristique coince si la sortie est dans une partie dont on fait le tour : On sort par un niveau inférieur ou supérieur. Elle ne fonctionne qu'avec un labyrinthe plan.

Cordialement.



Edité 1 fois. La dernière correction date de il y a trois semaines et a été effectuée par AD.
Seuls les utilisateurs enregistrés peuvent poster des messages dans ce forum.

Cliquer ici pour vous connecter

Liste des forums - Statistiques du forum

Total
Discussions: 149 214, Messages: 1 506 686, Utilisateurs: 27 657.
Notre dernier utilisateur inscrit Algomius.


Ce forum
Discussions: 889, Messages: 7 537.

 

 
©Emmanuel Vieillard Baron 01-01-2001
Adresse Mail:

Inscription
Désinscription

Actuellement 16057 abonnés
Qu'est-ce que c'est ?
Taper le mot à rechercher

Mode d'emploi
En vrac

Faites connaître Les-Mathematiques.net à un ami
Curiosités
Participer
Latex et autres....
Collaborateurs
Forum

Nous contacter

Le vote Linux

WWW IMS
Cut the knot
Mac Tutor History...
Number, constant,...
Plouffe's inverter
The Prime page