🔢 mathematics

Greedy Packing of Nested Rings: Placement Rules, a Golden Counterexample, and a Tribonacci Floor

Este artículo demuestra que el empaquetamiento ávido produce el conjunto factible lexicográficamente máximo si rho <= phi en discos planos. Esta garantía de la razón áurea se mantiene para inventarios finitos en el plano, pero se limita a cinco anillos en dimensiones superiores. Para configuraciones de huecos independientes, el umbral nítido para la optimalidad de área es 1/sqrt(2).

Autores originales: Javier Aguilar Martín

Publicado 2026-09-15✓ Author reviewed ⓘ

📖 4 min de lectura🧠 Análisis profundo

CC BY 4.0

Autores originales: Javier Aguilar Martín

Artículo original bajo licencia CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Esta es una explicación generada por IA del artículo a continuación. No ha sido escrita por los autores. Para mayor precisión técnica, consulte el artículo original. Leer descargo de responsabilidad completo

Imagina una cocina donde estás friendo aros de calamar. Tienes una sartén grande y un montón de aros de varios tamaños. Algunos son anchos y planos; otros son estrechos y pequeños. El objetivo es meter tantos aros como sea posible en la sartén sin que se superpongan. Hay un truco ingenioso: un aro pequeño puede encajar perfectamente dentro del centro hueco de un aro más grande, anidándose como un juego de muñecas rusas. Esta configuración física tan simple crea un rompecabezas complejo para los matemáticos. Ellos quieren saber si una estrategia sencilla, paso a paso, funciona mejor. La estrategia consiste en tomar los aros uno por uno, empezando por el más grande, y colocar cada uno donde quepa. Si un aro puede caber dentro del hueco de un aro más grande que ya está en la sartén, lo pones ahí; de lo contrario, lo colocas en el fondo vacío de la sartén. La pregunta es si este enfoque codicioso siempre conduce al mejor resultado, o si se necesita un plan más inteligente y complicado para empaquetar más aros o para maximizar la superficie total de contacto con la sartén.

Este rompecabezas pertenece a un campo de las matemáticas llamado geometría, específicamente al estudio de cómo las formas encajan en el espacio. Durante décadas, los matemáticos han sabido que, para ciertos tipos de problemas de empaquetamiento, una regla codiciosa simple funciona perfectamente. Sin embargo, cuando las formas son anillos que pueden anidarse unos dentro de otros, las reglas cambian. La nueva investigación muestra que la respuesta depende enteramente de cómo se relacionen los tamaños de los anillos entre sí. Si los anillos tienen tamaños muy específicos —donde el radio de cada anillo es significativamente mayor que la suma de los radios de todos los anillos más pequeños—, la estrategia codiciosa está garantizada a ser exitosa. En este escenario, aunque siempre debes procesar los anillos del más grande al más pequeño, no importa qué hueco o lugar específico elijas para cada aro; siempre obtendrás el conjunto factible lexicográficamente máximo.

Sin embargo, los investigadores descubrieron que este comportamiento perfecto tiene un límite nítido. Cuando los anillos no son tan drásticamente diferentes de tamaño, la estrategia codiciosa simple puede fallar. Demostraron que, si tienes cuatro anillos, el método codicioso podría perder la solución óptima, incluso si los anillos tienen tamaños que parecen casi seguros. El punto donde la estrategia deja de funcionar está ligado a un número famoso conocido como la proporción áurea, aproximadamente 1.618. El estudio muestra que mientras el máximo, sobre todos los anillos, del cociente entre la suma de los radios de los anillos más pequeños y el radio del anillo actual sea menor o igual a este número áureo, el método codicioso es seguro para obtener el conjunto factible lexicográficamente máximo. Pero si los anillos más pequeños se vuelven más grandes en relación con el anillo actual (haciendo que la suma de los pequeños sea mayor respecto al actual), la estrategia simple puede romperse, dejando anillos sobre la mesa que podrían haber sido empaquetados.

El equipo también encontró que este fallo no es solo una casualidad de una disposición específica. Construyeron pares de situaciones casi idénticas donde la única diferencia es el tamaño de los anillos más pequeños, y aun así, el método codicioso toma la decisión incorrecta en un caso y la correcta en el otro. Debido a que el algoritmo no puede distinguir estas dos situaciones simplemente mirando el estado actual de la sartén, ninguna regla simple basada en la observación inmediata puede ser perfecta para todos los casos. Los investigadores también exploraron qué sucede si los anillos tienen diferentes grosores o si el contenedor es un cuadrado en lugar de un círculo. Encontraron que, mientras la proporción áurea es el umbral crítico para las sartenes circulares, para las sartenes cuadradas se ha establecido un límite superior de aproximadamente 1.6845, aunque el valor exacto para los cuadrados aún se está investigando.

En última instancia, el trabajo proporciona un mapa claro de cuándo un enfoque simple e intuitivo funciona y cuándo falla. Confirma que para una amplia gama de tamaños, el método codicioso no es solo una buena suposición, sino un óptimo matemáticamente probado para obtener el conjunto factible lexicográficamente máximo. También señala exactamente dónde termina esa certeza, revelando un límite definido por la proporción áurea. Este resultado es significativo porque va más allá de las simulaciones por computadora para proporcionar pruebas rigurosas y escritas que se mantienen verdaderas para cualquier número de anillos en círculos planos, y para hasta cinco anillos en dimensiones superiores. El estudio resuelve una cuestión de larga data sobre la fiabilidad del empaquetamiento codicioso, mostrando que, si bien la simplicidad suele ganar, existe una línea matemática precisa y hermosa donde la complejidad toma el control.

Resumen Técnico: Empaquetamiento Voraz de Anillos Anidados

Planteamiento del Problema
El artículo investiga el problema de empaquetar anillos (anulares) de un ancho común $w$ en un contenedor compacto (la "sartén"), permitiendo que los anillos se aniden dentro de los agujeros de anillos más grandes. El estudio se centra en dos objetivos contrapuestos: maximizar el número de anillos colocados (cardinalidad) y maximizar el área de contacto total entre los anillos y el contenedor. Estos objetivos divergen porque el área de contacto es superaditiva en el radio, mientras que la cardinalidad no lo es.

La cuestión central es determinar las condiciones bajo las cuales un algoritmo voraz descendente (procesando los anillos desde el radio mayor al menor) garantiza encontrar el conjunto de anillos factible lexicográficamente máximo, independientemente de la regla específica utilizada para elegir entre contenedores factibles (por ejemplo, mejor ajuste, peor ajuste o aleatorio). Esta propiedad se denomina olvido de la colocación (placement obliviousness). El artículo busca identificar el umbral exacto $\rho$ (la relación máxima entre la suma de los radios menores y un radio dado) por debajo del cual se cumple este olvido de la colocación, y caracterizar las estructuras geométricas y combinatorias que causan el fallo de los algoritmos voraces. Para contenedores cuadrados, se establece un límite superior para el umbral $\tau_{\square} \le Y \approx 1.6845$ , aunque su valor exacto sigue siendo un problema abierto.

Metodología
El autor emplea un enfoque híbrido que combina análisis geométrico riguroso, optimización combinatoria y verificación formal:

Análisis Geométrico: El artículo utiliza propiedades del empaquetamiento de discos, incluyendo el teorema de los círculos de Descartes, criterios de separación angular para círculos tangentes a la pared y construcciones de "filas" (empaquetamiento de bolas a lo largo de un diámetro). Las herramientas clave incluyen el "lema de la fila" (Lema 3) y construcciones de "bolsillos" específicos (bolsillos de Descartes) que definen los límites del empaquetamiento de tres o más discos.
Reducción Combinatoria: El problema se descompone en una capa geométrica (factibilidad de empaquetamientos hermanos) y una capa combinatoria (selección de anillos). El autor demuestra que bajo radios superincrementales (donde cada radio excede la suma de todos los radios menores), la capa combinatoria se vuelve trivial, reduciendo el problema a un proceso de selección voraz que es óptimo para cualquier objetivo superaditivo.
Argumentos de Intercambio: Para demostrar el olvido de la colocación, el autor utiliza una técnica de "alineación de padres". Demuestran que si una ejecución voraz difiere de un testigo óptimo, se puede construir un nuevo testigo intercambiando la colocación del anillo discordante más grande y reinsertando los anillos desplazados en el espacio vaciado, preservando la factibilidad.
Verificación Formal: El artículo depende fuertemente de la verificación computacional. Un repositorio contiene 122 teoremas de Lean que formalizan identidades algebraicas, desigualdades polinómicas y certificados geométricos específicos. Se utilizan comprobaciones numéricas para explorar espacios de parámetros y generar contraejemplos, pero el autor establece explícitamente que los resultados numéricos no sustituyen a las pruebas escritas o a los certificados formales.

Contribuciones Clave y Resultados

Dicotomía de Superaditividad (Teorema 6): Bajo radios superincrementales, el algoritmo de selección voraz es óptimo para cualquier función objetivo positiva, estrictamente creciente y superaditiva (incluyendo el área de contacto). Sin embargo, para la cardinalidad (que no es superaditiva), existen contraejemplos incluso con radios superincrementales.
Olvido de la Colocación bajo Radios Superincrementales (Teorema 9): Si los radios son superincrementales, cualquier regla para elegir entre contenedores factibles produce el conjunto factible lexicográficamente máximo. Esto se sostiene para formas y dimensiones de contenedores arbitrarias.
Nitidez en $n=4$ (Teorema 13): El olvido de la colocación se cumple incondicionalmente para hasta tres anillos, pero falla para cuatro anillos. El artículo construye "instancias gemelas" (Teorema 14) donde el estado observable (capacidades del contenedor, ocupantes, anillo entrante) es idéntico para dos instancias de problemas diferentes, pero la colocación óptima para el anillo crítico difiere. Esto demuestra que ninguna regla determinista basada en el estado puede tener éxito universalmente, y las reglas aleatorias fallan con una probabilidad de al menos $1/2$ .
El Umbral de Oro ( $\tau = \phi$ ):
- Modelo Aditivo: El umbral para el modelo de sustitución aditiva es exactamente $\rho = 1$ .
- Modelo Geométrico (Discos): El artículo demuestra que el umbral global exacto para los contenedores de discos es la Proporción Áurea $\phi \approx 1.618$ .
- Contraejemplos: Se construye una "familia dorada" de instancias de cuatro anillos donde el olvido de la colocación falla en $\rho = \phi + 3\varepsilon$ . Esto refuta la conjetura natural de que el umbral es la constante de Tribonacci $T \approx 1.839$ .
- Garantía Universal (Teorema 22): Para cualquier inventario finito de discos en el plano con $\rho \le \phi$ , toda ejecución descendente voraz devuelve el conjunto lexicográficamente máximo. Esto se mantiene incluso con radios de agujeros independientes.
El Suelo de Tribonacci: Aunque el umbral global es $\phi$ , el artículo identifica una "subfamilia rígida" de contraejemplos de cuatro anillos donde el ínfimo de $\rho$ es exactamente la constante de Tribonacci $T$ . Esto representa el suelo exacto para una clase específica de intercambios bloqueados que involucran configuraciones geométricas rígidas.
Sartenes Cuadradas: Para contenedores cuadrados, el artículo establece un límite superior para el umbral $\tau_{\square} \le Y \approx 1.6845$ , derivado de una familia algebraica específica. El umbral global exacto para los cuadrados sigue siendo un problema abierto.
Dimensionalidad: Los resultados para contenedores esféricos en dimensiones $d \ge 2$ se transfieren del caso planar mediante un lema de reducción de dimensión. El olvido de la colocación se cumple para hasta tres anillos en cualquier dimensión y falla a los cuatro. Un argumento separado extiende la garantía del umbral dorado hasta cinco anillos en cualquier dimensión.
Agujeros Independientes y Área: Para radios de agujeros independientes, el artículo demuestra un factor de garantía de área exacto de $\min(1, \kappa^{-2} - 1)$ bajo $\rho \le \kappa < 1$ , con un umbral de optimalidad nítido en $1/\sqrt{2}$ .

Significancia y Reivindicaciones
El artículo afirma resolver las cuestiones estructurales relativas al empaquetamiento voraz de anillos anidados, yendo más allá de los enfoques heurísticos para proporcionar umbrales exactos y resultados de imposibilidad.

Optimalidad de lo Voraz: Establece que, bajo la condición $\rho \le \phi$ , el algoritmo voraz garantiza el conjunto de anillos factible lexicográficamente máximo, independientemente de las decisiones de colocación. La optimalidad del área bajo este umbral requiere condiciones adicionales (ancho común y radios superincrementales).
Geométrico vs. Combinatorio: El trabajo desacopla la dificultad del problema en una capa geométrica (NP-duro en general) y una capa combinatoria (resuelta mediante condiciones superincrementales).
Refutación de Conjeturas: Refuta explícitamente la conjetura de que la constante de Tribonacci es el umbral universal, mostrando en su lugar que la Proporción Áurea es el límite correcto para el caso general, mientras que la de Tribonacci permanece como el suelo para una subfamilia rígida específica.
Verificación Rigurosa: El autor enfatiza que sus resultados están respaldados por una combinación de pruebas geométricas escritas y certificados algebraicos formalizados en Lean, distinguiendo su trabajo de estudios puramente numéricos o heurísticos en la literatura de empaquetamiento de círculos.

El artículo concluye que, si bien el umbral global para los discos queda resuelto en $\phi$ , permanecen abiertos problemas relativos al umbral exacto para sartenes cuadradas, los suelos inferiores precisos de familias especializadas de intercambio anidado más allá del caso rígido, y la complejidad computacional de encontrar colocaciones óptimas cuando se permite el acceso total a la entrada.

Resumen Técnico: Empaquetamiento Voraz de Anillos Anidados

Más como este