Exercice 9

1. Les mots de longueur $1$ sont $a$ et $b$, et ceux de longueur $2$ sans facteur $aa$ sont $ab$, $ba$ et $bb$ : $u_{1} = 2$ et $u_{2} = 3$. Soit $n \geqslant 1$, et $w$ un mot de longueur $n + 2$ sans facteur $aa$. On distingue selon sa dernière lettre.

• Si $w$ se termine par $b$, alors $w = w'b$, où $w'$ est un mot de longueur $n + 1$ sans facteur $aa$ ; réciproquement, pour tout tel mot $w'$, le mot $w'b$ n'a pas de facteur $aa$, puisqu'un tel facteur se trouverait dans $w'$. Il y a $u_{n+1}$ tels mots.

• Si $w$ se termine par $a$, son avant-dernière lettre est $b$, et $w = w''ba$, où $w''$ est un mot de longueur $n$ sans facteur $aa$ ; réciproquement, tout mot $w''ba$ de ce type convient. Il y a $u_{n}$ tels mots.

Les deux cas sont disjoints, et la proposition 2 (i) donne $$\boxed{u_{n+2} = u_{n+1} + u_{n} \text{ pour tout } n \geqslant 1}$$ Comme $u_{1} = 2 = F_{3}$ et $u_{2} = 3 = F_{4}$, une récurrence double montre que $u_{n} = F_{n+2}$ pour tout $n \geqslant 1$ : si $u_{n} = F_{n+2}$ et $u_{n+1} = F_{n+3}$, alors $u_{n+2} = F_{n+3} + F_{n+2} = F_{n+4}$. $$\boxed{u_{n} = F_{n+2} \text{ pour tout } n \geqslant 1}$$ La formule vaut aussi pour $n = 0$, si l'on convient que le mot vide compte : $u_{0} = 1 = F_{2}$.

2. Un mot $w = w_{1}\cdots w_{n}$ n'a pas de facteur $ab$ si et seulement si aucune lettre $a$ n'est suivie, plus loin, d'une lettre $b$. En effet, s'il existe $i < j$ tels que $w_{i} = a$ et $w_{j} = b$, notons $j'$ le plus petit indice $j' > i$ tel que $w_{j'} = b$ : les lettres $w_{i}$, …, $w_{j'-1}$ sont des $a$, et $w_{j'-1}w_{j'} = ab$ est un facteur. Les mots sans facteur $ab$ sont donc les mots $b^{k}a^{n-k}$, formés de $k$ lettres $b$ suivies de $n - k$ lettres $a$, avec $k \in \llbracket 0\,,n \rrbracket$, et ils sont deux à deux distincts. $$\boxed{n + 1 \text{ mots sans facteur } ab}$$ Pour $aab$, on sépare les mots qui n'ont pas de facteur $aa$, au nombre de $u_{n} = F_{n+2}$, et ceux qui en ont un. Soit $w$ un mot sans facteur $aab$ qui contient le facteur $aa$, et $i$ la position de la première occurrence de ce facteur. Toutes les lettres qui suivent sont des $a$ : sinon, la première lettre $b$ située après la position $i$ serait précédée de deux $a$ au moins. Le mot $w$ s'écrit donc $a^{n}$, ou bien $vba^{m}$ avec $m \in \llbracket 2\,,n - 1 \rrbracket$ et $v$ un mot de longueur $n - 1 - m$ sans facteur $aa$ ; réciproquement, ces mots n'ont pas de facteur $aab$ et contiennent $aa$. Pour $n \geqslant 2$, il y en a donc, en posant $j = n - 1 - m$ et avec $u_{0} = F_{2} = 1$, $$1 + \sum_{m=2}^{n-1} u_{n-1-m} = 1 + \sum_{j=0}^{n-3} F_{j+2} = 1 + \big(F_{n+1} - 2\big) = F_{n+1} - 1,$$ puisque $\sum_{i=0}^{N} F_{i} = F_{N+2} - 1$ : les égalités $F_{i} = F_{i+2} - F_{i+1}$ donnent une somme télescopique (chapitre 3, proposition 3), égale à $F_{N+2} - F_{1}$. Au total, $F_{n+2} + F_{n+1} - 1 = F_{n+3} - 1$, valeur qui reste juste pour $n = 1$, où les deux mots conviennent. $$\boxed{F_{n+3} - 1 \text{ mots sans facteur } aab}$$ Les trois formules ont été vérifiées par énumération pour $n \leqslant 14$. Pour $n = 4$, on trouve $8$, $5$ et $12$ mots.

3. À une partie $A$ de $\llbracket 1\,,n \rrbracket$, on associe le mot $w_{1}\cdots w_{n}$ défini par $w_{i} = a$ si $i \in A$ et $w_{i} = b$ sinon : c'est l'indicatrice de $A$, écrite avec les lettres $a$ et $b$, et cette application est une bijection de $\mathcal{P}\big(\llbracket 1\,,n \rrbracket\big)$ sur $\{a, b\}^{n}$ (démonstration de la proposition 3). La partie $A$ contient deux entiers consécutifs $i$ et $i + 1$ si et seulement si $w_{i}w_{i+1} = aa$. La bijection envoie donc les parties cherchées sur les mots sans facteur $aa$. $$\boxed{F_{n+2} \text{ parties de } \llbracket 1\,,n \rrbracket \text{ sans deux entiers consécutifs}}$$

4. La fonction suivante calcule $u_{n}$ par la récurrence de la question 1, à partir de $u_{0} = 1$ et $u_{1} = 2$.

def u(n):
    a, b = 1, 2           # a = u_k, b = u_(k+1), pour k = 0
    for _ in range(n):    # on passe de k a k + 1
        a, b = b, a + b
    return a

print(u(20))              # affiche 17711

Les résultats d'un candidat forment un mot de longueur $20$ sur l'alphabet $\{0, 1\}$, et la condition « jamais deux bonnes réponses consécutives » signifie que $11$ n'en est pas un facteur : il y a $u_{20} = F_{22} = 17\,711$ listes de résultats possibles. Si les $17\,712$ candidats avaient des résultats deux à deux distincts, l'application qui associe à chaque candidat sa liste serait une injection d'un ensemble à $17\,712$ éléments dans un ensemble à $17\,711$ éléments, ce qu'interdit le principe des tiroirs (chapitre 2, théorème 2). $$\boxed{\text{Oui : deux candidats au moins ont exactement les mêmes résultats}}$$ À retenir. Les mots sans facteur $aa$ reviennent sous de nombreux déguisements : parties sans entiers consécutifs, pavages d'une bande par des dominos et des carrés, montées d'un escalier une ou deux marches à la fois. Chaque fois, la décomposition selon la fin de l'objet donne la récurrence de Fibonacci. C'est cette décomposition, et non la formule, qu'il faut retenir.