Exercice 3 — Parlons le MIU — Olympiades 2012 Montpellier et Maroc

Sujet

Dans le jeu suivant, on appelle mot une suite de lettres ou chaîne de caractères.
Les mots que nous allons considérer n'utilisent que les trois lettres \(M, I\) et \(U\), autant de fois que l'on veut (IMUUIM est un tel mot).
Le but du jeu est de fabriquer des mots nouveaux à partir du seul mot \(M I\).
Pour cela, il y a quatre règles, et quatre seulement, qui permettent d'agrandir la collection de mots :
\(\mathbf{R}_{1}\) : Si vous possédez un mot se terminant par \(I\), vous pouvez lui rajouter un \(U\) à la fin.
Par exemple, avec \(M I\) vous pouvez faire \(M I U\).
\(\mathbf{R}_{2}\) : Si vous avez un mot de la forme \(M x\) où \(x\) représente n'importe quelle chaîne de caractères jusqu'à la fin du mot, vous pouvez faire le mot \(M x x\).
Par exemple, avec MIU vous pouvez faire MIUIU et avec MI vous pouvez faire MII.
\(\mathbf{R}_{3}\) : Si dans un mot vous avez III (trois fois la lettre I) vous pouvez remplacer ce III par \(U\) et inversement \(U\) par III.
Par exemple avec UIIIM vous pouvez faire UUM ou IIIIIIM.
\(\mathbf{R}_{4}\) : Si dans un mot vous avez \(U U\) à n'importe quel endroit du mot vous pouvez supprimer ce \(U U\).
Par exemple avec MIMUU vous pouvez faire MIM.
Vous pouvez appliquer ces règles dans l'ordre de votre choix.

Montrez qu'on peut fabriquer le mot MUIUI (indiquer soigneusement les étapes suivies avec les numéros des règles utilisées).
Montrez qu'on peut fabriquer le mot MUIIU (indiquer soigneusement les étapes là aussi)
Peut-on fabriquer le mot \(M U\) ? Si non, pourquoi?

En tous cas, aMIUsez-vous bien!

\(M I \xrightarrow{R 2} M I I \xrightarrow{R 2} M I I I I \xrightarrow{R 3} M U I \xrightarrow{R 2} M U I U I\)
MI \(\xrightarrow{R 2}\) MII \(\xrightarrow{R 2}\) MIIII \(\xrightarrow{R 1}\) MIIIU \(\xrightarrow{R 3}\) MUIU \(\xrightarrow{R 2}\) MUIUUIU \(\xrightarrow{R 4}\) MUIIU
Montrons qu'il est impossible d'obtenir MU.

Pour chaque mot \(m\) obtenu, notons \(N(m)\) le nombre \(I\) de lettres présentes dans ce mot.
Au départ \(N(M I)=1\).
Si on a un mot \(m\) et qu'on fabrique un mot \(m^{\prime}\) en utilisant une des quatre règles, avec \(\mathrm{R}_{1}\) et \(\mathrm{R}_{4}\), le nombre de \(I\) ne change pas. Avec \(\mathrm{R}_{2}\), on a \(N\left(m^{\prime}\right)=2 N(m)\), et avec \(\mathrm{R}_{3}\), on a \(N\left(m^{\prime}\right)=N(m) \pm 3\). En utilisant le langage commode des congruences : modulo 3, la seule règle qui modifie \(N(m)\) est \(\mathrm{R}_{2}\), et par cette règle \(N(m)\) est multiplié par 2 modulo 3 .
Il est donc exclu en partant de \(m=M I\) avec \(N(m)=1\), d'arriver à un mot final \(M U\) avec \(N(M U)=0\).

Au niveau première, on parlera seulement de divisibilité par \(3 \ldots\)