Exercice 1 — Le baguenaudier

Sujet

Le baguenaudier est un casse-tête composé de deux parties principales : la navette qui est une tige métallique recourbée sur elle-même et le système des anneaux.
L'objectif est de séparer les anneaux enchevêtrés de la navette.
Il résulte de la construction du baguenaudier que le déplacement d'un seul anneau est soumis aux principes suivants :

• On peut toujours baisser le premier anneau situé à droite s'il est levé, ou le lever s'il est baissé.
• Pour qu'un anneau de rang quelconque puisse être déplacé, c'est-à-dire levé ou baissé, il faut et il suffit qu'il se trouve placé immédiatement à la gauche d'un anneau monté, et que celui-ci soit le seul anneau monté à la droite de l'anneau considéré.

On représente la navette par une droite horizontale, les anneaux levés par des ronds placés au-dessus, dans leur situation respective, et les anneaux baissés, par des ronds placés au-dessous.
Par exemple si la position d'un baguenaudier à 7 anneaux est la suivante :

Les deux mouvements possibles sont représentés par les schémas suivants :

1. Voici la position d'un baguenaudier à 7 anneaux :
   

Représenter par un schéma analogue les mouvements possibles à l'étape suivante.
2. Démonter le baguenaudier signifie qu'on doit passer de la position initiale où tous les anneaux sont levés à la position finale où tous les anneaux sont baissés.
Dresser la liste minimale d'étapes pour démonter un baguenaudier à 3 anneaux.
3. Montrer qu'on peut démonter en 10 étapes un baguenaudier à 4 anneaux.
4. On code désormais la position des anneaux, en partant de la gauche par 0 ou 1 avec les conventions suivantes :

• Le premier anneau levé à gauche est codé 1 et les anneaux levés situés à sa droite sont représentés alternativement par 0 et 1 , sans tenir compte, dans cette alternance, des anneaux baissés.