embalaje cuadrado

Problema de embalaje bidimensional

El empaquetamiento de cuadrados es un problema de empaquetamiento en el que 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.

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 longitud de lado uno) que se pueden empaquetar dentro de un cuadrado más grande de longitud de lado . Si es un número entero , la respuesta es, pero la cantidad precisa (o incluso asintótica ) de espacio vacío 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 empaquetar 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 la única excepción de 5 y 10), el embalaje es el natural con cuadrados alineados con el eje, y es , donde está el techo (redondo arriba) función. ^{[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 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 más pequeño sin resolver implica empaquetar 11 cuadrados unitarios en un cuadrado más grande. No se pueden empaquetar 11 cuadrados unitarios en un cuadrado de longitud de lado menor que . Por el contrario, el empaquetamiento más apretado conocido de 11 cuadrados está dentro de un cuadrado de longitud de lado aproximadamente 3,877084 encontrado por Walter Trump . ^{[6] [4]} ${\displaystyle \textstyle 2+2{\sqrt {4/5}}\approx 3.789}$

Resultados asintóticos

Problema no resuelto en matemáticas :

¿Cuál es la tasa de crecimiento asintótico del espacio desperdiciado al empaquetar cuadrados en un cuadrado semientero?

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

Para valores mayores de la longitud del lado , se desconoce el número exacto de cuadrados unitarios que pueden llenar un cuadrado. Siempre es posible empaquetar una cuadrícula de cuadrados unitarios alineados con sus ejes, pero esto puede dejar un área grande, aproximadamente , descubierta y desperdiciada. ^[4] En cambio, Paul Erdős y Ronald Graham demostraron que para un embalaje diferente mediante cuadrados unitarios inclinados, el espacio desperdiciado podría reducirse significativamente a (aquí escrito en pequeña notación o ). ^[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 al menos espacio . 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ótica precisa del espacio desperdiciado, incluso para longitudes de lados semienteros, 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}$

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

Embalaje cuadrado en 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. Aquí hay soluciones mínimas para n hasta 12: ^[10]

Ver también

• Embalaje circular en un cuadrado.
• Cuadrando el cuadrado
• Embalaje rectangular
• Problema con el sofá en movimiento

Referencias

1. Latón, Peter; Moser, William; Pach, János (2005), Problemas de investigación en geometría discreta, Nueva York: Springer, p. 45, ISBN 978-0387-23815-9, LCCN  2005924022, SEÑOR  2163782
2. Kearney, Michael J.; Shiu, Peter (2002), "Efficient packaging of unit squares in a square", Electronic Journal of Combinatorics , 9 (1), Research Paper 14, 14 págs., MR  1912796
3. Bentz, Wolfram (2010), "Empaquetamientos óptimos de 13 y 46 cuadrados unitarios en un cuadrado", The Electronic Journal of Combinatorics , 17 (R126), arXiv : 1606.03746 , doi : 10.37236/398, MR  2729375
4. Friedman, Erich (2009), "Empacar cuadrados de unidades en cuadrados: una encuesta y nuevos resultados", Electronic Journal of Combinatorics , Dynamic Survey 7, MR  1668055
5. Stromquist, Walter (2003), "Empacar 10 u 11 cuadrados unitarios en un cuadrado", Electronic Journal of Combinatorics , 10 , Research Paper 8, MR  2386538
6. Gensane, Thierry; Ryckelynck, Philippe (2005), "Empaquetamientos densos mejorados de cuadrados congruentes en un cuadrado", Geometría computacional y discreta , 34 (1): 97–109, doi : 10.1007/s00454-004-1129-z , SEÑOR  2140885
7. Erdős, P .; Graham, RL (1975), "Sobre empaquetar 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, ventilador ; Graham, Ron (2020), "Empaquetamientos eficientes de cuadrados unitarios en un cuadrado grande" (PDF) , Geometría computacional y discreta , 64 (3): 690–699, doi :10.1007/s00454-019-00088-9
9. Roth, KF ; Vaughan, RC (1978), "Ineficiencia al empaquetar 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 embalaje de Erich