Poco colocación de puzzle

Question

Considere la posibilidad de un vector binario de longitud $n$ que es principio de todos los ceros. Elige un bit del vector y la puso a $1$. Ahora se inicia un proceso que establece el bit que es la mayor distancia desde cualquier $1$ poco $1$ (o una elección arbitraria de más bits si hay más de uno). Esto sucede varias veces con la regla de que no hay dos $1$ bits pueden estar uno al lado del otro. Termina cuando no hay más espacio para colocar una $1$ bits. El objetivo es colocar la inicial $1$ poco, así que como muchos bits como sea posible se establecen a $1$ a la terminación.

Decir $n =2$. A continuación, dondequiera que establece el bit terminamos con exactamente un conjunto de bits.

Para $n =3$, si se establece el primer bit llegamos $101$ en la final. Pero si ponemos la mitad de bits obtenemos $010$ que no es óptimo.

Para $n=4$, lo poco que podemos establecer terminamos con dos set.

Para $n=5$, estableciendo la primera nos da el $10101$ con tres bits en el final.

Para $n=7$, tenemos que establecer el tercer bit para obtener $1010101$ parece.

¿Cuál es la regla más simple para colocar la inicial de bits que siempre va a dar una respuesta óptima?

Answer 1

Vamos $A(k)$, $B(k)$, $C(k)$ ser el número de movimientos que si el juego se inicia con $\underbrace{0\ldots0}_k$, $1\underbrace{0\ldots0}_k$, o $1\underbrace{0\ldots0}_k1$, respectivamente (con $k\ge1$ $C$ de los casos de forma que se comience en una posición legal). Claramente $A(0)=0$, $A(1)=1$, $B(0)=B(1)=0$ y también se $C(1)=C(2)=0$. Para grandes valores de $n$ tenemos la recursiones $$ \begin{align}A(n)&=1+\max_{0\le k< n}(B(k)+B(n-k-1))\\ B(n)&=1+C(n-1)\\ C(2n+1)&=1+2C(n)\\ C(2n)&=1+C(n)+C(n-1)\\ \end{align}$$ Por lo tanto, primero debemos encontrar las $C(n)$. Por experimentos numéricos, $C(n)$ parece crecer uno por uno, excepto que los valores de la forma $2^k-1$ se repiten $2^{k}+1$ veces. Podemos lanzar esta más precisamente en el siguiente

Lema. $$\tag1 C(n) =\begin{cases}0&\text{if }n\in\{1,2\},\\ \min\{n-2^{k+1},2^{k+1}-1\}&\text{if }k=\lfloor\log_2\tfrac n3\rfloor \text{ (i.e. }3\cdot 2^k\le n<3\cdot2^{k+1}\text{)}.\end{casos}$$ Podemos ver esto por inducción: Para $n\in\{1,2,3\}$ nos de verificación (1) inmediatamente. Incluso para $n=2m>3$ $3\cdot 2^k<n<3\cdot 2^{k+1}$ hemos $$\begin{align}C(n)&=1+C(m)+C(m-1)\\&= 1+\min\{m-2^{k},2^{k}-1\}+\min\{m-1-2^{k},2^{k}-1\}\\&=\begin{cases}1+m-2^{k}+m-1-2^{k}&\text{if }m-2^{k}\le 2^{k}-1\\ 1+2^{k}-1+2^{k}-1&\text{if }m-2^{k}\ge2^{k}\end{casos} \\&=\begin{cases}n-2^{k+1}&\text{if }n-2^{k+1}\le 2^{k+1}-2\\ 2^{k+1}-1&\text{if }n-2^{k+1}\ge2^{k+1}\end{casos}\end{align}$$ (tenga en cuenta que $n-2^{k+1}=2^{k+1}-1$ no puede suceder) y si $n=3\cdot 2^k$ $k\ge1$ hemos $$\begin{align}C(n)&=1+C(m)+C(m-1) \\ &= 1+\min\{3\cdot 2^{k-1}-2^{k},2^{k}-1\}+\min\{3\cdot 2^{k-1}-1-2^{k},2^{k}-1\}\\ &=1+2^{k-1}+2^{k-1}-1=2^{k}=n-2^{k+1}\end{align}$$ como sea necesario. Y por extraño $n=2m+1$ $3\cdot2^k\le n<3\cdot2^{k+1}$ tenemos $3\cdot2^{k-1}\le m<3\cdot 2^k$ y por lo tanto $$C(n)=1+2C(m)=1+2\min\{m-2^{k},2^{k}-1\}=\min\{1+2(m-2^{k}),1+2(2^{k}-1)\}=\min\{n-2^{k+1},2^{k+1}-1\}$$ también en este caso. $_\square$

Ahora podemos obtener inmediatamente

Corolario. $A$B(n)=\begin{cases}0&\text{if }n\in\{0,1\},\\ 1&\text{if }n\in\{2,3\},\\ \min\{n-2^{k+1},2^{k+1}\}& \text{with }k=\lfloor\log_2\tfrac {n-1}3\rfloor\text{ if }n>3.\end{casos}$$ Si $n>1$ $\frac n3\le B(n)\le \frac n2$ con la igualdad de la izquierda iff $n$, es tres veces la de una potencia de dos y la igualdad en el derecho iff $n$ es una potencia de dos.

Prueba: La fórmula para $B$ sigue inmediatamente de la lema y $B(n)=1+C(n-1)$. Para $n>3$ tenga en cuenta que $k=\lfloor\log_2\tfrac {n-1}3\rfloor$ implica $3\cdot 2^k\le n-1<3\cdot 2^{k+1}$, es decir,$n=3\cdot 2^k+r$$1\le r\le 3\cdot 2^k$. La próxima $B(n)=n-2^{k+1} = 2^k+r$ si $r\le 2^k$ y, a continuación, $\frac{n}{B(n)}=\frac{3\cdot 2^k+r}{2^k+r}$ entre $\frac{4\cdot 2^k}{2\cdot2^k}=2$$\frac{3\cdot 2^k}{2^k}=3$. Y $B(n)=2^{k+1}$ si $2^k\le r\le 3\cdot 2^k$ y, a continuación, $\frac{n}{B(n)}=\frac{3\cdot 2^k+r}{2\cdot 2^k}$ entre $\frac{3+1}{2}=2$$\frac{3+3}{2}=3$. Esto demuestra la desigualdad por $n>3$, los casos de $n=2$ $n=3$ puede ser activada manualmente. También vemos en el argumento de que $\frac{n}{B(n)}=2$ $\frac{n}{B(n)}=3$ se producen sólo para $r=2^k$$r=3\cdot 2^k$, respectivamente. $_\square$

El aspecto más importante de el corolario es: $B(n+1)-B(n)$ es $0$ o $1$. Por lo tanto, al determinar el $a, b$ tal que $a+b=n-1$ $A(n)=1+B(a)+B(b)$ observamos que podemos reemplazar $a$ $a+1$ (e $b$$b-1$) si $3\cdot 2^k\le a<4\cdot 2^k$ (e $a<n-1$) como que deja a $B(a)$ sin cambios y por lo tanto no puede disminuir el valor de $B(a)+B(b)$. Por otro lado, si $4\cdot 2^k<a\le 6\cdot 2^k$, la reducción de $a$ aumenta el $B(a)$ y por lo tanto no puede disminuir el valor de $B(a)+B(b)$. Si empezamos con un otimal par $(a,b)$$a\ge b$, este procedimiento conduce a otra óptimo par donde $a$ se ha convertido en una potencia de dos, $a=4\cdot 2^k$. En este proceso, $a$ mayo se han convertido $<b$ o se $\ge b$. En el segundo caso, cuando $a\ge b$, $a$ es la mayor potencia de dos $\le n-1$. En el primer caso, la inicial $a\ge b$$<6\cdot 2^k$, lo que significa que $8\cdot 2^k<n-1<12\cdot 2^k$, lo $4\cdot 2^k<b<8\cdot 2^k$. Si $4\cdot 2^k<b\le 6\cdot 2^k$, obtenemos $B(a)+B(b) = 2^{k+2}=B(8\cdot 2^k)\le B(8\cdot 2^k)+B(n-1-8\cdot 2^k)$ y por maximality $B(n-1-8\cdot 2^k)=0$, es decir, $n$ está ligeramente por encima de una potencia de dos y podemos escoger también el $a=8\cdot 2^k$. Por otro lado, si $6\cdot 2^k<b<8\cdot 2^k$, podemos intercambiar $a$ $b$ y repita el procedimiento anterior, esta vez en la mayoría de aumento de $a$, de modo que terminamos en el segundo caso nuevo. En resumen, podemos suponer que wlog. que $a$ es la mayor potencia de dos $\le n-1$, por lo que han demostrado

Teorema. Para$n=2^k+r+1$$0\le r<2^k$, tenemos $$ A(n)=1+B(2^k)+B(r)=1+2^{k-1}+B(r). _\square$$

Si $r>1$ en el teorema y lo escribimos como $c\cdot 2^m$$3\le c<6$, $B(r)=(c-2)2^m$ si $3\le c\le 4$ $B(r)=2\cdot 2^m$ si $4\le c<6$. De $2^k>r$ tenemos $m\le k-2$ en el primer caso y $m\le k-3$ en el segundo caso. Así, en el primer caso nos encontramos con $$\frac{n-1}{A(n)-1}=\frac{2^k+c2^m}{2^{k-1}+(c-2)2^m}\le\frac{2^k+3\cdot 2^{m}}{2^{k-1}+2^{m}}\le \frac{2^k+3\cdot2^{k-2}}{2^{k-1}+2^{k-2}}=\frac 73.$$ Y en el segundo caso nos encontramos con $$ \frac{n-1}{A(n)-1}=\frac{2^k+c2^m}{2^{k-1}+2^{m+1}}\le \frac{2^k+6\cdot 2^m}{2^{k-1}+2\cdot 2^{m}}\le\frac{2^k+3\cdot 2^{k-2}}{2^{k-1}+2^{k-2}}=\frac{7}{3}$$ (una pequeña mejora de una manera más sencilla de estimar dando a $\frac{n}{A(n)}\le \frac{12}5$).

Answer 2

Primero, considere el número de bits que será activado por este proceso en una cadena de $n$ ceros flanqueado por. Llamar a ese número $A_n$. Claramente $A_1=A_2=0$, y para $n\ge 3$ el siguiente recursión se tiene: $$ A_n = 1+A_{\lfloor (n-1)/2\rfloor}+A_{\lceil (n-1)/2 \rceil}, $$ o $$\begin{eqnarray}A_{2k+1}&=&1+2A_{k} \\ A_{2k+2}&=&1+A_{k}+A_{k+1}\end{eqnarray}$$ para $k\ge 1$. Ahora considere el $B_n$, el número de bits que se convertirá en una cadena de $n$ ceros con un único acompañamiento. Aquí $B_{n}=1+A_{n-1}$$n\ge 2$, por lo que nos encontramos con los siguientes: $$\begin{eqnarray} B_{2k+2}&=&1+A_{2k+1}&=&2+2A_{k}&=&2B_{k+1} \\ B_{2k+3}&=&1+A_{2k+2}&=&2+A_{k}+A_{k+1}&=&B_{k+1}+B_{k+2}\end{eqnarray}$$ para $k\ge 1$. (La secuencia se inicia con $B_{0}=B_{1}=0$$B_{2}=B_{3}=1$.) El problema original se pregunta por $i \in \{1,2,\ldots,n\}$ tal que $B_{i-1}+B_{n-i}$ está maximizada. El estudio de la secuencia de $B_n$, uno ve eficientes de embalaje ( $B_n=n/2$ ) $n$ es una potencia de $2$, e ineficiente de embalaje ( $B_n=n/3$ ) $n$ es tres veces la potencia de $2$. Una razonable "codiciosos" conjetura, entonces, es que obligando a la mayor cadena de bits en un eficiente embalaje de la estructura, por la elección de $$i=2^{\lfloor \log_2(n-1)\rfloor}+1,$$will produce an efficient overall packing; at any rate, it guarantees a packing fraction of $5/12$, ya no más de la mitad de los bits son suboptimally lleno.

Esta conjetura parece sostener numéricamente; al menos para $n\le 10000$, una de empaquetamiento óptimo es producida por esta elección de $i$. Esta elección parece arriesgado al $n=2^k+3\cdot 2^{k-2}+1$, ya que el resto de la porción es grande y su embalaje es tan baja como sea posible. De hecho, los valores de $n$ tienen un número inusualmente elevado de igual de buenas opciones para $i$ (a diferencia de, digamos, $n=2^k+2^{k-2}+1$); pero la simple elección anterior es siempre empatados para el primer puesto.

---

Una forma cerrada de la expresión para el número de bits que se establecerá para un determinado $(i, n)$ es proporcionado por la sección 3.3 de este documento sobre el "orinal problema" (que es la esencia de este rompecabezas es). En términos de la función auxiliar $$K_n=2^{\lfloor\log_2 n\rfloor},$$ que es la potencia más grande de $2$ no mayor de $n$, dan la siguiente expresión correcta para mi $B_n$: $$ B_{n} = \frac{1}{2}K_n + \left(\left\lfloor\frac{2n}{K_n}\right\rfloor - 2\right)\cdot\left(n - \frac{3}{2}K_n\right). $$ La expresión $\lfloor{2n / K_n}\rfloor - 2$ es igual a $1$ (si $n$'s representación binaria comienza con $11$) o $0$ (si comienza con $10$), y por lo $B_{n}$ sí es $n - K_n$ o $K_n / 2$. Si $n$ es una potencia de $2$, entonces claramente $B_{n}=K_n/2=n/2$ exactamente.

Ahora, cuando la inicial bit es colocado en el $i$-ésima posición, el número total de bits que se enciende es $1 + B_{i-1} + B_{n-i}$. Mi conjetura es que el establecimiento $i=K_{n-1}+1$ siempre producirá un empaquetamiento óptimo; el número de bits que se establece es entonces $$ 1 + B_{K_{n-1}} + B_{n-1-K_{n-1}}. $$ Debido a $K_{n-1}$ es una potencia de $2$, esto también puede ser escrito como $$ 1 + \frac{1}{2}K_{n-1} + B_{n-1-K_{n-1}}. $$