Given an alphabet $S={a_1,\cdots,a_m}$, we consider the words of length $n$, $S^n$.
We call two words $b_1b_2\cdots b_n$ and $c_1c_2\cdots c_n$ are connected if $b_i=c_i$ for some $i$.
We consider $P\subseteq S^n$ with the following property: for any $r\in S^n$, there exists $p\in P$ such that $r$ and $p$ are not connected.
What is the minimal size $u_m(n)$ of $P$ to have the wanted property? Is there an explicit construction?
For $m=2$, it shall be $u_2(n)=2^{n}$. What about general $m$?
For $m=3$ and $n=2$, we only need 3 elements, $a_1a_1$, $a_2a_2$ and $a_3a_3$. Because for any $b_1b_2$, there is $i$ such that $b_1\neq a_i$ and $b_2\neq a_i$. Then $a_ia_i$ is not connected with $b_1b_2$. So $u_3(2)=3$.
This seems like a standard error correcting code question.