Long distance string problem We are considering length n strings over the alphabet S. 

The goal is to compute a set of string, M, such that for any string, x, in S^n there exists a string, y, in M such that the hamming distance between x and y is at least r.

A way of thinking of this is that we want to guarantee that for any string, we have a string in our solution M which is far away from the given string.

For a given S (with size at least 3), n and r (which may be a funciton of n, for example n/2) for many strings a needed to include in M to guarantee that for any string in S^n, we have a string in M which has a hamming distance to it of at least r.

I have a feeling this is well studied and might be related to covering designs. Can someone give me a good reference (or insight)? I would be very grateful.
Look up the concept of anticodes. Some bounds exist.

Also if you have a linear $t-$error correcting code over $GF(q)$ with length $n$ and covering radius $r$ and use homogeneity under translations by adding vectors $n-d=n-2t-1$ would seem to be your answer but I haven't checked carefully. Cohen and Litsyn have a book on covering codes.

A Simple Construction

Fix $k\geq 1$ and let $v=\lceil n/k \rceil$ and consider the strings as $GF(q)^n.$ Generate all $k-$tuples over $GF(q)$ to obtain $M=q^k$ codewords. Map these codewords to $GF(q)^n$ by expanding by $v$ for the first $k-1$ coordinates and expanding by $n-(k-1)v$ for the last coordinate. For example, let $q=3,$ $n=5$ and $k=2.$ Your codewords are
$$
\begin{array}{cc}
0&amp;0\\
0&amp;1\\
0&amp;2\\
1&amp;0\\
1&amp;1\\
1&amp;2\\
2&amp;0\\
2&amp;1\\
2&amp;2\\
\end{array}
$$

which become upon expansion with $v=4$

$$
\begin{array}{c}
0000~000\\
0000~111\\
0000~222\\
1111~000\\
1111~111\\
1111~222\\
2222~000\\
2222~111\\
2222~222\\
\end{array}
$$
Now, for any possible vector in $GF(3)^7$ there is a codeword which is quite far from it.
Namely, if there are fewer than 2 symbols for that vector in a block, there is a codeword which is at Hamming distance $v$ from it. If all 3 symbols occur, there is a codeword at Hamming distance $\geq \lfloor 2v/3 \rfloor$ from it. Since all possible constant blocks occur, for any possible vector in $GF(3)^7$ there is a codeword in this code of only $M=9$ codewords which is at Hamming distance $\geq k \lfloor (q-1)v/q \rfloor \approx n(1-\frac{1}{q}).$ Choosing $v$ a multiple of $q$ will make this more efficient.