Rompecabezas para eliminar k bits de vectores binarios de longitud 3k

Question

Considerar todos los $2^n$ diferentes vectores binarios de longitud $n$ y asumen $n$ es un múltiplo entero de $3$. Usted puede borrar exactamente $n/3$ bits de cada uno de los vectores binarios, dejando vectores de longitud $2n/3$ restante. El número de los distintos vectores restantes depende de los bits de eliminar. Asumiendo que su objetivo es salir lo poco que queda de vectores diferentes como sea posible, de cómo unos pocos se puede dejar como una función de la $n$?

Ejemplo, $n=3$. Usted puede dejar sólo los dos vectores $11$ e $00$.

Luego de los comentarios en las matemáticas.se sitio (en particular por Jack D'Aurizio), en general, para grandes valores de $n$ puede sustituir a cualquier bloque de tres bits por cualquiera de las $00$ o $11$. Esto le da un límite superior de $2^{n/3}$. Es esto en realidad, la respuesta correcta?

Ahora tengo algo de código para resolver instancias pequeñas, podemos empezar a rellenar una tabla de resultados óptimos. Usamos la notación $H(n,b)$ a indicar el número más pequeño de los distintos vectores que los resultados de partida con todos los vectores de longitud $n$ y la eliminación de $b$ de cada uno.

$$12 \leq H(15,5) \leq17$$

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

Para $n=10$ e $b = 1,2,3,4$ tenemos $\leq140,\leq 31,10, 4$

Para $n=9$ e $b = 1,2,3,4$ tenemos $70,18,6,2$

Para $n=8$ e $b = 1,2,3$ tenemos $40,10,4$

Para $n=7$ e $b = 1,2,3$ tenemos $20,6,2$

Para $n=6$ e $b = 1,2$ tenemos $12,4$

Para $n=5$ e $b = 1,2$ tenemos $6,2$

$$H(4,1) = 4, H(3,1) = 2, H(2,1) = 2$$

Si sólo nos permiten soluciones simétricas, a continuación,$H(10,2)=32$. Esto implica (assumnig no hay ningún error en los cálculos) que para algunos casos, puede no ser simétrica soluciones óptimas, como ya tenemos $H(10,2) \leq 31$.

Answer 1

Al menos puedo responder a su pregunta "¿Es esta la respuesta correcta?" con un afirmativo 'no'.

Específicamente, podemos reemplazar el límite superior$2^{n/3} \approxeq 1.26^n$ con el límite ligeramente mejor$6^{n/9} \approxeq 1.22^n$ aplicando la misma construcción 'separar en bloques independientes' al siguiente conjunto de cobertura (conjetura óptima) para$n = 9$:

PS

Claramente,$$\{000000, 111111, 111000, 000111, 001100, 110011\}$ sigue siendo óptimo para$2^{n/3}$ y de hecho (por búsqueda exhaustiva)$n = 3$.

Answer 2

Esto no es una respuesta, sino más bien un comentario largo. Quiero dar un informal argumento que sugiere lo que la respuesta correcta debe ser. La prueba de que el límite inferior es de rigor, la prueba de que el límite superior no está.

Denotar $k=n/3$. Digamos que una palabra binaria de $y\in\{0,1\}^{2k}$ cubre una palabra $x\in \{0,1\}^n$ si $y$ puede ser obtenido a partir de $x$ mediante la eliminación de $k$ dígitos. Nuestro objetivo es encontrar un conjunto $S \subset \{0,1\}^{2k}$ de más pequeño posible cardinalidad que cubre todas las palabras en $\{0,1\}^n$.

Un límite inferior en el tamaño de $S$. Vamos a mostrar que cada palabra $y$ cubre aproximadamente el $2^{nH(1/3)}$ palabras en $\{0,1\}^n$. Por lo tanto, el tamaño de $|S|$ al menos $2^{n(1-H(1/3))}\approx 2^{0.08\, n}$. Aquí $H(t)$ es la entropía de la función $$H(t) = -t \log_2 t - (1-t) \log_2(1-t).$$

Fijemos $y$ y contar el número de palabras $x$ que $y$ cubre. Para ello, vamos a considerar un algoritmo que comprueba si $y$ cubre $x$. Esto es sólo una simple algoritmo voraz que escanea $x$ de izquierda a derecha y encuentra los índices de $i_1 < \dots < i_{2k}$ s.t. $x_{i_r} = y_r$ para $r\in\{1,\dots, 2k\}$: $i_1$ es el primer índice s.t. $x_{i_1} = y_1$, $i_2$ es el primer índice después de $i_1$ s.t. $x_{i_2} = y_2$ y así sucesivamente. El algoritmo termina cuando se define $i_{2r}$. El algoritmo se realiza correctamente y se encuentra a $i_1< \dots < i_{2r} \leq n$ si y sólo si $y$ cubre $x$.

Deje $I_y(x) = \{i_1, \dots, i_{2k}\}$ para los que recibieron palabras de $x$ e $y$. Tenga en cuenta que si $I_y(x') = I_y(x'')$, a continuación, el algoritmo realiza exactamente los mismos pasos. En particular, la primera $i_{2r}$ cifras en $x'$ e $x''$ son iguales. También para cada conjunto $I\subset \{1,\dots, n\}$ del tamaño de la $2k$, hay una palabra $x$ s.t. $I_y(x) = I$.

Por lo tanto, el número de palabras $x$ cubierto por $y$ es igual a la suma sobre todos los valores posibles de $j\equiv i_{2r}$ el número de subconjuntos de $\{1,\dots, j\}$ del tamaño de la $2k$ multiplicado por el número de posibilidades para que los dígitos en las posiciones $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}.$$ donde $f(t) = (H(t)-1)/t$. La función de $f(t)$ alcanza su máximo en $[2/3,1]$ al $t=2/3$. Por lo tanto el número de palabras cubiertos por $y$ es de aproximadamente $$2^{n + 2 f(2/3)k} = 2^{nH(1/3)}.$$ Llegamos a la conclusión de que el conjunto de $S$ debe contener, al menos, $2^{n}/2^{H(1/3)n}\approx 2^{0.08\, n}$ palabras.

Un límite superior en el tamaño óptimo de $S$. Tenga en cuenta que este problema es una versión de la cobertura establecida problema. Por lo tanto el tamaño del conjunto óptimo de la cubierta (tamaño óptimo de $S$) está dentro de un registro-factor del tamaño de la óptima fracciones de la cubierta. (El registro del factor de es $\log 2^{3n} = O(n)$). Por lo que es suficiente para obtener un límite superior en el tamaño de una fracción de la cubierta para obtener un aproximado de límite superior en el tamaño del conjunto óptimo $S$.

Advertencia: Esto no es una prueba! Algunos de los siguientes enunciados no es correcto!

Considerar el bipartito gráfico con las palabras $\{0,1\}^{2k}$ a la izquierda, y las palabras de $\{0,1\}^{n}$ a la derecha, en la que $y$ está conectado a $x$ si $y$ cubre $x$. El gráfico es "más o menos bipartito". Para ser precisos, no es regular, pero está muy cerca de un gráfico regular (esto es una declaración informal que necesita justificación!). Vamos a pretender , sin embargo, que el grafo es regular. El grado de cada vértice de la izquierda es de aproximadamente $2^{H(1/3)n}$ como se calculó anteriormente. Así, podemos obtener una fracción de la cubierta cuando tomamos cada cadena de longitud $2k$ peso $2^n / (2^{2k} 2^{H(1/3)n})$. El peso total de todas las palabras en las fracciones de la cubierta es $2^n / (2^{H(1/3)n}) \approx 2^{0.08\, n}$.

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

Answer 3

Aquí está una exponencial límite inferior. Comenzamos por determinar exactamente cuántas cadenas de $Y$ de la longitud de la $n$ puede ser reducido a una cadena de caracteres $X=x_1x_2\cdots x_k$. En general $y$ podría contener muchas copias de $X$, pero contiene exactamente un izquierdo de copia de $X$; es decir, la primera $x_1$ luego de la primera $x_2$ y así sucesivamente. Las cadenas con $X$ como una más a la izquierda de la subcadena forma de un lenguaje regular de forma sencilla. Por ejemplo, si $X=101$, entonces el lenguaje es $0^*1 \cdot 1^*0 \cdot 0^*1 \cdot (0+1)^*$. La generación de la función de $0^*1$ e $1^*0$ es$z/(1-z)$, mientras que la generación de la función de $(0+1)^*$ es $1/(1-2z)$.

Por lo tanto, el número de $Y$s que contengan $X$ es independiente de la estructura de $X$ e es el coeficiente de $z^n$ en $z^k (1-z)^{-k} (1-2z)^{-1}$, es decir, $$N(n,k) = \sum_{i=0}^{n-k} 2^i\binom{n-i-1}{k-1},$$ que creo que no tiene una forma cerrada.

Por lo tanto, un límite inferior para la cuestión es $2^n/N(n,k)$.

Para $k=2n/3$, el mayor término de la suma es la primera, y a las siguientes condiciones son cerca de una progresión geométrica con relación $2/3$. Esto le da $$ N(n,2n/3) = (2 + O(1/n)) \binom{n}{2n/3},$$ dando un límite inferior de $$ (1+o(1)) \frac{\sqrt{\pi n}}{3} \left(\frac{2^{5/3}}{3}\right)^n. $$ Tenga en cuenta que $2^{5/3}/3\approx 1.05826737$.

Creo que es más probable que éste sea el mejor posible.

Answer 4

Si un vector tiene $d$ una de las entradas, y $d\leq n/2$, a continuación, elimine como muchos como usted puede, (y más ceros si es necesario). Por el contrario, si un vector tiene más entradas que cero entradas, eliminar tantos ceros como usted puede, (y más si es necesario).

Cualquier resto de vector del primer tipo se han $\max(d-n/3,0)\leq n/6$ queridos. El número de tales vectores con exactamente $n/6$ en $2n/3$ posiciones es $\binom{2n/3}{n/6}$. Para la suma final, uno tiene que suma más de bimomial coeficientes de $2 \sum_{i=0}^{n/6} \binom{2n/3}{i}$ y una suma puede ser aproximada: Tenga en cuenta que la entrada más grande, con $d=n/6$ da por lejos la mayor contribución. El coeficiente binomial en esta región se puede aproximar por $\binom{k}{l}=2^{k H(l/k)+o(k)}$ donde $H$ denota la función de la entropía $H(x)=\frac{-x \log x-(1-x)\log (1-x) }{\log 2}$, (para $x\in [0,1]$, e $\log $ es el logaritmo natural).

Edit: En vista de que Yuri comentario, puedo corregir esto: (Gracias, Yuri!)

Como $H(1/4)$ es de alrededor de $0.811$, esto es acerca de la $2^{2n/3 \times 0.811...+o(1)}=2^{0.54\ldots n}$.

Este límite superior es, sin duda más débil que el enlazado $2^{n/3}$, pero utiliza muy diferente método. Sería interesante ver, si el "óptimo" utiliza un determinista de la construcción, o de un azar de la construcción (como el de Shannon de los límites de la teoría de la codificación), o una combinación de métodos.

Alguna explicación de por qué el método anterior da algunas ahorro de más de la trivial $2^{2n/3}$: la mayoría de la original vectores tienen acerca de $n/2+ O(\sqrt{n})$ cero y una de las entradas. Se va a alejar de este simétrica centro se reduce (por medio de la distribución binomial) el número de de posibilidades. En otras palabras, la cola de esta distribución es pequeño.

Answer 5

Para $n=12$ es posible el uso de $10$ cadenas de longitud $2k=8.$

Hay, por $n=3k$, un tamaño más pequeño $s(n)$ para un conjunto $S$ de las cadenas en $ \{0,1\}^{2k}$ que cubre todas las cadenas en $\{0,1\}^n$.

Tenemos $s(n_1)s(n_2)\ge s(n_1+n_2)$, por lo que, por Fekete del Lema no es una constante $\alpha=\inf {s(n)^{1/n}}$ tal que $\lim {s(n)^{1/n}}=\alpha.$

Estamos tan lejos de las diversas respuestas que $$1.05827 \lt \alpha \lt 6^{1/9}\approx 1.2203.$$

Os muestro a continuación que $s(12) \le 10$, lo que mejora la cota superior de a $10^{1/12}\approx 1.2115.$

Para mejorar en este límite superior necesitaríamos $s(15) \le 17$ (yo apostaría por $16$, si acaso, sólo porque parece más bonito.) Teniendo en cuenta que debemos tener $0^{10},1^{10}$ (en un caso obvio de la notación) y añadiendo el optimista de la condición de que el conjunto de cadenas es cerrado bajo complementa y revertir el orden, podría ser posible investigar esto un poco inteligente de la fuerza bruta. Aún más optimista de la condición sería que cada cadena de longitud $2k=10$ es cambiado o sustituido por su complemento cuando invierte. Finalmente, uno podría añadir la restricción de que cada una de las no-palabras constantes tiene cinco $0$'s y cinco $1$'s. Puedo pensar en algunas obvio aún más las cadenas que incluyen, pero que aún queda mucho por hacer.

Un mayor límite inferior podrían (o no) surgen de la consideración de cómo las coincidencias no tiene que ser para varios "radio $k$" bolas. Por ejemplo, cada uno de los seis miembros de la establecida para $s(9)=6$ cubre $130$ de la $512$ cadenas en $\{0,1\}^{9}$, por lo que en promedio cada cadena es un poco más de $1.5$ veces. Algunos sólo una vez y en otros, como $111000111$ hasta tres veces.

En general, uno podría esperar razonablemente tener una cubierta de conjunto donde todos los no-constante de cadena ha $k$ $0$'s y por lo tanto $k$ $1$'s. Esto tiene la ventaja de que uno sabe para cualquier palabra en particular cuántas $1$'s y $0$'s, debe ser eliminado.

Para $n=12$ los ocho cadenas ( Walsh secuencias ) son (casi) lo suficiente $$00000000,00001111,00110011,00111100$$$$11111111,11110000,11001100,11000011.$$ They are enough with the addition of the two strings $$11101000,00010111$$ Aquí es un sketch donde evitamos el uso de la final de dos cadenas de tanto tiempo como sea posible:

Gracias a las dos cadenas constantes sólo necesitamos considerar la longitud de la $12$ cadenas con $5,6$ o $7$ $1$'s. Por la simetría y complementos que se puede restringir a $6$ o $7$ $1$'s con, al menos, como muchos entre los primeros $6$ lugares como el último $6$. Observar que cualquier longitud de $6$ cadena con $3$ $1$'s puede ser reducido a $0011$ o $1100$ con dos eliminaciones.

Veamos primero el caso de $6$ $1$'s. Si $3$ están en la mitad izquierda (y $3$ a la derecha), a continuación, la observación anterior demuestra que se puede conseguir una de las cuatro cadenas que no son constantes en la mitad. Si $5$ o $6$ están en la izquierda, entonces podemos obtener $11110000$.

Queda por considerar el caso de $7$ $1$'s y $5$ $0$'s con al menos $4$ de la $1$'s en el lado izquierdo. Debemos eliminar de una sola $0$ y tres $1$'s. De nuevo, si hay $5$ o $6$ $1$'s en el lado izquierdo, entonces podemos obtener $11110000$. Todo lo que queda es el subcase con $4$ $1$'s a la izquierda. Si el lado izquierdo es$abcde0$, entonces podemos eliminar la sola $0$ entre $abcde$ y continuar recibiendo $11110000.$ Si el lado izquierdo es$abcd11$, entonces podemos eliminar los dos $1$'s entre $abcd$ conseguir $0011$. Así que ahora tenemos la subsubcase que el lado izquierdo es $abcd01$ y el lado derecho tiene $3$ $0$'s y $3$ $1$'s. Las cuatro posibilidades de la izquierda incluyen $111001$,$110101$ (ambos de estos puede ser reducido a $1100$ con dos eliminaciones). Por último tenemos el caso de que el lado izquierdo es $101101$ o $011101$ y hay tres $1$'s en el lado derecho. En algunos casos, todavía estamos cubiertos, pero $101101\ 010101$ (por ejemplo) parece no tener esperanza. Sin embargo, para todos los $30$ de la longitud de 12 cuerdas dejado al descubierto que podemos eliminar el primer $0$ a partir de la mitad izquierda y los tres $1$'s de la derecha para obtener $1110101000.$