Puzzle on deleting k bits from binary vectors of length 3k Consider all $2^n$ different binary vectors of length $n$ and assume $n$ is an integer multiple of $3$.  You are allowed to delete exactly $n/3$ bits from each of the binary vectors, leaving vectors of length $2n/3$ remaining. The number of distinct vectors remaining depends on which bits you delete. Assuming your aim is to leave as few remaining different vectors as possible, how few can you leave as a function of $n$?
Example, $n=3$.  You can leave only the two vectors $11$ and $00$.
Following comments at the math.se site (in particular by Jack D'Aurizio), in general for larger values of $n$ you can replace any block of three consecutive bits by either $00$ or $11$.  This gives an upper bound of $2^{n/3}$. Is this in fact the correct answer?
Now I have some code to solve small instances, we can start to fill in a table of optimal results. We use the notation $H(n,b)$ to indicate the smallest number of distinct vectors that results from starting with all vectors of length $n$ and removing $b$ from each.
$$12 \leq H(15,5) \leq17$$
$$H(12,4) = 10$$
For $n=10$ and $b = 1,2,3,4$ we have $\leq140,\leq 31,10, 4$
For $n=9$ and $b = 1,2,3,4$ we have $70,18,6,2$
For $n=8$ and $b = 1,2,3$ we have $40,10,4$
For $n=7$ and $b = 1,2,3$ we have $20,6,2$
For $n=6$ and $b = 1,2$ we have $12,4$
For $n=5$ and $b = 1,2$ we have $6,2$
$$H(4,1)  = 4, H(3,1) = 2, H(2,1) = 2$$
If we only allow symmetric solutions then $H(10,2)=32$. This implies (assumnig no error in the calculations) that for some instances there may be no symmetric optimal solutions as we already have $H(10,2) \leq 31$.
 A: I think it may be helpful and/or intersting to consider the problem for fractions other than $1/3$.
Specifically, if $n$ is a multiple of $q$, let $f(p/q,n)$ be the minimal size of a set of $n- (p/q)n$ bit strings such that deleting $(p/q)n$ bits from each $n$-bit string produces an element of the set. Then set
$$g(p/q) = \lim _{n\to \infty} \frac{\log f\left(\frac{p}{q},n\right)}{n}$$
The limit exists because, by the divide-into-independent-blocks argument, any particular value is a bound for the $\lim\sup$.
It is clear that $g$ is monotonic. It's not immediately obvious to me if we can prove that $g$ is continuous.
Clearly $g(x)=0$ for $x \geq 1/2$.
For a simple upper bound on $g$ for $x<1/2$, we can assume with the loss only of a constant that there are fewer $0$s than $1$s. Then divide the $n$ bits into $q$ equally sized parts, and delete all the $0$s in the $2p$ parts with the fewest ones. This takes $2^{ (1-2p/q)n }$, giving an upper bound $g(x) \leq (1-2x) \log 2$. 
Thanks to Brendan McKay and Yury,  we have a lower bound on $g$. If I understand this bound correctly, it is that $g(x) \geq \log 2 + x  \log x + (1-x) \log(1-x)$. (We can easily check that the maximal term in the $x=1/3$ case remains maximal for all $0<x<1/2$.)
Specific examples, like, Adam Goucher's, can give us tighter upper bounds for specific values of $x$.
A: I can, at least, answer your question 'Is this in fact the correct answer?' with an affirmative 'no'.
Specifically, we can replace the upper bound $2^{n/3} \approxeq 1.26^n$ with the slightly better bound $6^{n/9} \approxeq 1.22^n$ by applying the same 'separate into independent blocks' construction to the following (conjecturally optimal) covering set for $n = 9$:
$$\{000000, 111111, 111000, 000111, 001100, 110011\}$$
Clearly, $2^{n/3}$ is still optimal for $n = 3$ and indeed (by exhaustive search) $n = 6$.
A: This is not an answer but rather a long comment. I give an informal argument that suggests what the right answer should be. The proof of the lower bound is rigorous, the proof of the upper bound is not.
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).$$
Let us fix $y$ and count the number of words $x$ that $y$ covers. To this end, we consider an algorithm that checks whether $y$ covers $x$. This is just a simple 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\}$: $i_1$ is the first index s.t. $x_{i_1} = y_1$, $i_2$ is the first index after $i_1$ s.t. $x_{i_2} = y_2$ and so on. The algorithm terminates when it defines $i_{2r}$. The algorithm succeeds and finds $i_1< \dots < i_{2r} \leq n$ if and only if $y$ covers $x$. 
Let $I_y(x) = \{i_1, \dots, i_{2k}\}$ for given words $x$ and $y$. Note that if $I_y(x') = I_y(x'')$ then the algorithm performs exactly the same steps. In particular, the first $i_{2r}$ digits in $x'$ and $x''$ are equal. Also for every set $I\subset \{1,\dots, n\}$ of size $2k$, there is a word $x$ s.t. $I_y(x) = I$. 
Therefore, the number of words $x$ covered by $y$ is equal to sum over all possible values of $j\equiv i_{2r}$ the number of subsets of $\{1,\dots, j\}$ of size $2k$ times the number of possibilities for digits at positions $j+1,\dots, n$.
$$\sum_{j=2k}^{n} \binom{j}{2k} 2^{n-j} \approx \sum_{j=2k}^{n} 2^{jH(2k/j)} 2^{n-j}\approx 2^n \sum_{j=2k}^n 2^{(\frac{j}{2k} (H(2k/j)-1))\cdot 2k} = 2^n \sum_{j=2k}^n 2^{f(2k/j)\cdot 2k}.$$
where $f(t) = (H(t)-1)/t$. The function $f(t)$ attains its maximum on $[2/3,1]$ when $t=2/3$. Thus the number of words covered by $y$ is approximately 
$$2^{n + 2 f(2/3)k} = 2^{nH(1/3)}.$$
We conclude that 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 of $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}$.
A: Here is an exponential lower bound.  We begin by determining exactly how many strings $Y$ of length $n$ can be reduced to a given string $X=x_1x_2\cdots x_k$.  In general $y$ might contain many copies of $X$, but it contains exactly one left-most copy of $X$; that is, the first $x_1$ then the first $x_2$ and so on. The strings with $X$ as a left-most substring form a regular language of simple form.  For example, if $X=101$ then the language is $0^*1 \cdot 1^*0 \cdot 0^*1 \cdot (0+1)^*$. The generating function for $0^*1$ and $1^*0$ is $z/(1-z)$ while the generating function for $(0+1)^*$ is $1/(1-2z)$.
Therefore, the number of $Y$s that contain $X$ is independent of the structure of $X$ and is the coefficient of $z^n$ in $z^k (1-z)^{-k} (1-2z)^{-1}$, namely
$$N(n,k) = \sum_{i=0}^{n-k} 2^i\binom{n-i-1}{k-1},$$
which I think doesn't have a closed form.  
Therefore, a lower bound for the question is $2^n/N(n,k)$.
For $k=2n/3$, the largest term in the sum is the first one, and the following terms are close to a geometric progression with ratio $2/3$.  This gives
$$ N(n,2n/3) = (2 + O(1/n)) \binom{n}{2n/3},$$
giving a lower bound of 
$$ (1+o(1)) \frac{\sqrt{\pi n}}{3} \left(\frac{2^{5/3}}{3}\right)^n. $$
Note that $2^{5/3}/3\approx 1.05826737$.
I think it is most unlikely that this is best possible.
A: If a vector has $d$ one-entries, and $d\leq n/2$, then delete as many ones as you can, (and further zeros if necessary).  Conversely, if a vector has more one entries than zero entries, delete as many zeros as you can,
(and further ones if necessary).
Any remaining vector of the first type will have $\max(d-n/3,0)\leq n/6$ ones.
The number of such vectors with exactly $n/6$ ones in $2n/3$ positions 
is $\binom{2n/3}{n/6}$. For the final sum, one needs to sum over bimomial coefficients
$2 \sum_{i=0}^{n/6} \binom{2n/3}{i}$ and such a sum can be approximated:
Note that the largest entry, with $d=n/6$ gives by far the greatest contribution.
The binomial coefficient in this region can be approximated by
 $\binom{k}{l}=2^{k H(l/k)+o(k)}$, where $H$ denotes the entropy function
$H(x)=\frac{-x \log x-(1-x)\log (1-x) }{\log 2}$, 
(for $x\in [0,1]$, and $\log $ is the natural logarithm).
Edit: In view of Yuri's comment, I correct this:
(Thank you, Yuri!)
As $H(1/4)$ is about $0.811$, 
this is about $2^{2n/3 \times 0.811...+o(1)}=2^{0.54\ldots n}$.
This upper bound is certainly weaker than the bound $2^{n/3}$, but uses a quite different method. It would be interesting to see, whether the "optimum" uses a deterministic construction, or a random construction (like Shannon's bounds in coding theory), or a combination of methods.
Some explanation why the method above gives some saving over the trivial $2^{2n/3}$: most of the original vectors have about $n/2+ O(\sqrt{n})$ zero and one entries. Going away from this symmetric centre reduces (by the binomial distribution) the number
of possibilities. In other words the tail of this distibution is small.
A: This answer is an elaboration on the idea of Christian Elsholtz. Like that answer, this answer does not beat $2^{n/3}$.
As noted by Christian, by symmetry it suffices to deal with vectors that contain at most $n/2$ ones. By left-right symmetry, it suffices to deal with vectors of at most $n/4$ ones among the first $n/2$ positions. Remove the first $n/3$ ones. That leaves a vector of length $2n/3$ with at most $n/6$ ones that starts with a string of $n/4$ zeros. There are approximately $\binom{2n/3-n/4}{n/6}\approx 2^{5n/12\times H(2/5)}=2^{0.40455n}$, which is still worse than $2^{n/3}$.
One can improve this a bit. Namely, after deleting all the ones from the first half of string, we choose whether to remove ones from third or four quarter. It appears that in the worse case (non-rigorously!) we end up with a string of length $2n/3$ that contains $n/6$ ones among which $n/24$ are in the third quarter and $n/8$ are in the fourth quarter. There are approximately $\binom{n/6}{n/24}\binom{n/4}{n/8}\approx 2^{0.385n}$ of them.
A: For each $\ n=9\cdot m + 3\cdot k\ $ one gets a bound of $\ 6^m\cdot 2^k\ =\ 6^{\frac n9}\cdot 2^k\ $ for every $\ m=0\ 1\ \ldots\ $ and $\ k\in\{0\ 1\ 2\}$.
A hand justification below of the result by @Adam P. Goucher (and a computer) indicates a further possible progress along a similar line. I'll explicitly associate binary sequences of length $\ 9\ $ with the respective Goucher's sequences.
I'll provide a simpler derivation below, and will leave the previous one at the bottom.

Let $\ b_0\ldots b_8\ $ be a bit string.
Case A:   Let $\ b_0b_1b_2b_3\ $ have (at least) three same bits, say $\ x$.   Then $\ b_4b_5b_6b_7b_8\ $ bits contain (at least) three bits say $\ y$ (the majority of five),   where values $\ x\ y\ $ are different or the same. In either case by leaving the two groups of three bits we get one of the four strings of length 6:
$$ 000000\quad 000111\quad 111000\quad 111111$$
Case A':   Consider $\ b_5b_6b_7b_8\ $ -- everything is symmetric.
From now on let's assume that the distribution of bits in $\ b_0b_1b_2b_3\ $ is two bits of each, and the same for $\ b_5b_6b_7b_8$.
Case B:   $b_3=b_5$,   and say $\ b_3=b_5=x$.   Then remove one of bits of value $\ 1-x\ $ from $\ b_0b_1b_2\ $ and from $\ b_6b_7b_8\ $ and remove also bit $\ b_4$.   We are left with one of the strings:
$$ 001100\qquad 110011$$
Case C:   $b_3=b_4\ne b_5$,   and say $\ b_3=x$.   Then remove the one bit of value $\ x\ $ from $\ b_0b_1b_2$,   and the two more bits $\ x\ $ from $\ b_6b_7b_8$.   We are left with one of the two 6-strings as the above.
Case C':   $b_3\ne b_4= b_5$ -- symmetry.
END of PROOF 

(Back to the old argument)
Let's refer to the six Goucher's sequences as of the type $\ 6\ \ 3\!+\!3\ \ 2\!+\!2\!+\!2$,   where each type addresses the consecutive two sequences by Goucher.
Case 1: one of the bit values of a binary sequence $\ b_0\ldots b_8\ $ occurs at least $\ 6\ $ times. Then we may leave a six of them to produce a 6-sequence of type $\ 6$.   Now we may restrict ourselves to the cases when each bit value of a 9-sequence $\ b_0\ldots b_8\ $ occurs $\ 4\ $ or $\ 5\ $ times.
Let the bit value $\ x\ $ be the value of the majority of $\ b_6b_7b_8$,   and $\ y\ $ be the value of the majority of $\ b_0b_1b_2$. (Values $ x\ y\ $ can be equal or different).
Case 2:   $b_6=b_7=b_8=x\ $ or $\ b_0=b_1=b_2=y$. It's enough to consider just the earlier option, about $\ x$.   Then there are three bits among $\ b_0\ldots b_5\ $ which have the same value.   These three bits together with $\ b_6b_7b_8\ $ form a 6-sequence of type $\ 6\ $ or $\ 3+3$. The latter option, about $\ y$,   is proved similarly.
Now we may assume that exactly two bits of $\ b_6b_7b_8\ $ have value $\ x$,   and exactly two of $\ b_0b_1b_2\ $ have value $\ y$.
Case 3:   $x=y$.   Then if at least $\ 2\ $ of the bits of $\ b_3b_4b_5\ $ have value $\ x\ $ then we leave these two $x$-bits together with two of the $x$-bits of $\ b_0b_1b_2\ $ and another two $x$-bits of $\ b_6b_7b_8\ $ to produce a 6-sequence of type $\ 6$.   Otherwise two bits of $\ b_3b_4b_5\ $ are different from $\ x=y$.   Then two (middle) non-x bits together with the 2+2 bits from $\ b_0b_1b_2\ $ and $\ b_6b_7b_8\ $ form a 6-sequence of type $\ 2+2+2$.
Case 4:   $x\ne y$.   The three bits $\ b_3b_4b_5\ $ cannot have the same value or else there would be $\ 6\ $ bits of the same value in the whole 9-sequence. Next, if there are integers $\ r\ s\ $ such that $\ 3\le r<s\le 5\ $ and $\ b_r=y\ $ and $\ b_s=x\ $ then we would get a 6-sequence of type $\ 3+3$.   Otherwise $\ b_3=x\ $ and $\ b_5=y$. Let's assume that $\ b_4=x\ $ (the case $\ b_4=y\ $  is symmetric). The the two of $y$-bits of $\ b_0b_1b_2\ $ together with $\ b_3b_4b_5\ $ and the single $y$-bit of $\ b_6b_7b_8\ $ form a 6-sequence of type $\ 2+2+2$.
END of PROOF
