Return to Question

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 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$.

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$.

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 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) \leq18$$

$$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$.

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 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$.

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 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) \leq18$$

$$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 $\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$$

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 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) \leq18$$

$$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$.