Question also asked at http://math.stackexchange.com/questions/497343/deletion-puzzle.

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 that the vectors of length $n$ and the number of bits removed per vector is $b$.

$$11 \leq H(15,5) \leq18$$

$$H(12,4) = 10$$

For $n=10$ and $b = 1,2,3,4$ we have $\leq141,\leq 31,10, 4$

For $n=9$ and $b = 1,2,3,4$ we have $\leq70,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$$