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 (venga, 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 n=1 y n=4, 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 n=p^2, entonces s(p^2)=p. Vaya, nos hemos quitado un buen puñado de casos de golpe.

Intentad continuar por vuestra 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 queréis, por ahora pensad qué ocurre con el caso n=5. Os dejo un poco de tiempo para que le deis una vuelta.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

¿Qué tal ha ido? ¿Tenéis 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 mismo 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, podéis verlo aquí: On packing squares with equal squares, y 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 s(5)=2+\frac{1}{\sqrt{2}}. 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 (por Walter Stromquist, Packing 10 or 11 unit squares in a square, donde da también cotas para el caso n=11) que el valor óptimo del lado del cuadrado grande es s(10)=3+\frac{1}{\sqrt{2}}:

Y a partir de aquí ya hay pocos valores de n para los cuales se conozca el valor óptimo de s(n). Para n \le 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:

s(m^2-1)=s(m^2-2)=m, \; \forall m \ge 2

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 os 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 s(m^2-3)=m 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. 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.

Print Friendly, PDF & Email
0 0 votes
Article Rating

¿Te ha gustado la entrada? Puedes invitarme a un café, Gauss te lo agradecerá 😉


Comparte: