Shortlist 2011, C6¶
Domaine : Combinatoire · Difficulté : ★★★★☆ · Proposé par : non indiqué
Concepts : Double comptage · Principe extrémal
Solution officielle : Shortlist officielle 2011 (avec solutions), p. 37 (page 38 du PDF)
Énoncé¶
Let \(n\) be a positive integer and let \(W = \ldots x_{-1} x_0 x_1 x_2 \ldots\) be an infinite periodic word consisting of the letters \(a\) and \(b\). Suppose that the minimal period \(N\) of \(W\) is greater than \(2^n\).
A finite nonempty word \(U\) is said to appear in \(W\) if there exist indices \(k \leq \ell\) such that \(U = x_k x_{k+1} \ldots x_\ell\). A finite word \(U\) is called ubiquitous if the four words \(Ua\), \(Ub\), \(aU\), and \(bU\) all appear in \(W\). Prove that there are at least \(n\) ubiquitous finite nonempty words.
Indices : les idées clés
- Multiplicité : \(\mu(R)\) compte les occurrences de \(R\) sur une période ; par double comptage, \(\mu(R) = \mu(Ra) + \mu(Rb) = \mu(aR) + \mu(bR)\).
- Période minimale : tout mot de longueur \(N\) a une multiplicité \(0\) ou \(1\), et l'une des lettres a une multiplicité supérieure à \(2^{n-1}\).
- Mots extrémaux : pour chaque \(k < n\), un mot \(U_k\) de longueur maximale parmi ceux de multiplicité \(> 2^k\) est omniprésent, et \(2^k < \mu(U_k) \leq 2^{k+1}\), donc les \(U_k\) sont distincts.
Solutions
Les solutions ci-dessous suivent la solution officielle de la Shortlist 2011 (une solution et deux remarques).
Solution¶
Dans toute la solution, les mots sont non vides. Pour un mot \(R\) de longueur \(m\), on appelle multiplicité de \(R\), notée \(\mu(R)\), le nombre d'indices \(i \in \{1, 2, \ldots, N\}\) tels que \(R\) coïncide avec le sous-mot \(x_{i+1} x_{i+2} \ldots x_{i+m}\) de \(W\). Un mot \(R\) apparaît dans \(W\) si et seulement si \(\mu(R) > 0\). Comme chaque occurrence d'un mot dans \(W\) est suivie de la lettre \(a\) ou de la lettre \(b\), et de même précédée de l'une de ces deux lettres, on a
pour tout mot \(R\).
La condition que \(N\) est la période minimale de \(W\) garantit que chaque mot de longueur \(N\) a une multiplicité égale à \(1\) ou \(0\), selon qu'il apparaît ou non. En effet, si les mots \(x_{i+1} x_{i+2} \ldots x_{i+N}\) et \(x_{j+1} \ldots x_{j+N}\) sont égaux pour \(1 \leq i < j \leq N\), alors \(x_{i+a} = x_{j+a}\) pour tout entier \(a\), et \(j - i\) est aussi une période.
De plus, comme \(N > 2^n\), l'un au moins des deux mots \(a\) et \(b\) a une multiplicité strictement supérieure à \(2^{n-1}\).
Pour chaque \(k = 0, 1, \ldots, n - 1\), soit \(U_k\) un sous-mot de \(W\) dont la multiplicité est strictement supérieure à \(2^k\) et dont la longueur est maximale sous cette condition. Un tel mot existe d'après les deux observations des paragraphes précédents.
Fixons un indice \(k \in \{0, 1, \ldots, n - 1\}\). Comme le mot \(U_k b\) est plus long que \(U_k\), sa multiplicité est au plus \(2^k\), donc en particulier \(\mu(U_k b) < \mu(U_k)\). Par (1), le mot \(U_k a\) doit donc apparaître. Pour une raison analogue, les mots \(U_k b\), \(aU_k\) et \(bU_k\) doivent aussi apparaître. Le mot \(U_k\) est donc omniprésent. De plus, si la multiplicité de \(U_k\) était strictement supérieure à \(2^{k+1}\), alors par (1) l'un au moins des mots \(U_k a\) et \(U_k b\) aurait une multiplicité supérieure à \(2^k\), ce qui contredirait la maximalité de \(U_k\).
On a donc \(\mu(U_0) \leq 2 < \mu(U_1) \leq 4 < \cdots \leq 2^{n-1} < \mu(U_{n-1})\), ce qui implique en particulier que les mots \(U_0, U_1, \ldots, U_{n-1}\) sont distincts. Comme ils sont omniprésents, le problème est résolu. \(\blacksquare\)
Remarques¶
Remarque 1. Il y a une construction simple pour obtenir des mots omniprésents à partir de mots qui apparaissent avec une multiplicité au moins \(2\). Partant d'un tel mot \(U\), on prolonge l'une de ses occurrences dans \(W\) vers l'avant et vers l'arrière tant que sa multiplicité reste la même ; on obtient un mot qu'on peut appeler le prolongement omniprésent \(p(U)\) de \(U\).
Il existe plusieurs variantes de la seconde moitié de la solution utilisant cette notion. Par exemple, on peut prendre tous les mots omniprésents \(U_1, U_2, \ldots, U_\ell\), rangés par multiplicité croissante, et prouver que \(\mu(U_i) \leq 2^i\) pour \(i \in \{1, 2, \ldots, \ell\}\). En effet, si \(i\) était un contre-exemple minimal, des arguments analogues à ceux ci-dessus montreraient que le prolongement omniprésent de l'un des mots \(U_i a\), \(U_i b\), \(aU_i\) ou \(bU_i\) contredit la définition de \(U_i\). La multiplicité de l'une des deux lettres \(a\), \(b\) est strictement supérieure à \(2^{n-1}\) ; en passant encore aux prolongements omniprésents, on obtient \(2^{n-1} < \mu(U_\ell) \leq 2^\ell\), d'où \(\ell \geq n\), comme voulu.
Remarque 2. La borne \(n\) du nombre de mots omniprésents n'est pas optimale, mais elle est proche d'une borne optimale au sens suivant : il existe une constante universelle \(C > 0\) telle que, pour tout entier \(n \geq 1\), il existe un mot périodique infini \(W\) de période minimale supérieure à \(2^n\) mais ayant moins de \(Cn\) mots omniprésents.