¿Cuál es la tasa de crecimiento asintótica del espacio desperdiciado para el empaquetamiento cuadrado en un cuadrado medio entero?
El empaque cuadrado en un cuadrado es un problema de empaque en el que el objetivo es determinar cuántos cuadrados del lado uno (cuadrados unitarios) se pueden empaquetar en un cuadrado de lado. Si es un número entero, la respuesta es , pero la cantidad precisa, o incluso asintótica , de espacio desperdiciado para no enteroses una pregunta abierta. [1]
Pequeños números de cuadrados
El valor más pequeño de que permite el embalaje 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 excepciones únicamente del 5 y 10), el el empaque es el natural con cuadrados alineados con el eje, y es . [2] [3] La figura muestra los empaques óptimos para 5 y 10 cuadrados, los dos números más pequeños de cuadrados para los cuales el empaque óptimo involucra 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 cuadrados unitarios en un cuadrado de lado menor que. Por el contrario, el empaque más estrecho conocido de 11 cuadrados se encuentra dentro de un cuadrado con una longitud lateral de aproximadamente 3,877084, lo que mejora ligeramente un empaque similar encontrado anteriormente por Walter Trump . [6]
Resultados asintóticos
Para valores mayores de la longitud del lado , el número exacto de unidades cuadradas que pueden empacar una el cuadrado permanece desconocido. Siempre es posible empacar un cuadrícula de cuadrados unitarios alineados con el eje, pero esto puede dejar un área grande, aproximadamente , descubierto y desperdiciado. [4] En cambio, Paul Erdős y Ronald Graham demostraron que para un empaque diferente por unidades cuadradas inclinadas, el espacio desperdiciado podría reducirse significativamente a(aquí escrito en notación pequeña o ). [7] Más tarde, Graham y Fan Chung redujeron aún más el espacio desperdiciado, para. [8] Sin embargo, como demostraron Klaus Roth y Bob Vaughan , todas las soluciones deben desperdiciar espacio al menos. En particular, cuandoes 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 lado medio enteros, sigue siendo un problema abierto . [1]
Algunos números de cuadrados unitarios nunca son el número óptimo en un paquete. En particular, si un cuadrado de tamaño permite el embalaje de cuadrados unitarios, entonces debe darse el caso de que y que un paquete de cuadrados unitarios también es posible. [2]
Embalaje cuadrado en círculo
Un problema relacionado es el de empaquetar 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]
Numero de cuadrados | Radio del círculo |
---|---|
1 | 0,707 ... |
2 | 1,118 ... |
3 | 1.288 ... |
4 | 1.414 ... |
5 | 1.581 ... |
6 | 1.688 ... |
7 | 1.802 ... |
8 | 1.978 ... |
9 | 2.077 ... |
10 | 2.121 ... |
11 | 2.214 ... |
12 | 2.236 ... |
Ver también
Referencias
- ^ a b Latón, Peter; Moser, William; Pach, János (2005), Research Problems in Discrete Geometry , Nueva York: Springer, p. 45, ISBN 978-0387-23815-9, MR 2163782
- ^ a b Kearney, Michael J .; Shiu, Peter (2002), "Empaquetamiento eficiente de cuadrados unitarios en un cuadrado" , Electronic Journal of Combinatorics , 9 (1), Documento de investigación 14, 14 págs., MR 1912796.
- ^ Bentz, Wolfram (2010), "Embalajes óptimos de 13 y 46 unidades cuadradas en un cuadrado" , Electronic Journal of Combinatorics , 17 (1), Research Paper 126, MR 2729375
- ^ a b Friedman, Erich (2009), "Envasado de cuadrados unitarios en cuadrados: una encuesta y nuevos resultados" , Electronic Journal of Combinatorics , Dynamic Survey 7, MR 1668055.
- ^ Stromquist, Walter (2003), "Empacando 10 u 11 unidades cuadradas en un cuadrado" , Revista Electrónica de Combinatoria , 10 , Documento de Investigación 8, MR 2386538.
- ^ Gensane, Thierry; Ryckelynck, Philippe (2005), "Empaquetamientos densos mejorados de cuadrados congruentes en un cuadrado", Geometría discreta y computacional , 34 (1): 97–109, doi : 10.1007 / s00454-004-1129-z , MR 2140885
- ^ Erdős, P .; Graham, RL (1975), "Sobre empacar cuadrados con cuadrados iguales" (PDF) , Journal of Combinatorial Theory , Serie A, 19 : 119-123, doi : 10.1016 / 0097-3165 (75) 90099-0 , MR 0370368.
- ^ Chung, Fan ; Graham, Ron (2020), "Empaquetaduras 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 , MR 4156244
- ^ Roth, KF ; Vaughan, RC (1978), "Ineficiencia en el empaquetado 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.
- ^ Friedman, Erich, cuadrados en círculos
enlaces externos
- Cuadrados en cuadrados , Erich's Packing Center, Erich Friedman, Stetson University