Cette partie comporte des questions nécessitant un code C.
Soit $G=(S, A)$ un graphe non orienté à $|S|=n$ sommets. On note ce graphe
$G=(S, A, c)$ lorsqu'il est muni d'une fonction de valuation des arêtes $c: S
\times S \rightarrow\mathbb{N}$ telle que pour tout $s \in S, c(s, s)=0$ et
$c(s, t)=+\infty$ s'il n'existe pas d'arête entre $s$ et $t$.
\begin{definition}[Cycle hamiltonien]
Un cycle hamiltonien dans $G=(S, A)$ est un chemin qui passe une fois
et une seule par chaque sommet de $G$ et qui commence et termine par le
même sommet.
\end{definition}
On considère les problèmes suivants:
\begin{itemize}
\item CYCLE-HAMILTONIEN qui, étant donné un graphe non orienté $G=(S, A)$, décide s'il existe un cycle hamiltonien dans $G$,
\item COUVERTURE-SOMMET qui, étant donnés un graphe non orienté $G=(S, A)$ et $m \in\mathbb{N}$, décide s'il existe un sous-ensemble de sommets $S_{c} \subseteq S$ tel que $|S_{c}| \leq m$ et que chaque arête de $A$ ait au moins une de ses extrémités dans $S_{c}$,
\item TSP qui, étant donnés un graphe $G=(S, A, c)$ et un entier $k \in\mathbb{N}$, décide s'il existe un cycle hamiltonien dans $G$ de coût inférieur ou égal à $k$.
\end{itemize}
On admet dans la suite que COUVERTURE-SOMMET est NP-complet. On souhaite alors montrer que TSP est NP-complet.
\begin{question}
Montrer que TSP est dans NP.
\end{question}
\subsection{Réduction de CYCLE-HAMILTONIEN vers TSP}
\begin{question}
Montrer que CYCLE-HAMILTONIEN est dans NP.
\end{question}
Soit $G=(S, A)$ une instance de CYCLE-HAMILTONIEN. On construit l'instance correspondante de TSP comme suit:
\begin{enumerate}[(i)]
\item on crée un nouveau graphe $G'=(S', A')$ qui est un graphe complet tel que $S'=S$,
\item on attribue un coût à chaque arête de $G'$:
\begin{itemize}
\item si l'arête ( $s, t$ ) existe dans $G$, on lui attribue un coût de 1 ,
\item si l'arête ( $s, t$ ) n'existe pas dans $G$, on lui attribue un coût de 2 ,
\end{itemize}
\item on fixe un seuil de coût $k=|S|$.
\end{enumerate}
\begin{question}
Montrer que la construction de $G'$ est polynomiale en la taille de $G$.
\end{question}
\begin{question}
Montrer que si CYCLE-HAMILTONIEN renvoie Vrai sur l'entrée $G$ alors TSP renvoie Vrai sur l'entrée $(G', k)$.
\end{question}
\begin{question}
Montrer que si TSP renvoie Vrai sur l'entrée $G'$ alors CYCLE-HAMILTONIEN renvoie Vrai sur l'entrée $G$.
\end{question}
\subsection{Réduction de COUVERTURE-SOMMET vers CYCLE-HAMILTONIEN}
Soient une instance de COUVERTURE-SOMMET donnée par le graphe $G=(S, A)$ et un entier $m \leq|S|$. On doit construire un graphe $G'=(S', A')$ tel que $G'$ a un cycle hamiltonien si et seulement si $G$ a une couverture de sommets de taille au plus $m$. On admettra cette équivalence dans la suite. On s'intéresse, pour les questions\ref{q:exemple-couverture} à \ref{q:construction-gprime}, uniquement à la construction de $G'$ à partir de $G$. De plus, pour les questions\ref{q:exemple-couverture} à \ref{q:ensembles-etape3}, on utilisera le graphe $G$ décrit dans la figure\ref{fig:graphe-exemple}.
\begin{figure}[h]
\begin{center}
\begin{tikzpicture}[scale=1.5]
\node[draw,circle] (alpha) at (1,2) {$\alpha$};
\node[draw,circle] (beta) at (0,1) {$\beta$};
\node[draw,circle] (gamma) at (3,2) {$\gamma$};
\node[draw,circle] (delta) at (2,1) {$\delta$};
\node[draw,circle] (epsilon) at (2,0) {$\epsilon$};
Le problème COUVERTURE-SOMMET répond-il Vrai pour $m=2$? pour $m=3$? Si oui, donner pour chaque valeur de $m$ un sous-ensemble $S_{c}$ correspondant.
\end{question}
La construction de $G'$ passe par les étapes suivantes:
\begin{enumerate}[(i)]
\item\label{etape1} on construit $m$ sommets $a_{1} \ldots a_{m}$ utilisés pour sélectionner $m$ sommets de $G$,
\item\label{etape2} pour chaque arête $e=(s, t)$ de $G$, on construit un graphe gadget $G_{e}=(S_{e}, A_{e})$ à 12 sommets et 14 arêtes avec $S_{e}=\{s_{i}(e), i \in\llbracket1,6\rrbracket\}\cup\{t_{i}(e), i \in\llbracket1,6\rrbracket\}$ et
\item\label{etape3} pour chaque sommet $s \in S$ de degré $d(s)$, on connecte tous les graphes gadgets où $s$ apparaît. Pour ce faire, on construit un ensemble d'arêtes $A_{s}=\{\{s_{6}(e_{s[j]}), s_{1}(e_{s[j+1]})\}, j \in\llbracket1, d(s)-1\rrbracket\}$, où les $e_{s[j]}$ sont les arêtes incidentes à $s$ ordonnées arbitrairement. Cette étape créé un chemin dans $G'$ composé exactement des sommets $u_{i}(e)$ tels que $u=s$.
\item on complète les arêtes de $G'$ en connectant les sommets $a_{1} \ldots a_{m}$ aux premiers et derniers sommets de chaque chemin créé dans l'étape précédente. Pour ce faire, on construit les arêtes $A_{c}=\{\{a_{i}, s_{1}(e_{s[1]})\},\{a_{i}, s_{6}(e_{s[d(s)]})\}, i \in\llbracket1, m \rrbracket, s \in S\}$.
\end{enumerate}
Le graphe $G'$ est alors défini par $S'=\{a_{i}, i \in\llbracket1, m \rrbracket\}\cup(\cup_{e \in A} S_{e})$ et $A'=(\cup_{e \in A} A_{e})\cup(\cup_{s \in S} A_{s})\cup A_{c}$.
\begin{question}
Dessiner le graphe gadget de l'arête $e_{2}=(\beta, \delta)$. Représenter les $\beta_{i}(e_{2})$ sur une même ligne, les $\delta_{i}(e_{2})$ sur une même ligne, chaque $\beta_{i}(e_{2})$ étant à la verticale de $\delta_{i}(e_{2})$.
\end{question}
Soit $e=(s, t)$ une arête de $G$. Le graphe gadget $G_{e}$ permet de garantir qu'au moins une extrémité de $e$ figure parmi les $m$ sommets sélectionnés dans l'étape\ref{etape1}. Dans la construction finale de $G'$, les seuls sommets de $G_{e}$ qui seront impliqués dans des arêtes supplémentaires construites dans l'étape\ref{etape2} sont $s_{1}(e), t_{1}(e), s_{6}(e)$ et $t_{6}(e)$.
\begin{question}
Donner alors les trois traversées possibles du gadget $G_{e}$ par un cycle hamiltonien dans $G'$.
\end{question}
\begin{question}\label{q:ensembles-etape3}
Donner les ensembles $A_{\gamma}$ et $A_{\delta}$ produits par l'étape\ref{etape3}.
\end{question}
\begin{question}\label{q:construction-gprime}
Montrer que $G'$ peut être construit à partir de $G$ et $m$ en temps polynomial.
\end{question}
\subsection{Conclusion des réductions}
\begin{question}
En déduire que TSP est NP complet.
\end{question}
\subsection{2-approximation du problème TSP}
On change ici la manière de voir le problème TSP. On passe du problème de décision au problème d'optimisation: étant donné un graphe $G=(S, A, c)$, trouver dans $G$ le chemin de coût total minimal qui passe exactement une fois par chaque sommet et revient au sommet de départ.
On ajoute maintenant une contrainte sur la fonction $c$: on demande à ce qu'elle respecte l'inégalité triangulaire, c'est-à-dire: $V(s, t, u)\in S^{3} c(s, u)\leq c(s, t)+c(t, u)$. On suppose de plus que le graphe $G$ est complet.
On montre alors, dans la suite, qu'il existe une 2-approximation du problème TSP. À cette fin, on propose l'algorithme\ref{algo:2approx}.
\begin{algorithm}
\caption{2-approximation du problème TSP}
\label{algo:2approx}
\begin{algorithmic}
\State{\textbf{Entrées:}$G=(S, A, c)$, $c: S \times S \rightarrow\mathbb{N}$}
\State{\textbf{Sortie:} Un cycle hamiltonien $H$}
\State{$T \gets\text{arbre couvrant de coût minimal de $G$}$}
\State{$L \gets\text{liste des sommets visités lors d'un parcours en profondeur de $T$}$}
\State{$H \gets\text{cycle hamiltonien qui visite les sommets dans l'ordre de $L$}$.}
\end{algorithmic}
\end{algorithm}
% Énoncé d'origine modifié.
% La question d'origine disait:
% « Quel algorithme peut-on utiliser pour réaliser l'étape 2 de
% l'algorithme1? Quelle est la complexité de votre solution? »
% On ne sait pas exactement à quoi fait référence cette étape 2. La ligne
% numérotée 2 dans le sujet d'origine contient uniquement le texte "début", et
% la deuxième affectation, portant sur L, n'est pas particulièrement
% intéressante. Cela ressemble à une erreur d'énoncé, où la question aurait dû
% porter sur le calcul de l'arbre couvrant de poids minimum.
\begin{question}
Quel algorithme peut-on utiliser pour réaliser le calcul de $T$ dans l'algorithme\ref{algo:2approx}? Quelle est la complexité de votre solution?
\end{question}
On note $H^{*}$ un cycle hamiltonien de coût optimal pour le problème TSP. On note également $c(E)$ le coût associé à un chemin $E$, qu'il soit représenté par une suite ordonnée d'arêtes ou de sommets.
\begin{question}
Montrer que $c(T)\leq c(H^{*})$.
\end{question}
On ajoute un sommet dans $L$ dès qu'on le rencontre lors du parcours en profondeur de $T$. Dans $L$, certains sommets sont donc visités plus d'une fois. La figure 2 donne un exemple de la construction de $L=[1,2,3,2,8,2,1,4,5,6,5,7,5,4,1]$.
\begin{figure}[h]
\caption{Exemple de calcul de $L$ par l'algorithme\ref{algo:2approx}}
node (p2) at ([xshift=-1mm,yshift=1mm]n2.north west) {}
node (p3) at ([xshift=-1mm]n3.west) {}
node (p8) at ([xshift=-1mm]n8.west) {}
node (p4) at ([xshift=-2mm]n4.south west) {}
node (p5) at ([xshift=-2mm]n5.west) {}
node (p6) at ([xshift=-1mm]n6.west) {}
node (p7) at ([xshift=-2mm]n7.west) {}
;
\draw[->] plot[smooth] coordinates {
([yshift=-1mm]p1)
(p1)
(p2)
([xshift=-1mm]n3.north west)
(p3)
([xshift=-1mm]n3.south west)
([yshift=-1mm]n3.south)
([xshift= 1mm]n3.south east)
([yshift=-2mm]n2.south)
(p8)
([xshift=-1mm]n8.south west)
([yshift=-1mm]n8.south)
([xshift= 1mm]n8.east)
([xshift= 1mm]n2.east)
([xshift= 3mm,yshift=-2mm]n1.south east)
(p4)
(p5)
([xshift=-1mm]n6.north west)
(p6)
([xshift=-1mm]n6.south west)
([yshift=-1mm]n6.south)
([xshift= 1mm]n6.south east)
([yshift=-2mm]n5.south)
(p7)
([xshift=-1mm,yshift=-1mm]n7.south west)
([yshift=-1mm]n7.south)
([xshift= 1mm,yshift=-1mm]n7.south east)
([xshift= 1mm,yshift=1mm]n7.east)
([xshift= 1mm,yshift=1mm]n5.north east)
([xshift= 1mm,yshift=1mm]n4.north east)
([yshift=1mm]n1.north)
};
\end{tikzpicture}
\caption{Construction de $L$}
\end{subfigure}
\end{center}
\end{figure}
\begin{question}
Montrer que $c(L)\leq2 c(H^{*})$.
\end{question}
\begin{question}
Montrer qu'il est possible de supprimer la visite d'un sommet dans $L$ sans augmenter le coût du parcours.
\end{question}
\begin{question}
En déduire comment construire $H$, résultat de l'algorithme\ref{algo:2approx}.
\end{question}
\begin{question}
En conclure que l'algorithme\ref{algo:2approx} produit une 2-approximation de TSP.
\end{question}
Les sommets du graphe étant codés par des entiers, on donne les structures de données suivantes:
\begin{minted}{c}
// Structure de graphe
struct Graphe_s {
int n; // Nombre de sommets
int** C; // Matrice des coûts
};
typedef struct Graphe_s Graphe;
// Structure Arbre Couvrant de coût minimal
struct ACM_s {
int* parent; // Tableau indiquant le parent de chaque sommet dans l'arbre
int n; // Nombre de sommets de l'arbre
};
typedef struct ACM_s ACM;
// Structure Cycle Hamiltonien
struct CH_s {
int* cycle; // Sommets dans l'ordre d'apparition dans le cycle
int 1; // Longueur du cycle = taille du tableau cycle
};
typedef struct CH_s CH;
\end{minted}
On admet, de plus, disposer d'une fonction de prototype \mintinline{c}{ACM* Recherche_ACM(Graphe* G)} qui calcule l'arbre couvrant de coût minimal de $G$. Cette fonction alloue la structure \mintinline{c}{ACM}:
\begin{minted}{c}
ACM* a = malloc(sizeof(ACM));
a->n = n;
a->parent = malloc(n * sizeof(int));
\end{minted}
avant de la calculer et de la renvoyer.
Soit un fichier texte, présent sur le disque et correctement écrit, de la forme:
\begin{verbatim}
fichier.txt
n p
s1 t1 c1
s2 t2 c2
...
sp tp cp
\end{verbatim}
où \mintinline{c}{n} est le nombre de sommets du graphe, \mintinline{c}{p} le nombre d'arêtes, les \mintinline{c}{p} lignes suivantes donnant les deux sommets \mintinline{c}{si} et \mintinline{c}{ti} et le coût \mintinline{c}{ci} de l'arête correspondante.
\begin{question}
Écrire une fonction de prototype \mintinline{c}{Graphe* creer_graphe(char* nom_fichier)} qui créé un graphe à partir de la lecture d'un fichier texte dont le nom est spécifié dans la chaîne de caractères \mintinline{c}{nom_fichier}. On rappelle les fonctions suivantes de gestion des fichiers:
\begin{itemize}
\item\mintinline{c}{FILE *fopen(char *nom_fichier, char *accessMode)} ouvre un fichier de nom \mintinline{c}{nom_fichier} selon le mode d'ouverture spécifié par \mintinline{c}{accessMode}. Pour une ouverture en mode lecture texte, on peut prendre \mintinline{c}{accessMode="r"};
\item\mintinline{c}{int fclose(FILE *f)} ferme le fichier pointé par \mintinline{c}{f};
\item\mintinline{c}{int fscanf(FILE *f, char *s, ...)} lit dans le fichier pointé par \mintinline{c}{f} une chaîne de caractères et utilise le paramètre \mintinline{c}{s} pour préciser le format à utiliser pour décoder la chaîne de caractères. Les valeurs lues sont stockées, une à une, dans les paramètres suivants de la fonction, dont la mémoire doit avoir été allouée. Ainsi, \mintinline{c}{fscanf(f,"%d %d" ,&i ,&j);} lit dans \mintinline{c}{f} une ligne composée de deux entiers, séparés par un espace et les stocke aux adresses \mintinline{c}{&i} et \mintinline{c}{&j}.
\end{itemize}
\end{question}
\begin{question}
Écrire une fonction de prototype \mintinline{c}{void dfs(ACM* a, int s, int* chemin, int* indice)} qui réalise un parcours en profondeur de l'arbre \mintinline{c}{a} dont la racine est \mintinline{c}{s}. \mintinline{c}{chemin} est un tableau d'entiers, \mintinline{c}{chemin[i]} contenant le $i$\ieme{} sommet du parcours: à chaque fois qu'un sommet est exploré, il est ajouté au tableau chemin à la position spécifiée par \mintinline{c}{*indice} (passage par pointeur de l'entier).
\end{question}
\begin{question}
Écrire une fonction de prototype \mintinline{c}{CH* calcule_CH(int* chemin, int n)} qui transforme le chemin calculé par \mintinline{c}{dfs} en un cycle hamiltonien. On prendra soin d'allouer correctement la structure de donnée retournée par la fonction et de refermer le chemin pour obtenir un cycle.
\end{question}
\begin{question}
Écrire des fonctions \mintinline{c}{void free_ACM(ACM* a)} et \mintinline{c}{void free_CH(CH* cycle)} qui désallouent la mémoire précédemment allouée. On supposera que la fonction \mintinline{c}{Recherche_ACM} n'effectue pas d'allocation mémoire supplémentaire.
\end{question}
\begin{question}
Écrire une fonction de prototype \mintinline{c}{CH* TSP2(Graphe* G)} qui calcule une 2-approximation de TSP. On prendra soin d'allouer/désallouer la mémoire lorsque cela est nécessaire.
\end{question}
\section{Suite de Prouhet-Thue-Morse}
Cette partie comporte des questions nécessitant un code OCaml.
L'objectif de cette partie est d'étudier quelques définitions et propriétés de la suite de Prouhet-ThueMorse (abrégé PTM), du nom des mathématiciens français, norvégien et américain Eugène Prouhet, Axel Thue et Marston Morse.
Pour $n \in\mathbb{N}$, on écrit $n$ en base $2$ sous la forme $n=\sum_{i} d_{i} 2^{i}$ et on note $b_{n}=\sum_{i} d_{i}$. On définit alors $t_{0}=0$ et pour $n>0$, $t_{n}=\begin{cases}1 & \text {si $b_n$ impair} \\0 & \text {sinon}\end{cases}$.
Écrire une fonction récursive de signature \mintinline{ocaml}{compte_bits_a_un : int -> int} telle que \mintinline{ocaml}{compte_bits_a_un n} renvoie le nombre de bits à $1$ dans l'écriture en base $2$ de l'entier $n$.
En déduire une fonction de signature \mintinline{ocaml}{affiche_ptm : int -> unit} qui affiche le mot $T_n$. On écrira une fonction auxiliaire récursive de signature \mintinline{ocaml}{puissance2 : int -> int} qui calcule $2^n$. Pour afficher les $t_i$, on utilisera la fonction \mintinline{ocaml}{print_int} de signature \mintinline{ocaml}{print_int : int -> unit}.
\end{question}
\begin{definition}[Deuxième définition]
On pose $t_{0}=0$. On suppose que pour $n>0$ on a construit le mot $T_n$. On construit alors le mot $T_{n+1}$ et donc les termes $t_{2^{n}}, \cdots t_{2^{n+1}-1}$ de la suite PTM par négation binaire: $\forall i \in\llbracket0,2^{n}-1\rrbracket, t_{2^{n}+i}=\bar{t}_{i}$. Autrement dit, $T_{n+1}=T_n \bar{T}_{n}$.
\end{definition}
\begin{question}
Montrer par récurrence que cette définition calcule la même suite que la première définition.
\end{question}
\begin{definition}[Troisième définition]
On définit la suite PTM de manière récursive: $t_{0}=0$ et pour tout $n>0 t_{2 n}=t_{n}, t_{2 n+1}=\overline{t_{n}}$.
\end{definition}
\begin{question}
Montrer que cette définition calcule la même suite que la première ou la deuxième définition.
Un morphisme sur $\Sigma^{*}$ est une fonction $\mu: \Sigma^{*} \rightarrow\Sigma^{*}$ vérifiant $\mu(\varepsilon)=\varepsilon$ et: $\forall u, v \in\Sigma^{*} \mu(u \cdot v)=\mu(u)\cdot\mu(v)$.
\end{definition}
On définit alors le morphisme suivant sur les éléments de $\Sigma: \mu(a)=\begin{cases}01 & \text {si $a=0$} \\10 & \text {si $a=1$}\end{cases}$ et la suite $(u_i, i \in\mathbb{N})$ par: $u_{0}=0$ et pour tout $i \in\mathbb{N}^{*}, u_{i+1}=\mu(u_{i})$.
\begin{question}
Montrer que pour tout $i \in\mathbb{N}^{*}$, $u_{i}=T_{i}$.
\end{question}
On représente maintenant un mot de $\Sigma^{*}$ par une liste d'entiers.
\begin{question}
Écrire une fonction de signature \mintinline{ocaml}{thue_morse_4 : int -> int list}, un appel à \mintinline{ocaml}{thue_morse_4 n} générant $T_n$. Cette fonction fera appel à une fonction récursive de signature \mintinline{ocaml}{morphisme : int list -> int list} renvoyant l'application du morphisme $\mu$ sur la liste d'entiers en entrée. On lèvera une exception \mintinline{ocaml}{INVALID_ARGUMENT} si le mot donné en entrée n'est pas binaire.
\end{question}
\subsection{Mot infini de Thue-Morse}
Le mot infini de Thue-Morse $T$ est le mot obtenu en itérant $\mu$ une infinité de fois, en partant du symbole $0$. Nous allons ici nous intéresser à la structure de $T$.
\begin{definition}[Carré, cube]
Soit $m \in\Sigma^{*}$. $m$ est un carré s'il s'écrit $m=w \cdot w$, où $w \in\Sigma^{*}$. C'est un cube si $m=w \cdot w \cdot w$, où $w \in\Sigma^{*}$.
\end{definition}
Par exemple, le mot $m=110110110$ est un cube avec $w=110$.
\begin{question}
Montrer qu'il n'existe pas de mots de $\Sigma^{*}$ de longueur supérieure ou égale à $4$ sans carrés.
Écrire une fonction récursive de signature \mintinline{ocaml}{divise_mot : int list -> int list * int list} qui divise un mot $m$ en deux sous-mots de taille identique, le premier constitué des $|m| /2$ premiers éléments de $m$, le second des éléments restants. On supposera ici que $|m|$ est paire.
En déduire une fonction de signature \mintinline{ocaml}{est_carre : int list -> bool} qui détermine si un mot $m$ est un carré. On prendra soin de vérifier que $|m|$ est paire.
$m \in\Sigma^{*}$ est un entrelacement s'il contient un facteur de la forme $xyz$ où $x, y, z$ sont des facteurs non vides de $m$ et $x y=y z$. On dit que les deux facteurs $x y$ et $y z$ se chevauchent sur la partie commune $y$.
\end{definition}
Par exemple, le mot $101\mathbf{0}1001$ est un entrelacement, puisqu'il contient le facteur $010$ en positions $2$ et $4$, qui se chevauchent sur le $0$ en position $4$ (en gras).
Écrire une fonction récursive de signature \mintinline{ocaml}{sousliste : int list -> int -> int -> int list} telle que \mintinline{ocaml}{sousliste lst i l} renvoie la sous-liste de \mintinline{ocaml}{lst} qui commence à l'indice \mintinline{ocaml}{i} et de longueur \mintinline{ocaml}{l}. Si la sous-liste dépasse la fin de la liste \mintinline{ocaml}{lst}, elle est tronquée.
Écrire une fonction de signature \mintinline{ocaml}{est_entrelacement : int list -> bool} telle que l'appel \mintinline{ocaml}{est_entrelacement m} renvoie \mintinline{ocaml}{true} si \mintinline{ocaml}{m} est un entrelacement, \mintinline{ocaml}{false} sinon. On pourra tester récursivement toutes les longueurs de facteurs possibles et, pour un facteur donné, vérifier s'il apparaît ailleurs dans le mot avec chevauchement. On utilisera obligatoirement la fonction \mintinline{ocaml}{sousliste}.
Montrer que si un mot $m$ contient un facteur cube, alors c'est un entrelacement.
\end{question}
On admet dans la suite que si un mot est un entrelacement dont la partie commune est de longueur $k \geq1$, alors c'est également un entrelacement de partie commune de longueur $1$.
\begin{question}\label{q:facteur-avava}
Montrer que si un mot $m$ est un entrelacement, alors il contient un facteur de la forme $avava$, où $a \in\Sigma$ et $v \in\Sigma^{*}$.
Soit $m=a_{0} a_{1} \cdots a_{2 n-1} \in\Sigma^{*}$ tel que, pour tout $i \in\llbracket[0, n-1]$, $a_{2 i} a_{2 i+1}$ s'écrit soit $01$, soit $10$. Montrer qu'il n'est pas possible d'écrire les mots $0 m 0$ et $1 m 1$ sous la forme $b_{0} b_{1} \cdots b_{2 n+1}$, où, pour tout $i \in\llbracket0, n \rrbracket$, $b_{2 i} b_{2 i+1}$ s'écrit soit $01$, soit $10$.
\end{question}
Soit $m \in\Sigma^{*}$. On construit le mot $\mu(m)$ où $\mu$ est défini après la définition\ref{def:quatrieme}. Si $\mu(m)= wavavaz$ où $a \in\Sigma$ et $v, w, z \in\Sigma^{*}$, on peut montrer qu'alors $v$ contient un nombre impair de symboles.
\begin{question}
Montrer, en utilisant la question\ref{q:facteur-avava} et l'indication précédente, que si $\mu(m)$ est un entrelacement, alors $m$ est un entrelacement.
\end{question}
\begin{question}
Montrer par récurrence que pour tout $n \in\mathbb{N}$, $T_n$ n'est pas un entrelacement.
\end{question}
\begin{question}
En déduire que pour tout $n \in\mathbb{N}$, $T_n$ ne contient pas de cube.
