CLR cover
Previous problem

Problem 16: Skolem words

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

A Skolem 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$.
Skolem words have a definition very similar to that of Langford words (Problem 17) but the small change in the distance makes a big difference.

If $igi$ is a factor of a Skolem word, the gap word $g$ does not contain the letter $i$ and $|g|=i-1$. For example, $\sa{11}$ is an obvious Skolem word of order $1$, $\sa{23243114}$ a Skolem word of order $4$ and $\sa{4511435232}$ a Skolem word of order $5$. But a mere checking shows there is no Skolem word of order $2$ or of order $3$.

Discuss for which positive integer $n$ there exists a Skolem word of order $n$ and design an algorithm to build it when possible.
Discuss according to $n$ modulo $4$.

References

  • T. Skolem. On certain distributions of integers in pairs with given differences. Mathematica Scandinavica, 5:57-68, 1957.