## Example

\(
\def\sa#1{\tt{#1}}
\def\dd{\dot{}\dot{}}
\)

The word $\sa{0110}$ is dense but $\sa{0101}$ is not.
The longest binary perfect words are $\sa{011001010}$ and its complement
$\sa{100110101}$, they have length $9$.
However, on the ternary alphabet the
word $\sa{0120022110}$ of length $10$ is perfect.

#
Problem 69: Perfect Words

A word of length is called *dense* if it has the
largest number of (distinct) factors among words of the same length on the
same alphabet.
A word is said to be *perfect* if all its prefixes are dense.
Note that each prefix of a perfect word is also perfect.

There are only finitely many binary perfect words, but the situation changes
dramatically for larger alphabets.

Show how to construct in linear time a ternary perfect word of any given length.
Prove also the existence of an infinite perfect ternary word.

Consider Hamiltonian and Eulerian cycles in de Bruijn automata.

## References

D. Repke and W. Rytter. On semi-perfect de Bruijn words. *Theor.
Comput. Sci.*, **720**:55-63, 2018.
N. Vörös. On the complexity measures of symbol-sequences. In A. Iványi,
editor, *Conference of Young Programmers and Mathematicians*, pages
43-50, Budapest, 1984. Faculty of sciences, Eötvös Loránd University