¿Cuál es el número mínimo de líneas rectas necesarias para cubrir una cuadrícula de $n \times n$?

Question

Quiero saber cuál es el número mínimo de líneas necesarias para tocar cada cuadro de una cuadrícula de $n \times n$. La única regla adicional es que la línea tiene que pasar por dentro del cuadro, no por el borde/esquina. He encontrado una solución para $n-1$ líneas para todos los $2 pero no con menos líneas. Me imagino que se pueden representar las líneas por los cuadros que atraviesan, creando así una cantidad finita de "líneas", pero no tengo muchas ideas adicionales. Aquí tienes un ejemplo de lo que quiero decir con "cubrir un cuadro". La línea solo necesita pasar por cualquier parte del cuadro:

También aquí tienes una solución para una cuadrícula de $3 \times 3$ con 2 líneas:

Answer 1

He trabajado en este problema y he consultado a muchas personas al respecto. Creo que es un problema difícil. Según los autores del artículo a continuación, es un problema abierto, hasta 2013.

Afirmo tener una construcción de $n-1$ líneas para todos los $n$, pero nunca lo escribí formalmente. Creo que esta es la respuesta correcta, pero las pruebas del límite inferior son bastante difíciles. Para valores pequeños de $n$ (por ejemplo, $n \leq 9$), pude demostrar un límite inferior correspondiente mediante argumentos ad hoc.

Si deseas intentar resolver este problema de manera interactiva, visita mi sitio web: https://bob1123.github.io/website/linecovering.html.
Actualización (2023-11-09): https://bob1123.github.io/linecovering.html

Un límite inferior trivial es $n/2$. Se conoce un límite inferior mejor de $2n/3$. Consulta a Eyal Ackerman y Rom Pinchasi. "Covering a chessboard with staircase walks." Discrete Mathematics 313.22 (2013): 2547-2551. Ellos generalizan de líneas a "caminos monótonos", es decir, conjuntos contiguos de cuadrados que siempre se mueven hacia abajo (o se mantienen iguales) al ir hacia la derecha o siempre se mueven hacia arriba (o se mantienen iguales) al ir hacia la derecha. Cuando se cubre con caminos monótonos, el $2n/3$ es un límite ajustado, por lo que para llegar a $n-1$ necesitas explotar la estructura especial de las líneas.

Debo mencionar que la única continuación que conozco es la de Kerimov, Azer. "Covering a rectangular chessboard with staircase walks." Discrete Mathematics 338.12 (2015): 2229-2233. Ellos generalizan de un tablero de $n \times n$ a un tablero de $n \times m$.

Answer 2

Considera una función continua $w$ en $Q=[-1,1]^2$ y piensa en tu cuadrícula como una cuadrícula de $2n\times 2n$ cuadrados de tamaño $1/n$. Entonces la suma de los valores de $w$ a lo largo de los cuadrados que intersectan una línea $\ell$ es esencialmente $n\int_{\ell\cap Q} w(|dx|+|dy|)\le n\sqrt 2\int_{\ell\cap Q}w\,ds$ donde $s$ es el elemento de longitud en $\ell$. Ahora, la suma total es aproximadamente $n^2\int_Q w$. Así que tenemos un límite asintótico de $n$ veces $\frac 1{\sqrt 2}\int_Q w$ dividido por el supremo de $\int_{\ell\cap Q}w\,ds$ sobre todas las líneas. Ahora tomamos $w$ como una versión suavizada de $1/{\sqrt{1-|z|^2}}$ en el disco unitario y $0$ afuera (la función usada para mostrar que no puedes cubrir el disco unitario con franjas de ancho total menor a $2$). Entonces la razón de la integral al supremo es ${2\pi}/\pi=2$ y obtenemos $\sqrt 2 n$ versus el $2n$ esperado, que es una pérdida de un factor de $\sqrt 2$. Por supuesto, todo el argumento es un descarado plagio de Arquímedes y parece que debería haber lugar para alguna mejora. :-)

Answer 3

Utilicé el enfoque de programación lineal entera (ILP) sugerido por @BillyJoe. Deje que $L$ sea el conjunto de líneas discretas, deje que $S$ sea el conjunto de cuadrados, y deje que $L_s \subseteq L$ sea el subconjunto de líneas que cubren el cuadrado $s$. Deje que la variable binaria $z_\ell$ indique si se utiliza la línea discreta $\ell$. El problema (de cobertura de conjuntos) es minimizar $$\sum_{\ell\in L} z_\ell$$ sujeto a $$\sum_{\ell\in L_s} z_\ell \ge 1$$ para todos los $s\in S$. Para $n\in\{3,\dots,12\}$, el mínimo resulta ser $n-1$. Utilicé la lista de líneas generada aquí por @MikeEarnest, pero solo se necesitan las máximas (con respecto a la inclusión de conjuntos).

Para $n=10$, el límite inferior de programación lineal (LP) es ligeramente inferior a $7$, por lo que no obtenemos un certificado de optimalidad corto de una solución dual LP. El solucionador ILP devolvió la siguiente solución con $9$ líneas, donde cada cuadrado está etiquetado por las líneas que lo cubren. Por ejemplo, el cuadrado superior izquierdo está cubierto por las líneas $2$ y $7$.

27    2    2    1    1    9    9    8    8    6 
47    7    2    2    1   19    1    8    6    6 
 4    7    7    2   29    9  168  168    6    3 
 4    4    7   79  269   26   68   13   13    3 
 5    4    4  679   67   28  238   23    1    1 
 5   56 4569  469    7  378   37    2    2    1 
 6    6   59   45  345   38    7    7    2    2 
 6    9    9    3 3458  458    5    7    7    2 
 9    9    3    3    8    4    5    5    7    7 
39    3    3    8    8    4    4    5    5   57 

Aquí están los resultados para $n \le 15$: \begin{matrix} n & \text{# líneas} & \text{# líneas maximales} & \text{LP} & \text{ILP} \\ \hline 1 & 1 & 1 & 1 & 1 \\ 2 & 12 & 4 & 1.3333333333 & 2 \\ 3 & 54 & 16 & 2 & 2 \\ 4 & 152 & 44 & 2.5882352941 & 3 \\ 5 & 338 & 116 & 3.3333333333 & 4 \\ 6 & 652 & 236 & 4 & 5 \\ 7 & 1138 & 484 & 4.6976744186 & 6 \\ 8 & 1864 & 820 & 5.3979238754 & 7 \\ 9 & 2882 & 1384 & 6.1142857143 & 8 \\ 10 & 4236 & 2164 & 6.8352769679 & 9 \\ 11 & 6058 & 3276 & 7.5793705947 & 10 \\ 12 & 8376 & 4668 & 8.290598175 & 11 \\ 13 & 11358 & 6632 & 9.0237713232 & [11,12] \\ 14 & 15044 & 8988 & 9.7587254886 & [11,13] \\ 15 & 19498 & 12128 & 10.499058033 & [12,14] \\ \end{matrix}

Answer 4

Creo que Bob tiene razón. (¡Gracias por proporcionar el dispositivo!) El patrón que encontré para $n=15$ debería dar una idea sobre un patrón general factible. Una vez que todas las cuadrículas fueron cubiertas, eliminé cada otras línea para exhibir las formas de escalera.

Subiendo desde la esquina inferior izquierda (o bajando desde la esquina superior derecha), el patrón encontrado es 1 2 1 - 1 2 1 - 1 2 1 - 1 2.
Yendo hacia la derecha desde la esquina inferior izquierda (o hacia la izquierda desde la esquina superior derecha), el patrón es 2 4 4 4 1. Ambos patrones juntos describen completamente la cobertura.

Así que parece que esto solo depende de n módulo 4 y es fácil de iterar. Para ser completo:
Por supuesto, esto aún no es una prueba rigurosa, pero debería estar bastante claro cómo formalizarlo si se desea. :)

EDITAR: Aunque obviamente es un problema muy difícil, es lineal en cierto sentido, en una línea similar al (muy fácil) teorema de Pick. Ahora, después de jugar un poco con el dispositivo, tengo una conjetura más sólida:

Intentar cubrir un cuadrado de $n\times n$ con solo $n-2$ líneas, dejará al menos 4 casillas sin cubrir. Además, si exactamente cuatro casillas quedan, los únicos componentes conectados formados por esas son de 1x1 (es decir, celdas aisladas) y/o 2x1. Esto también significaría (aunque tengo un poco menos de certeza al respecto) que ninguna de esas cuatro celdas puede estar diagonalmente adyacente, es decir, compartir exactamente 1 vértice.

Es esta conjetura/descubrimiento lo que me dio la idea de 'linealidad'. ¡Después de todo, puede haber un mecanismo oculto pero bastante fácil detrás!