CLR cover
Previous problem

Problem 17: Langford words

Next problem
\( \def\sa#1{\tt{#1}} \)

A Langford word of order $n$, for a positive integer $n$, is a word over the alphabet $A_n=\{\sa{1},\sa{2},\ldots, n\}$ satisfying, for each $i\in A_n$, the properties:

  1. The letter $i$ appears exactly twice in the word.
  2. Consecutive occurrences of $i$ are at distance $i+1$.
Langford words have a definition very similar to that of Skolem words (Problem 16) but the small change in the distance makes a big difference.

If $igi$ is a factor of a Langford word the gap word $g$ does not contain letter $i$ and $|g|=i$. For example, $\sa{312132}$ is a Langford word of order $3$ and $\sa{41312432}$ a Langford word of order $4$.

Discuss for which positive integer $n$ there exists a Langford word of order $n$ and show how to build it when possible.
Discuss according to $n$ modulo $4$.

References

  • J. Berstel. Langford strings are square free. Bulletin of the EATCS, 37:127-128, 1989.