Número mínimo de rectángulos para cubrir la cuadrícula sin diagonales

Question

Estoy tratando de averiguar el número mínimo de rectángulos deben cubrir un $n \times n$ cuadrícula, menos de la diagonal. Lo que esto significa es la siguiente: Supongamos que tenemos una $n \times n$ cuadrícula, con la diagonal que faltan. ¿Cuál es el mínimo número de rectángulos necesito que están contenidos dentro de la red tales que la unión de los rectángulos cubre la totalidad de la cuadrícula?

Creo que la respuesta debería ser $\log_2 n$. El logro es muy fácil, hay dos $n^2/4$ plazas (con lo que quiero decir dos cuadrados con área de $n^2/4$), cuatro $n^2/16$ plazas, 8 $n^2/64$ plazas, y así sucesivamente. Sumando a esto (y asumiendo $n = 2^m$), se obtiene $$ \sum_{k=1}^{m = \log_2 n} 2^k \cdot n^2/4^k = \sum_{k=1}^m n^2 2^{-k} = n^2(1 - 1/n) = n^2 - n. $$ Pero no veo una manera limpia argumentar que esto es lo mejor que puedes hacer.

Answer 1

Supongamos que cada cuadrado de la cuadrícula de coordenadas $i,j$ que representa a su fila y columna. Echa un vistazo a las plazas: (1,2), (2,3), (3,4), ..., ($n$-1, $n$) por encima de la diagonal y (2,1), (3,2), ..., ($n$, $n-1$) por debajo de la diagonal. No hay rectángulo que cubre cualquiera de las dos plazas recogidas a partir de este conjunto al mismo tiempo.

Por lo que necesita al menos $2(n-1)$ rectángulos sólo para cubrir todas las plazas de este conjunto. Afortunadamente, usted puede cubrir todo el tablero con el mismo número de rectángulos (un conjunto de rectángulos horizontales de altura 1 va a hacer el trabajo).

Así que el mínimo número de rectángulos que realmente es $2(n-1)$.