Check the new version here

Popular channels

El problema del empaquetamiento de cuadrados en un cuadrado





El problema del empaquetamiento de cuadrados en un cuadrado






Imagina que tienes un puñado de cuadrados de lado uno y quieres meterlos dentro de otro cuadrado de forma que no se superpongan entre ellos (te dejamos que, como mucho, se toquen en los bordes) de la manera más eficiente posible. Está claro que dependiendo de cuántos cuadrados quieras meter necesitarás un cuadrado de un tamaño u otro. Pues ése es el problema del empaquetamiento de cuadrados en un cuadrado (en inglés, Packing squares in a square):



Dados n cuadrados de lado uno, ¿cuál será el lado, S(n), del cuadrado más pequeño posible en el que podemos empaquetar esos n cuadrados?



Vamos a analizar qué ocurre con los primeros valores de n para ir metiéndonos un poco en el problema:



Si tenemos un único cuadrado de lado uno, n=1, está claro que el lado del cuadrado más pequeño posible en el que podemos meterlo es también 1, por lo que S(1)=1:






Si tenemos dos cuadrados de lado uno, n=2, necesitaremos un cuadrado de lado 2, por lo que S(2)=2:






Con tres cuadrados de lado uno, n=3, es sencillo ver que debe ser también S(3)=2:






Para cuatro cuadrados, n=4, también parece evidente que S(4)=2:





Paremos aquí un segundo. Si echamos un vistazo a los casos y vemos que en ambos casos el lado coincide con la raíz cuadrada del números de cuadrados de lado uno. ¿Será esto siempre así? Pues sí: se tiene que si , entonces . Nos hemos quitado un buen puñado de casos de golpe.



Intenten continuar por su cuenta. ¿Qué longitud del lado necesitaremos si queremos empaquetar 5 cuadrados de lado uno? ¿Y si queremos empaquetar 6? ¿Qué ocurrirá con valores más grandes? ¿Habrá alguna regla que determine el lado en función del número de cuadraditos? Si quieren, por ahora, pueden pensar qué ocurre con el caso n = 5. Les doy un poco de tiempo.



.


.


.


.


.


.


.


.


¿Qué tal les ha ido? ¿Tienen alguna conjetura sobre cuál puede ser la respuesta correcta? Antes de continuar, vamos a comentar algo más de este problema.



Parece ser que uno de los primeros en darle algo de “fama” al problema fue Paul Erdős al publicar un artículo junto a Ron Graham en 1975 relacionado con el tema. Más concretamente, no estaba relacionado con el número de cuadraditos o la longitud del cuadrado en sí sino con el área que queda libre cuando colocamos los cuadraditos. El artículo, publicado en el Journal of Combinatorial Theory en 1975, básicamente lo que demostraba es que ese área era sorprendentemente pequeña, lo que significa que cantidades grandes de cuadrados de lado uno se podían empaquetar en un cuadrado de manera sorprendentemente eficiente (después el propio Graham mejoró el resultado de ese paper en Packing equal squares into a large square junto a Fan Chung).



Fue Frits Göbel quien dirigió el problema hacia encontrar empaquetamientos eficientes en lo que se refiere al valor mínimo del lado del cuadrado en el que se empaqueta. En los años posteriores mucha gente se preocupó por este tema, y se avanzó tanto en el cálculo de nuevos valores de s(n) como en el descubrimiento de nuevas configuraciones para valores ya conocidos, así como en el desarrollo de nuevas técnicas para descubrir el valor del lado para un número de cuadraditos más grande. Sigamos con los casos e iremos descubriendo algunos de estos avances.



A partir de n=5 la cosa se comienza a complicar, ya que a partir de aquí empiezan a aparecer (en algunos casos) valores de s(n) que no son números enteros. En este caso concreto, se tiene que . Una posibilidad (quizás la única) de colocación de los cuadrados sería la siguiente:





Seguimos con n=6. En este caso damos un pequeño salto y volvemos a un número entero, ya que está demostrado que S(6)=3:





El caso n=7 parece ser que es más duro de probar, pero se sabe que S(7)=3 también:





Para n=8 tenemos el mismo valor que en los dos anteriores: S(8)=3. Aquí podéis ver una configuración de cuadraditos:





Como n=9 es el cuadrado de 3, se sabe por lo comentado un poco más arriba que S(9)=3:





En el caso en el que n=10 también está demostrado que el valor óptimo del lado del cuadrado grande es





Y a partir de aquí ya hay pocos valores de n para los cuales se conozca el valor óptimo de S(n). Para n ≤ 100, en la mayoría de los casos lo que tenemos son cotas superiores e inferiores de S(n); para n > 100 no he conseguido encontrar información, por lo que posiblemente ni siquiera se tengan dichas cotas en la gran mayoría de los casos.
El principal culpable de que sepamos el lado óptimo para algunos valores por encima de 10 es Hiroshi Nagamochi. Este matemático japonés demostró en 2005, en su trabajo Packing unit squares in a rectangle, lo siguiente:






Este resultado nos da muchos más valores de S(n). Por ejemplo, S(14)=S(15)=4:






También nos dice que S(23)=S(24)=5:






Tendríamos que S(34)=S(35)=6:






Y que S(47)=S(48)=7:





Y así sucesivamente.

Todas las imágenes de las configuraciones de cuadraditos que les muestro aquí están sacadas del paper Packing unit squares in squares: a survey and new results, en el que Erich Friedman hace un repaso de la historia de este problema y da demostraciones para muchos de los casos conocidos, además de comentar las cotas para muchos valores menores que 100 y citar quiénes las encontraron. Friedman tiene además una web, Erich’s place, en la que habla sobre multitud de problemas. En relación con lo que nos ocupa en esta entrada, la web posee una sección, Packing center, en la que además de trata este tema de los empaquetamientos de cuadrados en un cuadrado y muchos otros tipos de empaquetamientos: triángulos en cuadrados, círculos en cuadrados, triángulos en triángulos, círculos en hexágonos, cuadrados en dominós, círculos en pentágonos… Vale la pena echarle un buen vistazo.

Bueno, ¿entonces los descubrimientos en relación con este problema se quedan en lo comentado hasta aquí? Pues eso creía yo…hasta que encontré Optimal packings of 13 and 46 unit squares in a square, de Wolfram Bentz. En él, como el propio título indica. Bentz encuentra el valor óptimo del lado del cuadrado en el que podemos empaquetar 13 y 46 cuadraditos de lado uno. Concretamente, demuestra que S(13)=4 y que S(46)=7, siendo en ambos casos la configuración igual que en los casos n=14 y n=47 respectivamente, pero con un cuadradito menos:





Por tanto, lo que demuestra Bentz es que para m=4 y m=7, y comenta que sus estudios sugieren que esta fórmula también se cumpliría para m=5 y m=6, aunque hasta donde yo sé no hay demostraciones de este hecho ni para esos ni para otros valores. De hecho, hasta donde yo he podido indagar no existen más valores de n para los cuales se conozca el valor óptimo de S(n), aunque si tenemos en cuenta que el trabajo de Bentz se publicó en 2010 puede que en los últimos años se haya hecho algún otro avance. Si alguien tiene noticias sobre ello (con enlaces a papers si puede ser) estaré muy agradecido si lo comenta.



La idea de este post me vino después de ver esta entrada de Visualizing Math, y debo decir que me ha encantado conocer cosas sobre estos tipos de empaquetamientos. Pueden buscarlo y ver otros tntos ejemplos:





Además, he descubierto que hay gente que va un poco más allá y estudia ¡¡empaquetamientos en un toro!!: Packing in a torus. Las matemáticas pueden ser maravillosas.


http://arxiv.org/abs/1110.5348




Packing Squares in a Torus

Don Blair, Christian D. Santangelo, Jon Machta
(Submitted on 24 Oct 2011 (v1), last revised 19 Mar 2012 (this version, v2))
The densest packings of N unit squares in a torus are studied using analytical methods as well as simulated annealing. A rich array of dense packing solutions are found: density-one packings when N is the sum of two square integers; a family of "gapped bricklayer" Bravais lattice solutions with density N/(N+1); and some surprising non-Bravais lattice configurations, including lattices of holes as well as a configuration for N=23 in which not all squares share the same orientation. The entropy of some of these configurations and the frequency and orientation of density-one solutions as N goes to infinity are discussed.


El empaquetamiento más denso de plazas de unidad de N de toros es estudiado utilizando métodos analíticos y simuladores recocidos. Se logran una gran variedad de soluciones de empaquetamiento: una densidad de embalaje cuando N es la suma de dos cuadrados enteros; una familia de soluciones de enrejado de Bravais "albañil calibrada" con densidad N/(N+1); y algunos sorprendentes no Bravais de enrejado de configuraciones, incluyendo enrejados de agujeros, así como una configuración para N = 23, en el que no todos los casilleros comparten la misma orientación. La entropía de algunas de estas configuraciones y la frecuencia y orientación de una densidad de soluciones se discuten como que N tiende infinito.




Eso fue todo




+3
16
0
12
16Comments
      mikeisx

      Falto el resumen nivel 5, da pereza leer tanto y solo por un cuadrado.

      0
      chizzo73

      Los puse en comentarios, básicamente el resumen lvl 5 podría ser este

      +1
      elbetu

      Por favor que alguien le ponga el baile del cuadrado...

      0
      smashrd
      guachopario

      Le pifiaste de toro me parece

      +1
      Reptilisimo

      ahh el famoso torus, tanto placer concentrado en una simple argolla

      +1
      Peter_Gunn
      +2
      geekdude

      No entendi ni mierda solo se que esto es inteligencia colectiva y por eso te di +10

      0
      geekdude

      @chizzo73
      😁 😁 😁

      +1
      Ess41

      resumen?

      0
      chizzo73
      +2
      Krrosis

      Alta pereza mental me provoca con solo ver los dibujitos

      +1
      capitanperico
      0
      chizzo73

      una variante muy interesante

      +1
      misdocumeno
      +2