CLR cover

Problem 143: Avoiding grasshopper repetitions

\( \)

The problem deals with grasshopper subsequences of words. A grasshopper subsequence of a word $x$ is a word of the form $x[i_1]x[i_2]\cdots x[i_k]$, where $i_t$ is a position on $x$ satisfying $i_{t+1}\in \{i_t+1,i_t+2\}$, for each $t$, $0\lt t \lt k$. We can imagine a grasshopper jumping to the right one or two positions.

The goal of the problem is related to long words that avoid grasshopper squares and grasshopper cubes over alphabets of size 3 and 6, respectively.

Let $A=\{\sa{a},\sa{b},\sa{c}\}$ and $A'=\{\sa{a'},\sa{b'},\sa{c'}\}$. The elements of $A'$ are called ''primed'' letters. For a word $v\in A^*$, the word $\Phi(v)$ over the alphabet $A\cup A'$ is defined using the coding (morphism): $$\sa{a} \rightarrow \sa{aa'},\; \sa{b} \rightarrow \sa{bb'},\; \sa{c} \rightarrow \sa{cc'}.$$

Let $x\in A^+$, $y=\Phi(x)$ and $z$ be a grasshopper square in $y$. Show how to compute in time $O(|z|)$ a (standard) square $v$ in $x$ of length at least $|z|/2$.

For a given integer $n\gt 0$, build a word of length $n$ over a 6-letter alphabet that avoids grasshopper cubes.

References