Skip to main content
2 of 4
added 13 characters in body
Yury
  • 726
  • 3
  • 9

This is not an answer but rather a long comment. I give an informal argument that suggests what the right answer should be.

Denote $k=n/3$. Let us say that a binary word $y\in\{0,1\}^{2k}$ covers a word $x\in \{0,1\}^n$ if $y$ can be obtained from $x$ by removing $k$ digits. Our goal is to find a set $S \subset \{0,1\}^{2k}$ of smallest possible cardinality that covers all words in $\{0,1\}^n$.

A lower bound on the size of $S$. We will show that every word $y$ covers approximately $2^{nH(1/3)}$ words in $\{0,1\}^n$. Therefore, the size of $|S|$ is at least $2^{n(1-H(1/3))}\approx 2^{0.08\, n}$. Here $H(t)$ is the entropy function $$H(t) = -t \log_2 t - (1-t) \log_2(1-t).$$

We can check whether $y$ covers $x$ by running a greedy algorithm that scans $x$ from left to right and finds indices $i_1 < \dots < i_{2k}$ s.t. $x_{i_r} = y_r$ for $r\in\{1,\dots, 2k\}$. For every $y$, the probability over $x$ that the algorithm finds a given set of indices $I=\{i_1,\dots, i_{2k}\}$ is $1/2^{i_{2k}}$. W.h.p. $i_{2k}\approx n$ and the number of subsets $I$ is approximately $\binom{3k}{2k} \approx 2^{H(1/3)n}$. Thus every $y$ covers approximately $2^{H(1/3)n}$ words. The set $S$ must contain at least $2^{n}/2^{H(1/3)n}\approx 2^{0.08\, n}$ words.

An upper bound on the optimal size of $S$. Note that this problem is a version of the set cover problem. Thus the size of the optimal set cover (optimal size $S$) is within a log-factor of the size of the optimal fractional cover. (The log factor is $\log 2^{3n} = O(n)$). So it suffices to get an upper bound on the size of a fractional cover to get an approximate upper bound on the size the optimal set $S$.

Warning: This is not a proof! Some statements below are not correct!

Consider the bipartite graph with words$\{0,1\}^{2k}$ on the left, and words $\{0,1\}^{n}$ on the right, in which $y$ is connected to $x$ if $y$ covers $x$. The graph is “more or less bipartite”. To be precise, it is not regular but it is very close to a regular graph (this is an informal statement that needs justification!). We will pretend nevertheless that the graph is regular. The degree of each vertex on the left is approximately $2^{H(1/3)n}$ as we computed above. Thus we get a fractional cover when we take every string of length $2k$ with weight $2^n / (2^{2k} 2^{H(1/3)n})$. The total weight of all words in the fractional cover is $2^n / (2^{H(1/3)n}) \approx 2^{0.08\, n}$.

Answer: $\approx 2^{(1-H(1/3))n}\approx 2^{0.08n}$.

Yury
  • 726
  • 3
  • 9