Embalaje cuadrado

Problema de empaquetamiento bidimensional

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

Embalaje cuadrado en un cuadrado

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

El valor más pequeño de que permite el empaquetamiento de cuadrados unitarios se conoce cuando es un cuadrado perfecto (en cuyo caso es ), así como para 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 las únicas excepciones de 5 y 10), el empaquetamiento es el natural con cuadrados alineados con el eje, y es , donde es la función de techo (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 que el empaquetamiento óptimo implica cuadrados inclinados. ^{[4] [5]} ${\displaystyle a}$ ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle {\sqrt {n}}}$ ${\displaystyle n={}}$ ${\displaystyle a}$ ${\displaystyle \lceil {\sqrt {n}}\,\rceil }$ ${\displaystyle \lceil \,\ \rceil }$

El caso no resuelto más pequeño es . Se sabe que no se pueden empaquetar 11 cuadrados unitarios en un cuadrado de lado menor que . Por el contrario, el empaquetamiento más ajustado conocido de 11 cuadrados está dentro de un cuadrado de lado de aproximadamente 3,877084 encontrado por Walter Trump . ^{[4] [6]} ${\displaystyle n=11}$ ${\displaystyle \textstyle 2+2{\sqrt {4/5}}\approx 3.789}$

El caso más pequeño en el que el empaquetamiento más conocido involucra cuadrados en tres ángulos diferentes es . Fue descubierto en 1998 por John Bidwell, un estudiante de pregrado de la Universidad de Hawái , y tiene una longitud lateral de . ^[4] ${\displaystyle n=17}$ ${\displaystyle a\approx 4.6756}$

Resultados asintóticos

Problema sin resolver en matemáticas :

¿Cuál es la tasa de crecimiento asintótico del espacio desperdiciado por empaquetamiento cuadrado en un cuadrado medio entero?

(más problemas sin resolver en matemáticas)

Para valores mayores de la longitud del lado , el número exacto de cuadrados unitarios que pueden empaquetar un cuadrado sigue siendo desconocido. Siempre es posible empaquetar una cuadrícula de cuadrados unitarios alineados con el eje, pero esto puede dejar un área grande, aproximadamente , descubierta y desperdiciada. ^[4] En cambio, Paul Erdős y Ronald Graham demostraron que para un empaquetamiento diferente por cuadrados unitarios inclinados, el espacio desperdiciado podría reducirse significativamente a (aquí escrito en notación o minúscula ). ^[7] Más tarde, Graham y Fan Chung redujeron aún más el espacio desperdiciado a . ^[8] Sin embargo, como demostraron Klaus Roth y Bob Vaughan , todas las soluciones deben desperdiciar espacio al menos . En particular, cuando es un medio entero , el espacio desperdiciado es al menos proporcional a su raíz cuadrada . ^{[9] La} tasa de crecimiento asintótico precisa del espacio desperdiciado, incluso para longitudes de lado medio enteras, sigue siendo un problema abierto . ^[1] ${\displaystyle a}$ ${\displaystyle a\times a}$ ${\displaystyle \lfloor a\rfloor \!\times \!\lfloor a\rfloor }$ ${\displaystyle 2a(a-\lfloor a\rfloor )}$ ${\displaystyle o(a^{7/11})}$ ${\displaystyle O(a^{3/5})}$ ${\displaystyle \Omega {\bigl (}a^{1/2}(a-\lfloor a\rfloor ){\bigr )}}$ ${\displaystyle a}$

Ciertas cantidades de cuadrados unitarios nunca son la cantidad óptima en un empaquetamiento. En particular, si un cuadrado de tamaño permite el empaquetamiento de cuadrados unitarios, entonces debe darse el caso de que y que un empaquetamiento de cuadrados unitarios también sea posible. ^[2] ${\displaystyle a\times a}$ ${\displaystyle n^{2}-2}$ ${\displaystyle a\geq n}$ ${\displaystyle n^{2}}$

Embalaje cuadrado en un círculo

El empaquetamiento de cuadrados en un círculo es un problema relacionado con el empaquetamiento de n cuadrados unitarios en un círculo con un radio lo más pequeño posible. Para este problema, se conocen buenas soluciones para n hasta 35. A continuación se presentan soluciones mínimas para n hasta 12: ^[10]

Véase también

• Empaquetado circular en un cuadrado
• Cuadrando el cuadrado
• Embalaje rectangular
• Problema con el sofá móvil

Referencias

1. Brass, Peter; Moser, William; Pach, János (2005), Problemas de investigación en geometría discreta, Nueva York: Springer, pág. 45, ISBN 978-0387-23815-9, LCCN  2005924022, MR  2163782
2. Kearney, Michael J.; Shiu, Peter (2002), "Empaquetado eficiente de cuadrados unitarios en un cuadrado", Electronic Journal of Combinatorics , 9 (1), Documento de investigación 14, 14 pp., doi :10.37236/1631, MR  1912796
3. Bentz, Wolfram (2010), "Empaquetamientos óptimos de cuadrados unitarios de 13 y 46 en un cuadrado", The Electronic Journal of Combinatorics , 17 (R126), arXiv : 1606.03746 , doi :10.37236/398, MR  2729375
4. Friedman, Erich (2009), "Empaquetado de cuadrados unitarios en cuadrados: una encuesta y nuevos resultados", Electronic Journal of Combinatorics , Dynamic Survey 7, doi : 10.37236/28 , MR  1668055
5. Stromquist, Walter (2003), "Empaquetado de 10 u 11 cuadrados unitarios en un cuadrado", Electronic Journal of Combinatorics , 10 , Documento de investigación 8, doi :10.37236/1701, MR  2386538
6. La versión de 2000 de Friedman (2009) indicaba que esta longitud lateral era 3,8772; el límite más estricto indicado aquí es de Gensane, Thierry; Ryckelynck, Philippe (2005), "Empaquetamientos densos mejorados de cuadrados congruentes en un cuadrado", Discrete & Computational Geometry , 34 (1): 97–109, doi : 10.1007/s00454-004-1129-z , MR  2140885
7. Erdős, P. ; Graham, RL (1975), "Sobre el empaquetamiento de cuadrados con cuadrados iguales" (PDF) , Journal of Combinatorial Theory , Serie A, 19 : 119–123, doi : 10.1016/0097-3165(75)90099-0 , MR  0370368
8. Chung, Fan ; Graham, Ron (2020), "Empaquetamientos eficientes de cuadrados unitarios en un cuadrado grande" (PDF) , Geometría discreta y computacional , 64 (3): 690–699, doi :10.1007/s00454-019-00088-9
9. Roth, KF ; Vaughan, RC (1978), "Ineficiencia en el empaquetamiento de cuadrados con cuadrados unitarios", Journal of Combinatorial Theory , Serie A, 24 (2): 170–186, doi : 10.1016/0097-3165(78)90005-5 , MR  0487806
10. Friedman, Erich, Cuadrados en círculos

Enlaces externos

• Friedman, Erich , "Cuadrados en cuadrados", Github , Centro de empaquetado de Erich