CLR cover

Additional Problem 1: Short Distinguishing Subsequence

\( \def\SMot{\mathit{Subs}} \)

The problem consider distinguishing subsequence between two different binary words (see Problem 51). Denoting by $\SMot(x)$ the set of subsequences of a word $x$, a word $z$ is said to distinguish $x$ and $y$, $x\neq y$, if it is a subsequence of only one of them, that is, $z\in \SMot(x)\Leftrightarrow z\notin \SMot(y)$.

Construct a distinguishing subsequence of length at most $\lceil (n+1)/2 \rceil$ for two distinct binary words of the same length $n$.

In fact, the above bound is optimal.

For each $n\gt 0$, construct two distinct binary words of length $n$ that do not have a distinguishing subsequence of length smaller than $\lceil (n+1)/2 \rceil$.

References