¿La forma más eficaz de embaldosar un rectángulo con cuadrados?

Question

Estaba escribiendo una descripción del Algoritmo euclidiano para un conjunto de apuntes del curso y estaba jugando con una intuición geométrica para el algoritmo que implica embaldosar un $m \times n$ rectángulo con cuadrados progresivamente más pequeños, como se ve en esta animación enlazada desde el Artículo de Wikipedia:

Estaba mirando esta animación y tenía curiosidad por saber si los cuadrados que se colocan en el curso de este algoritmo dan necesariamente el número mínimo de cuadrados necesarios para cubrir todo el rectángulo.

De manera más formal: supongamos que nos dan un $m \times n$ rectángulo, donde $m, n \in \mathbb{N}$ y $m, n > 0$ . Tu objetivo es embaldosar este rectángulo con un conjunto de cuadrados que no se superpongan. Dado $m$ y $n$ ¿Cuál es la forma más eficaz de colocar estas baldosas?

¿Es el mosaico sugerido por el algoritmo euclidiano (es decir, en un $m \times n$ rectángulo, con $m \ge n$ Siempre que sea posible, coloque un $n \times n$ rectángulo, y luego recurrir al rectángulo restante) siempre es óptimo? Si no, ¿hay algún algoritmo más eficiente para este problema?

Estoy razonablemente seguro de que el enfoque euclidiano es correcto, pero estaba teniendo muchos problemas para formalizar la intuición con una prueba debido a que hay un lote de diferentes maneras locas se puede tratar de colocar las plazas. Por ejemplo, no estoy seguro de cómo hacer que la prueba maneje la posibilidad de que los cuadrados puedan estar en ángulos, o puedan tener longitudes de lado en $\mathbb{R} - \mathbb{Q}$ .

Gracias.

Answer 1

Recordando el trabajo de Kenyon sobre esto, encontré estos comentarios en un viejo Puesto de MO

Embaldosar un rectángulo con el menor número de cuadrados. Kenyon, Richard J. Combin. Theory Ser. A 76 (1996), no. 2, 272-291. "Demostramos que un cuadrado de un rectángulo p×q, donde p y q son enteros relativamente primos, tiene al menos $\log 2p$ cuadrados. Si $q>p$ construimos un mosaico cuadrado con menos de $q/p+C \log p$ cuadrados de tamaño entero, para alguna constante universal $C.$ ''

Rectángulos como sumas de cuadrados. Walters, Mark Discrete Math. 309 (2009), nº 9, 2913-2921. Donde precisamente se discute esta cuestión y se atribuye a Laczkovich (es decir, el número mínimo de cuadrados necesarios para embaldosar un rectángulo de lados enteros (aunque no se supone que los cuadrados sean de lados enteros). Por supuesto, usted está pidiendo un algoritmo eficiente que es una cuestión diferente ... El artículo de Kenyon discute algún algoritmo (codicioso) sin embargo. -- Vagabond Nov 2 2010 at 9:18

Answer 2

Euclides no siempre minimiza el número de cuadrados. Por ejemplo, con un $8\times9$ rectángulo, Euclides dice que hay que usar un cuadrado de 8 y 8 cuadrados de 1, 9 cuadrados en total. Pero puedes hacerlo con un 5, dos 4, un 3, un 2 y dos 1, lo que hace un total de 7 cuadrados. Pones el 5 en una esquina, luego pones los 4 en las esquinas que tienen espacio para ellos; eso deja un $3\times5$ rectángulo a rellenar, lo que se puede hacer por Euclides.