Example
\(
\def\sa#1{\tt{#1}}
\def\dd{\dot{}\dot{}}
\def\code{\mathit{code}}
\)
$abbab$ contains a grasshopper cube
however $bbaabbaa$ avoids grasshopper cubes.
$\code(a\,b\,c)=a\,a'\,b\,b'\,c\,c'$.
Additional Problem 18: Grasshopper avoidance of repetitions
\(
\)
For a string $w$ its grasshopper subsequence is any subword
of the form $w[i_1]w[i_2]\cdots w[i_k]$, where $i_{t+1}\in \{i_t+1,i_t+2\}$
for each $t\lt k$.
We can imagine a grasshopper jumping to the right
one or two positions and avoiding repetitions.
Define a grasshopper square/grasshopper cube of a string a grasshopper subsequence
which is a square/cube.
Let $A=\{a,b,c\}$ and $A'=\{a',b',c'\}$.
The elements of $A'$ are called primed.
Assume $v$ is over the alphabet $A$.
We create the word $\code(w)$ over the alphabet $A\cup A'$
using the coding:
$$a \rightarrow aa',\; b \rightarrow bb',\;
c \rightarrow cc'$$
Assume $y=\code(x)$ and $z$ is a grasshopper square in $y$.
Compute in time $O(|z|)$ a square $v$ in $x$ of size at least $|z|/2$.
For a given number $n$ and a 6-letter alphabet construct a string $w$
of length $n$ over this 6-letter alphabet avoiding grasshopper squares.
For a given number $n$ and a 3-letter alphabet construct a string
$w$ of length $n$ over this 3-letter alphabet avoiding grasshopper cubes.
References
-
M. Debski, U. Pastwa, and K. Wesek,
Grasshopper Avoidance of Patterns,
Electron. J. Comb. 23(4) 2016.