Comptes Rendus MATh.en.JEANS 04-02

Enseignants : Dominique GUY, Mickaël PRADO.

Chercheur : Loïc ALLYS (Université du Mans).

Atelier MATh.en.JEANS du Lycée Romain Rolland (Argenteuil, 95). Atelier de Pratique Scientifique, année scolaire 2003-2004.

---

[Article en cours d'analyse et de vérification : les passages entre crochets sont des éditeurs]

1. Sujet

Comment trouver son chemin dans un labyrinthe?

Bien sûr on ne dispose pas du plan du labyrinthe. On peut seulement marquer certains couloirs ou carrefours pour éviter de tourner en rond, avec des craies ou des petits cailloux.

2. Les recherches effectuées

Pour commencer, on a voulu mettre en avant l'aspect mathématique. C'est pour cela qu'on a choisi d'insérer les lettres x, y, z et o spécifiques d'une orientation:

X ====> droite ; Y ====> gauche ; Z ====> tout droit ; O ====> demi tour

Les points cardinaux. On a découvert qu'il était plus judicieux d'utiliser les points cardinaux. En effet suivant la position d'une personne la droite et la gauche diffèrent.

On a donc noté à l'aide des points cardinaux le chemin emprunté, et ce dans plusieurs labyrinthes, puis on a comparé les résultats . Nous avons vu que certaines périodes se répétaient et on a donc essayé de les supprimer.

Or ceci n'a pas marché.

Suite aux recherches vaines précédentes, nous sommes allés chercher d'autres pistes, dont la définition du labyrinthe, afin d'avoir plus d'informations sur celui-ci.

Par définition, dans un labyrinthe tous les murs sont reliés entre eux.

3. La solution

Ceci nous a poussé à nous dire que le mur d'entrée est relié au mur de la sortie.

Nous avons donc suivi le mur se situant à notre droite pour voir si il nous mène à la sortie. Ceci a marché.

Nous avons procédé de manière analogue pour le mur de gauche et avons également trouvés la sortie ainsi.

Nous avons étendue ce procédé à plusieurs labyrinthes.

Nous en avons conclu :

[Théorème 1]. La [Une] solution consiste à toujours suivre de la même main le mur droit, ou le mur gauche, à l'entrée du labyrinthe, celui-ci nous menant à la sortie.

4. La démonstration de la solution.

Nous allons donc vous démontrer notre solution mathématiquement par le biais du raisonnement par l'absurde.

Raisonnement par l'absurde Soit une propriété dont on désire montrer qu'elle est vraie. Le raisonnement par l'absurde consiste à supposer que cette propriété est fausse et à aboutir à une contradiction.

Exemple de raisonnement par l'absurde. On veut démontrer que 5 est impair, commençons par supposer que 5 est pair. Supposons que 5 est pair. Soit n un nombre entier naturel non nul. Si 5 est pair alors on peut l'écrire 2n. Donc 2n = 5. D'où n = 2,5 Or 2,5 n'est pas un nombre entier naturel non nul. Notre hypothèse de départ est donc absurde. On en conclut donc que 5 n'est pas pair mais impair !

On s' est rendu compte que notre solution est valable car on ne passe pas par le même chemin deux fois dans le même sens.

Démonstration de notre solution avec le raisonnement par l'absurde

On veut démontrer qu'on ne peut pas passer deux fois dans le même sens dans le même couloir.
On suppose donc que l'on peut passer deux fois dans un même couloir dans le même sens.

On commence par numéroter les couloirs par lesquels on est passé. On remarque que par exemple si on repasse par le chemin [numéro] 5 dans le même sens cela signifie que l'on est déjà passé par le chemin [numéro] 4 et ainsi par tous les chemins précédents c'est à dire 3, 2, 1 et donc l'entrée. Or l'entrée étant à l'extérieur du labyrinthe cela signifie qu'on est déjà sorti et donc l'hypothèse de départ est absurde.

Donc on ne peut pas passer dans le même chemin deux fois dans le même sens.

Ainsi notre solution concernant le fait de trouver la sortie dans un labyrinthe sans disposer du plan de celui-ci est donc valable. 

5. [Autres] cas [...] de labyrinthes.

Il existe un certain type de labyrinthes, où tous les murs ne sont pas reliés entre eux. Pour ce cas, notre solution marchera si on est à l'extérieur du labyrinthe au départ.

Par contre si au départ on est au milieu du labyrinthe, il suffit de poser des cailloux pour déterminer sa position de départ. Ainsi, si on se rend compte que l'on est revenu à notre position de départ, on change de mur. Il faut poser un caillou à chaque nouveau mur pour éviter d'emprunter des murs par lesquels on est déjà passé. En procédant ainsi nous finissons par trouver le mur relié à la sortie et ainsi la sortie !!!

LABYRINTHES GRAPHES PLANAIRES SORTIE ALGORITHME GAUCHE DROITE