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 vérifié et annoté : les passages entre crochets sont des éditeurs]
reçu le 15 octobre 2004, publié en janvier 2005, revu en juillet 2005
[ L'icone renvoie au Glossaire MATh.en.JEANS , à un document ]

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. [note 1]

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.

[Définition 1]. 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 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. [note 2]

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. (note 2)

[le principe de la démonstration est le suivant.

On applique la recette de la solution pour parcourir le labyrinthe. Deux éventualités se présentent alors : soit on trouve la sortie, auquel cas on s'arrête, soit on "tourne en rond sans trouver la sortie", auquel cas on finit par repasser deux fois par le même chemin : même couloir, même sens de parcours.

Nous allons montrer, avec un raisonnement par l'absurde, que la seconde éventualité ne se produit pas.]

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

On veut démontrer que, [sans sortir], on ne peut pas passer deux fois dans le même sens dans le même couloir.
On suppose donc qu'on [puisse] passer, [sans sortir], 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 [par] 3, 2, 1 et donc [par] 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] [...] 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 !!! [note 3]

1. Pour la recherche s'est effectuée avec des exemples de labyrinthes tracés sur un quadrillage. Un labyrinthe est une portion d'espace bordée par une ligne fermée (le plus souvent rectangulaire) appelée l'enceinte, à l'intérieur de l'enceinte des murs délimitent des couloirs et des carrefours.

Certaines lignes du quadrillage sont tracés en trait épais et représentent des pans de mur infranchissables.

Pour être plus précis sur les notions de mur, couloir, carrefours, il faudrait faire appel à la théorie de graphes. Disons ici, que l'intérieur du labyrinthe est constitué de cases du quadrillage. les cases du quadrillage situées à l'intérieur de l'enceinte se répartissent en deux catégories : les cases carrefour, bordées sur un ou aucun coté, et les cases couloirs, bordées sur deux cotés ou plus. Deux cases contigües non séparées par un pan de mur sont dites adjacentes. Un chemin allant d'une case carrefour à un autre, est formé de cases adjacentes successives et bordé de deux cotés par des murs sont des cases "carrefours"; les cases bordés sur deux cotés au moins sont des cases "couloir". . Deux cases contigües non séparées par un pan de mur sont appelées adjacentes. Deux types de cases peuvent être distinguées : Deux cases particulières représentent l'entrée et la sortie du labyrinthe (la sortie communique généralement avec l'extérieur). L'ensemble de tous les pans de murs que l'on peut tracer sans lever le crayon à partir de l'un d'eux forme ce qu'on appellera un mur. Les murs partagent l'intérieur du labyrinthe en couloirs : on peut voir grosso modo un couloir comme. Dans l'exemple ci-dessous, il y a 8 murs, dont 2 murs d'enceinte, 14 carrefours et 15 couloirs. Pour es définitions plus précises feraient appel à la théorie des graphes.

retour à l'appel de cette note

2. "LA" solution des auteurs est "UN" moyen de sortir du labyrinthe trouvé par les auteurs. Rien n'empêche que d'autres solutions puissent exister.

retour à l'appel de cette note

3.

retour à l'appel de cette note

4. 

retour à l'appel de cette note