Empaquetado de cuadrados

El empaquetado de cuadrados es un problema de empaquetado donde el objetivo es determinar cuántos cuadrados congruentes se pueden empaquetar en una forma más grande, a menudo un cuadrado o un círculo.

Empaquetado de cuadrados en un cuadrado

Empaquetar cuadrados en un cuadrado es el problema de determinar el número máximo de cuadrados unidad (cuadrados de longitud de lado uno) que se pueden empaquetar dentro de un cuadrado más grande de longitud de lado $a$ . Si $a$ es un número entero, la respuesta es $a^{2},$ , pero la cantidad precisa (o incluso asintótica) del espacio que queda sin cubrir para un $a$ arbitrario no entero es una pregunta abierta.^[1]

Plantilla:Multiple image

El valor más pequeño de $a$ que permite empaquetar cuadrados unitarios $n$ se conoce cuando $n$ es un cuadrado perfecto (en cuyo caso es $\sqrt{n}$ ), así como para $n =$ 2, 3, 5, 6, 7, 8, 10, 13, 14, 15, 24, 34, 35, 46, 47 y 48. Para la mayoría de estos números (con la única excepción de 5 y 10), el empaquetamiento es el natural con cuadrados alineados con los ejes horizontal y vertical, y $a$ es $⌈ \sqrt{n} ⌉$ , donde $⌈ ⌉$ donde ceiling es es la función redondeo hacia arriba.^[2]^[3] La figura muestra los empaquetamientos óptimos para 5 y 10 cuadrados, los dos números más pequeños de cuadrados para los cuales el empaquetamiento óptimo involucra disponer cuadrados inclinados.^[4]^[5]

El caso más pequeño sin resolver implica empaquetar 11 cuadrados unitarios en un cuadrado más grande. No se pueden empaquetar 11 unidades de cuadrados en un cuadrado de longitud de lado menor que $2 + 2 \sqrt{4 / 5} \approx 3.789$ . Por el contrario, el empaquetamiento más apretado conocido de 11 cuadrados está dentro de un cuadrado de longitud de lado de aproximadamente 3,877084; solución encontrada por Walter Trump.^[6]^[4]

Resultados asintóticos

Plantilla:No resuelto

Para valores mayores de la longitud del lado $a$ , se desconoce el número exacto de cuadrados unitarios que pueden empaquetarse en un cuadrado de lado $a \times a$ . Siempre es posible empaquetar una cuadrícula $⌊ a ⌋ \times ⌊ a ⌋$ de cuadrados unitarios alineados con el eje, pero esto puede dejar un área grande, aproximadamente $2 a (a - ⌊ a ⌋)$ , descubierta y desperdiciada.^[4] En cambio, Paul Erdős y Ronald Graham demostraron que para un empaquetado diferente mediante cuadrados unitarios inclinados, el espacio desperdiciado podría reducirse significativamente a $o (a^{7 / 11})$ (aquí escrito como cota superior asintótica).^[7] Posteriormente, Graham y Fan Chung redujeron aún más el espacio desperdiciado a $O (a^{3 / 5})$ .^[8] Sin embargo, como Klaus Roth y Bob Vaughan demostraron, todas las soluciones deben desperdiciar al menos un espacio de $Ω (a^{1 / 2} (a - ⌊ a ⌋))$ . En particular, cuando $a$ es un número semientero, el espacio desperdiciado es al menos proporcional a su raíz cuadrada.^[9] La tasa de crecimiento asintótica precisa del espacio desperdiciado, incluso para longitudes de lados semienteros, sigue siendo un problema no resuelto.^[1]

Algunos números de cuadrados unitarios nunca son el número óptimo en un empaquetamiento. En particular, si un cuadrado de tamaño $a \times a$ permite empaquetar $n^{2} - 2$ cuadrados unitarios, entonces debe darse el caso de que $a \geq n$ , y que también es posible un empaquetamiento de cuadrados unitarios $n^{2}$ .^[2]