# Smallest set of balls under hamming distance that covers all $n$-bit strings

Suppose we defined a set $$S = \{x\mid0 \leq x \leq 2^n-1\}$$. Notice that all element in $$S$$ can be represented with a $$n$$-bit binary string. Now consider subset $$S_i$$ such that,

$$S_{y_i} = \{y \in S\mid d(y,y_i) \leq t\},$$

where $$y_i$$ is the $$i$$th element of $$S$$ and $$d(y_j,y_i)$$ is the hamming distance between the binary representation of $$y_j$$ and $$y_i$$ and $$t < n$$. Obviously, $$S_{y_i} \subset S$$.

Consider the family $${\Phi = \{S_0, S_1, \ldots, S_{2^n-1}\}}$$. Find $${\phi \subset \Phi}$$ with smallest cardinality, so that the union of the all elements in $$\phi$$ is equal to original set $$S$$ (notice that, each element of $$\phi$$ is a subset of $$S$$).

I was not be able to solve. However, I believe it is possible to find $$\phi$$ with an efficient algorithm rather than using an exhaustive search.

Edit: An example-

Assume $$n =3$$ and $$t = 1$$

Then $$S = \{0, 1, 2, 3, 4, 5, 6, 7\}$$

So, $$S_0 = \{y \in S\ |\ d(y,0) \leq 1;\} = \{0, 1, 2, 4\}$$

Similarly, $$S_1 = \{0, 1, 3, 5\}$$; $$S_2 = \{0, 2, 3, 6\}$$; $$S_3 = \{1, 2, 3, 7\}$$; $$S_4 = \{0, 4, 5, 6\}$$; $$S_5 = \{1, 4, 5, 7\}$$; $$S_6 = \{3, 4, 6, 7\}$$; $$S_7 = \{3, 5, 6, 7\}$$;

So, $$\Phi = \{S_0, S_1, S_2, S_3, S_4, S_5, S_6, S_7\}$$; Now, for this case the $$\phi = \{S_2, S_5\}$$ as $$S_2 \cup S_5 = S$$

• Can you share the context in which you encountered this task; and improve the title to make it more descriptive? – D.W. Apr 11 at 7:42
• To be honest, this is the exact problem that I am working on. This is not a part of a big problem. – user3862410 Apr 11 at 7:56