Problema de empaquetado: Un alucinante desafío matemático con increíbles aplicaciones prácticas

Un problema de empaquetado es básicamente cómo lograr meter la mayor cantidad de objetos en un espacio determinado sin que haya superposición.

Guía de: Matemáticas

En el año 1977 se lanzaron al espacio las dos naves espaciales mellizas Voyager 1 y 2 iniciando así su viaje interestelar, llegando donde ningún otro objeto humano ha llegado jamás. Para más detalles de este hermoso proyecto pueden clickear aquí.

Uno de los problemas que los ingenieros de la NASA tuvieron que resolver para asegurar el éxito de esta misión era lograr, con el equivalente energético de una ampolleta, enviar fotos a color de por ejemplo Saturno y Júpiter llegado el momento.

problema empaquetado

Foto: Internet

La conversión digital de 24 bits enviada a través de ondas de radio por el espacio hasta la tierra sufriría una distorsión enorme de la señal que sería cada vez peor a medida que la distancia aumentara. Para poder corregir estos errores la idea era codificar las señales en secuencias fuertemente distinguibles, es decir, que se pueden reconocer unas de otras aun teniendo bits corruptos. Pero mientras menos secuencias se permitan más lenta sería la transmisión de la información. El problema finalmente se podía plantear geométricamente como un problema de empaquetado esférico en 24 dimensiones.

Un problema de empaquetado es básicamente cómo lograr meter la mayor cantidad de objetos en un espacio determinado sin que haya superposición.

De hecho, gran parte de los problemas de comunicación digital y almacenamiento desde DVD’s, celulares hasta la internet se relacionan con un problema de empaquetado. Los matemáticos llevan siglos trabajando en estos problemas atraídos tanto por su aplicabilidad como por su dificultad. Es un campo donde se logra avanzar poco en un contexto general y cada problema se resuelve de manera particular. Tanto es así que por ejemplo no se sabe todavía como empaquetar de manera óptima con pentágonos regulares en el plano. Se conjetura que la mejor solución se logra formando dos patrones regulares de pentágonos con orientación invertida que pueden ver en el siguiente link.

Lo curioso es que el problema de empaquetado esférico en 3 dimensiones es algo que vemos todos los días en el supermercado con las pirámides de naranjas y otros frutos esféricos que se exhiben para la venta. La idea es bastante natural y simple de implementar, se acomodan en un plano una primera capa de naranjas para luego formar una segunda capa sobre la primera centrando las naranjas de la capa superior en el centro formado por 4 naranjas contiguas y así sucesivamente hasta llegar al último nivel formando una pirámide.

Si inicialmente teníamos una base de  naranjas entonces el total de naranjas en la pirámide será la suma siguiente:

problema empaquetado

Foto: Internet

Esto porque en cada nivel se pierde una fila y una columna de naranjas. Está suma se puede calcular con una simple fórmula que se enseña en casi cualquier curso de Álgebra Elemental que no requiere de realizar las sumas:

problema empaquetado

Foto: Internet

Esta solución aprovecha aproximadamente un 74% del espacio y fue propuesta por Johannes Keppler en 1611. A pesar de lo simple e intuitiva que parece la respuesta, la demostración de que esta era la mejor solución fue solo resuelta en 1998 por el matemático Thomas Hales de la Universidad de Princeton y publicada en los Annals of Mathematics, una de las revistas de más prestigio en el mundo matemático. Su demostración utilizaba una ecuación de 150 variables y recogía 5,000 agrupamientos posibles de esferas con más de 3 gigabytes  de código. Los doce revisores de la revista indicaron que estaban seguros en un 99% de la validez del resultado.

Ahora, una nueva técnica computacional por primera vez ha permitido avances en un número importante de casos que habían resistido el progreso durante décadas. Los matemáticos Christine Bachoc de la Universidad de Burdeos en Francia, y Frank Vallentin de la Universidad de Colonia en Alemania, desarrollaron una técnica en 2008, llamada “límites de programación semidefinidos”. Esta técnica da estimaciones generales sobre el empaquetamiento más denso de los objetos, a través del cálculo de un límite superior que se puede bajar gradualmente hasta la solución exacta haciendo  el cálculo cada vez más detallado.

Uno de los inesperados e intergalácticos beneficiados por este avance ha sido el Voyager. En un par de artículos publicados en Mayo de 2012 y noviembre de 2013 en IEEE Transactions on Information Theory, han mejorado los códigos con un rango de longitud de 18 a 28 bits.

Más sobre Matemáticas

Comentarios Deja tu comentario ↓
Síguenos en Facebook X