Corrigé CCINP 2026 Informatique MPI — Partie II (II.2) (Q30 à Q41) : Le mot infini de Thue-Morse : carrés, cubes, entrelacements

Dans les définitions de carré et de cube, $w$ est implicitement non vide : le mot vide est un carré et un cube, facteur de tout mot. « Contenir un carré » signifie donc contenir un facteur $ww$ avec $w\ne \epsilon$. Par Q28, $T_n=u_n$ est un préfixe de $\mathbb{T}$, et $\mathbb{T}=t_0{t}_1{t}_2\cdots$

Q30. Il suffit de traiter les mots de longueur exactement $4$ : un mot plus long contient son préfixe de longueur $4$. Soit $m=abcd$. Si $a=b$, $b=c$ ou $c=d$, $m$ contient un carré $xx$ ($x$ une lettre). Sinon, l'alphabet n'ayant que deux lettres, $c=a$ ($c\ne b$ et $a\ne b$) et $d=b$ ($d\ne c=a$), donc $m=abab=(ab)(ab)$ est un carré. Dans tous les cas, $m$ contient un carré. La borne est optimale : $010$ et $101$ sont sans carré (énumération exhaustive exécutée : $2$ mots sans carré de longueur $3$, aucun de longueur $4$ ou $5$).

Q31. La fonction auxiliaire récursive coupe k l rend le couple (les $k$ premiers éléments de l, le reste), en gardant l'ordre des lettres ; on l'appelle avec $k=|m|/2$ (la récursivité demandée est portée par cette fonction locale).

let divise_mot m =
  let rec coupe k l =
    if k = 0 then ([], l)
    else match l with
      | [] -> failwith "impossible : k <= |l|"
      | x :: q -> let (a, b) = coupe (k - 1) q in (x :: a, b)
  in
  coupe (List.length m / 2) m

Correction par récurrence sur $k$ : si coupe (k-1) q rend les $k-1$ premiers éléments de q et le reste, alors (x :: a, b) rend les $k$ premiers de x :: q et le reste. Le cas [] ne se produit pas puisque $k⩽|l|$ est préservé ; il est écrit pour que le filtrage soit exhaustif. Terminaison : $k$ décroît. Coût : $O(|m|)$ (List.length, au programme, puis $|m|/2$ appels). Exécuté : divise_mot [1;1;0;1;1;0] rend ([1;1;0], [1;1;0]), et le mot vide donne ([], []).

Q32.

let est_carre m =
  List.length m mod 2 = 0 &&
  (let (a, b) = divise_mot m in a = b)

$m$ est un carré si et seulement si $|m|$ est pair et ses deux moitiés sont égales ; l'opérateur && étant paresseux, divise_mot n'est appelée que sur un mot de longueur paire, et un mot impair rend false (et non une exception). L'égalité structurelle = compare les deux listes élément par élément, en $O(|m|)$. Exécuté : true pour $\epsilon$, $00$, $110110$, $0101$ ; false pour $01$, $010$, $0110$, $110110110$.

Q33. Par Q27, $t_{2k}{t}_{2k+1}=t_k{\bar{t}}_k$ : chaque bloc $t_{2k}{t}_{2k+1}$ de $\mathbb{T}$ vaut $01$ ou $10$ et contient deux lettres différentes. Un facteur de longueur $3$, $t_j{t}_{j+1}{t}_{j+2}$, contient un bloc entier : $t_j{t}_{j+1}$ si $j$ est pair, $t_{j+1}{t}_{j+2}$ si $j$ est impair. Il contient donc deux lettres différentes et n'est ni $000$ ni $111$.