, 2011

Throughout the solution, all the words are nonempty. For any word $R$ of length $m$, we call the number of indices $i \in \{1,2, \ldots, N\}$ for which $R$ coincides with the subword $x_{i+1} x_{i+2} \ldots x_{i+m}$ of $W$ the multiplicity of $R$ and denote it by $\mu(R)$. Thus a word $R$ appears in $W$ if and only if $\mu(R) > 0$. Since each occurrence of a word in $W$ is both succeeded by either the letter $a$ or the letter $b$ and similarly preceded by one of those two letters, we have
$$\begin{equation*} \mu(R) = \mu(R a) + \mu(R b) = \mu(a R) + \mu(b R) \tag{1} \end{equation*}$$
for all words $R$.

We claim that the condition that $N$ is in fact the minimal period of $W$ guarantees that each word of length $N$ has multiplicity $1$ or $0$ depending on whether it appears or not. Indeed, if the words $x_{i+1} x_{i+2} \ldots x_{i+N}$ and $x_{j+1} \ldots x_{j+N}$ are equal for some $1 \leq i < j \leq N$, then we have $x_{i+a} = x_{j+a}$ for every integer $a$, and hence $j-i$ is also a period.

Moreover, since $N > 2^{n}$, at least one of the two words $a$ and $b$ has a multiplicity that is strictly larger than $2^{n-1}$.

For each $k = 0, 1, \ldots, n-1$, let $U_{k}$ be a subword of $W$ whose multiplicity is strictly larger than $2^{k}$ and whose length is maximal subject to this property. Note that such a word exists in view of the two observations made in the two previous paragraphs.

Fix some index $k \in \{0,1, \ldots, n-1\}$. Since the word $U_{k} b$ is longer than $U_{k}$, its multiplicity can be at most $2^{k}$, so in particular $\mu\left(U_{k} b\right) < \mu\left(U_{k}\right)$. Therefore, the word $U_{k} a$ has to appear by (1). For a similar reason, the words $U_{k} b$, $a U_{k}$, and $b U_{k}$ have to appear as well. Hence, the word $U_{k}$ is ubiquitous. Moreover, if the multiplicity of $U_{k}$ were strictly greater than $2^{k+1}$, then by (1) at least one of the two words $U_{k} a$ and $U_{k} b$ would have multiplicity greater than $2^{k}$ and would thus violate the maximality condition imposed on $U_{k}$.

So we have $\mu\left(U_{0}\right) \leq 2 < \mu\left(U_{1}\right) \leq 4 < \ldots \leq 2^{n-1} < \mu\left(U_{n-1}\right)$, which implies in particular that the words $U_{0}, U_{1}, \ldots, U_{n-1}$ have to be distinct. As they have been proved to be ubiquitous as well, the problem is solved.