ACTUALIZACIÓN IMPORTANTE:
Lo que voy a mostrar no es una prueba del número mínimo de rectángulos. Sin embargo, en algunos casos he encontrado que el número de rectángulos puede ser menor que $f(n)^2$ . El más pequeño $N×N$ rejilla que he encontrado que puede tener menos de $f(n)^2$ rectángulos es $15×15$ que se muestra a continuación: $$\begin{array}{|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|} \hline 1&1&1&1&2&2&3&4&4&4&4&4&4&4&4\\ \hline 1&1&1&1&2&2&3&4&4&4&4&4&4&4&4\\ \hline 1&1&1&1&2&2&3&4&4&4&4&4&4&4&4\\ \hline 1&1&1&1&2&2&3&4&4&4&4&4&4&4&4\\ \hline 1&1&1&1&2&2&3&5&5&5&5&5&5&5&5\\ \hline 1&1&1&1&2&2&3&5&5&5&5&5&5&5&5\\ \hline 1&1&1&1&2&2&3&6&6&6&6&6&6&6&6\\ \hline 1&1&1&1&2&2&3&7&8&9&9&10&10&10&10\\ \hline 11&11&11&11&11&11&11&11&8&9&9&10&10&10&10\\ \hline 12&12&12&12&12&12&12&12&8&9&9&10&10&10&10\\ \hline 12&12&12&12&12&12&12&12&8&9&9&10&10&10&10\\ \hline 13&13&13&13&13&13&13&13&8&9&9&10&10&10&10\\ \hline 13&13&13&13&13&13&13&13&8&9&9&10&10&10&10\\ \hline 13&13&13&13&13&13&13&13&8&9&9&10&10&10&10\\ \hline 13&13&13&13&13&13&13&13&8&9&9&10&10&10&10\\ \hline \end{array}$$
El método utilizado en el anterior $15×15$ cuadrado puede generalizarse no sólo a otros cuadrados sino también a los rectángulos. Para aprovechar al máximo este método, ampliaré el método de la op a los rectángulos. Sea la longitud de un rectángulo igual a $m$ unidades y la anchura sea $n$ unidades. Entonces el número de rectángulos de base 2 utilizados para cubrir un $m × n$ rectángulo por el método de la op es $f(m)f(n)$ . Mi método no es fundamentalmente diferente del método del operador. Divide el $m×n$ rectángulo en cinco sub-rectángulos, y luego se aplica el método de la operación a cada uno de los cinco rectángulos. En algunos casos, el número de rectángulos de base 2 que cubren los cinco sub-rectángulos es menor que el número de rectángulos de base 2 que cubren el original $m$ × $n$ rectángulo utilizando el método de la op. Los cinco rectángulos están dispuestos de manera que hay dos pares de rectángulos que ocupan las esquinas y un rectángulo que está en el centro (sin tocar el perímetro). Cada par de rectángulos tiene el mismo tamaño y orientación pero en esquinas opuestas. (Arriba a la izquierda y abajo a la derecha o Arriba a la derecha y abajo a la izquierda.) La longitud y la anchura de los cinco rectángulos se construyen a partir de otras dos longitudes unitarias $a$ y $b$ . $a$ es el menor número tal que $m+a$ es una potencia de dos. $b$ es el menor número tal que $n+b$ es una potencia de dos. Esto significa que $f(m+a)$ y $f(n+b)$ son cada uno de ellos. La longitud y la anchura de los dos rectángulos del primer par son $f\left(\frac{m+a}{2}\right)$ y $f\left(\frac{n-b}{2}\right)$ respectivamente. La longitud y la anchura de los dos rectángulos del segundo par son $f\left(\frac{m-a}{2}\right)$ y $f\left(\frac{n+b}{2}\right)$ respectivamente. La fórmula para el número total de rectángulos de base 2 utilizados es $2f\left(\frac{m+a}{2}\right) f\left(\frac{n-b}{2}\right)+2f\left(\frac{m-a}{2}\right) f\left(\frac{n+b}{2}\right)+f(a)f(b)$ .
Tenga en cuenta que si un cuadrado con una longitud de $n$ unidades es de la forma $2^xy$ donde $x,y\in\Bbb{N}|x\ge 1,y\ge 1$ y $y$ es impar. Entonces el número de rectángulos de base 2 utilizados tanto para el método del operador como para mi método es el mismo que el número de rectángulos de base 2 utilizados para un cuadrado de longitud $y$ porque cada una de las dimensiones de los sub-rectángulos se puede multiplicar por $2^x$ . Por ejemplo, si queremos determinar cuántos rectángulos de base 2 son necesarios para cubrir un $30×30$ cuadrado utilizando mi método. Sólo utilizamos el $15×15$ ejemplo cerca de la parte superior de este post y multiplicar la longitud y la anchura de cada rectángulo de base 2 por $2$ . Así que esto significa que el $30×30$ requiere el mismo número de rectángulos de base 2 que el $15×15$ cuadrado. Así que el problema se puede simplificar a sólo rectángulos donde $m$ y $n$ son impar.
Se puede hacer una simple desigualdad que indique qué método utiliza menos rectángulos de base 2. Sea $N_l$ sea el número de unos en el número de la longitud del rectángulo en binario y $N_w$ sea el número de unos en el ancho en binario $\bigl($ o más simplemente $N_l=f(m)$ y $N_w=f(n)\bigr)$ . Además, deja que $Z_l$ sea el número de ceros en el número de la longitud del rectángulo en binario, $Z_w$ sea el número de ceros en el ancho en binario. Mi método utiliza menos rectángulos que el op cuando $$2f\left(\frac{m+a}{2}\right) f\left(\frac{n-b}{2}\right)+2f\left(\frac{m-a}{2}\right) f\left(\frac{n+b}{2}\right)+f(a)f(b)\lt f(m)f(n)$$
$$f\left(\frac{m+a}{2}\right)=1$$ $$f\left(\frac{n+b}{2}\right)=1$$ $$f\left(\frac{m-a}{2}\right)=N_l-1$$ $$f\left(\frac{n-b}{2}\right)=N_w-1$$ $$f(m)=N_l$$ $$f(n)=N_w$$ $$f(a)=Z_l+1$$ $$f(b)=Z_w+1$$
Con las sustituciones anteriores la desigualdad puede cambiarse a:
$$2(N_l-1)+2(N_w-1)+(Z_l+1)(Z_w+1)\lt N_lN_w$$ $$2N_l+2N_w-4+(Z_l+1)(Z_w+1)\lt N_lN_w$$ $$(Z_l+1)(Z_w+1)\lt N_lN_w-2N_l-2N_w+4$$ $$(Z_l+1)(Z_w+1)\lt (N_l-2)(N_w-2)$$
En el caso concreto del cuadrado (donde la longitud es igual a la anchura) mi método utiliza menos rectángulos de base 2 que el op cuando el número de unos en la representación binaria de la longitud es al menos cuatro más que el número de ceros. Para obtener la máxima utilidad de mi método, la desigualdad no sólo debe aplicarse a toda la longitud y anchura del cuadrado principal, sino también a los componentes del cuadrado. Por ejemplo, consideremos el cuadrado $1927×1927$ . La representación binaria de 1927 es 11110000111. Hay tres más unos que ceros en este número, por lo que mi método normalmente se igualaría a la operación, cubriendo el cuadrado con 49 rectángulos de base-2. Hay una forma de cubrir el cuadrado usando menos rectángulos de base 2 dividiendo el cuadrado en cuatro rectángulos $1920×1920$ , $1920×7$ , $7×1920$ y $7×7$ . Dividir de esta manera no cambia el resultado neto del método de la operación. Los tres primeros sub rectángulos satisfacen la desigualdad. Si utilizo mi método en los tres primeros sub rectángulos, utilizo 13, 11 y 11 rectángulos de base 2 respectivamente. Si utilizo el método de la op en el último subrectángulo y luego cuento todos los rectángulos de base 2, puedo cubrir el $1927×1927$ cuadrado utilizando 44 rectángulos de base-2.(13+11+11+9) Así que si una combinación de subcadenas en el valor binario de la longitud y la anchura satisface la desigualdad como lo hizo tres veces con los sub rectángulos, entonces mi método utilizará menos rectángulos de base-2 que el método del operador. Encontrar el número mínimo de rectángulos de base-2 para algunos cuadrados implicará inevitablemente la búsqueda de la mejor manera de dividir el cuadrado.
Para cuadrados suficientemente grandes, la peor combinación de dígitos en la que mi método no es mejor que el de la operación es un bloque de tres unos y el resto son ceros y unos alternados. Por ejemplo, el cuadrado $\require{enclose}\enclose{horizontalstrike}{343×343}$ su representación binaria es 101010111. Este cuadrado requiere 36 rectángulos de base 2 y está empatado con el mayor número de rectángulos de base 2 necesarios entre los cuadrados de nueve dígitos. Esto significa que se puede establecer un límite superior para el número mínimo de rectángulos necesarios. Sea $\enclose{horizontalstrike}{d_l}$ sea el número de dígitos de la representación binaria de la longitud del rectángulo. ( $\enclose{horizontalstrike}{d_l=N_l+Z_l}$ ) Deja que $\enclose{horizontalstrike}{d_w}$ sea el número de dígitos de la representación binaria de la anchura del rectángulo. ( $\enclose{horizontalstrike}{d_w=N_w+Z_w}$ ) Entonces el límite superior es: $$\enclose{horizontalstrike}{\left(\left\lceil\frac{d_l}{2}\right\rceil+1\right)\left(\left\lceil\frac{d_w}{2}\right\rceil+1\right)}$$
Conjeturo que la combinación de mi método y el método del operador es la forma óptima de minimizar el número de rectángulos de base 2. La única manera de que alguien pueda usar menos rectángulos es encontrar otra manera de dividir el cuadrado en sub-rectángulos de tal manera que usando el método de la OP en esos sub-rectángulos se usen menos rectángulos de base 2 que usando mi método y el método de la OP en todo el cuadrado.
El post de Rob Pratt(RP) muestra que hay un tercer método para cubrir el $n×n$ cuadrado con menos rectángulos de base 2 que mi método o el del operador para algunos $n×n$ cuadrados. Para describir cuántos rectángulos utiliza el método de RP seguiré utilizando el término $b$ de mi método (donde $b$ es el menor número tal que $b+n$ es una potencia de 2). También necesitaré un nuevo conjunto de términos $c_k$ y $s_k$ donde $k\in\Bbb{N}|1\le k\le f(b)$ . $c_1$ es el valor del dígito más a la izquierda de b en forma binaria. $c_2$ es el valor del segundo dígito a la izquierda de b en forma binaria. $c_3$ es el valor del tercer dígito a la izquierda de b en forma binaria. Etc. $s_v=\sum_{j=1}^vc_v$ . Por ejemplo, si $n=23$ entonces $b=9$ , $c_1=8$ , $c_2=1$ , $s_1=8$ , $s_2=9$ . El método de RP utiliza $$2f\left(\frac{n+b}{2}\right)f\left(\frac{n-b}{2}\right)+f\left(\frac{n+b}{2}\right)f\left(\frac{n-b}{2}+s_k\right)+f\left(\frac{n-b}{2}\right)f\left(\frac{n+b}{2}-s_k\right)+f(b)f(b-s_k)$$
rectángulos de base 2. Cada $f(•)f(•)$ producto contiene la longitud y la anchura de cada uno de los sub-rectángulos que cubre el cuadrado dentro de la función f. El método de RP tiene $k$ formas de cubrir el $n×n$ cuadrado uno para cada $s$ elemento. Evidentemente, el elemento $s_k$ elemento que utiliza el menor número de rectángulos de base 2 según la fórmula anterior es el que se utiliza para el mínimo. Una condición suficiente para cuando el método de RP utiliza menos rectángulos de base-2 que tanto mi método como el de op cuando la representación binaria de $n$ tiene al menos tres unos más que ceros, el segundo dígito a la izquierda es un cero, y el método de división que se mencionó para el $1927×1927$ cuadrado no se aplica.
