Problema de cobertura de Rado

Problema sin resolver en matemáticas

¿Cuál es la disposición de cuadrados con bordes paralelos que tiene el subconjunto de cuadrados que maximiza el área más pequeño en el que los cuadrados del subconjunto no se superponen?

Más problemas sin resolver en matemáticas

El problema de recubrimiento de Rado es un problema sin resolver en geometría que trata sobre cómo cubrir conjuntos planos con cuadrados. Fue formulado en 1928 por Tibor Radó y generalizado a formas más generales y dimensiones superiores por Richard Rado .

Formulación

En una carta a Wacław Sierpiński , motivado por algunos resultados de Giuseppe Vitali , Tibor Radó observó que para cada recubrimiento de un intervalo unitario, se puede seleccionar un subconjunto formado por intervalos disjuntos dos a dos con una longitud total de al menos 1/2 y que este número no se puede mejorar.

Luego pidió una declaración análoga en el avión.

Si el área de la unión de un conjunto finito de cuadrados en el plano con lados paralelos es uno, ¿cuál es el área total máxima garantizada de un subconjunto disjunto dos a dos?

Para que los cuadrados estén lo más separados posible pero aún así se superpongan, $\epsilon$ El símbolo se utiliza para denotar un valor de escala infinitesimalmente pequeño, que expande el cuadrado en esa cantidad desde el centro, y a medida que ese valor se acerca a cero, se aproxima al límite inferior. El área total cubierta por todos los cuadrados en cada se aproxima a 1 a medida que $\epsilon$ Se reduce, y la cantidad cubierta por una selección óptima de cuadrados para estos conjuntos se aproxima a 1/4 (donde los cuadrados seleccionados son rojos). Nótese que existen disposiciones que tienen una selección óptima con un área total ligeramente inferior a 1/4.

{\displaystyle \epsilon } — Para que los cuadrados estén lo más separados posible pero aún así se superpongan, $\epsilon$ El símbolo se utiliza para denotar un valor de escala infinitesimalmente pequeño, que expande el cuadrado en esa cantidad desde el centro, y a medida que ese valor se acerca a cero, se aproxima al límite inferior. El área total cubierta por todos los cuadrados en cada se aproxima a 1 a medida que $\epsilon$ Se reduce, y la cantidad cubierta por una selección óptima de cuadrados para estos conjuntos se aproxima a 1/4 (donde los cuadrados seleccionados son rojos). Nótese que existen disposiciones que tienen una selección óptima con un área total ligeramente inferior a 1/4.

Radó demostró que este número es al menos 1/9 y conjeturó que es al menos 1/4, una constante que no se puede mejorar más. Esta afirmación fue demostrada independientemente para el caso de cuadrados iguales por A. Sokolin, R. Rado y V. A. Zalgaller . Sin embargo, en 1973, Miklós Ajtai refutó la conjetura de Radó, construyendo un sistema de cuadrados de dos tamaños diferentes para el cual cualquier subsistema compuesto por cuadrados disjuntos cubre un área como máximo de $1/4 - 1/1728 \approx 0,2494$ del área total cubierta por el sistema.

Límites superior e inferior

Problemas análogos a la conjetura de Tibor Radó, pero que involucran otras formas, fueron considerados por Richard Rado a partir de finales de la década de 1940. Un escenario típico es una familia finita de figuras convexas en el espacio euclidiano R ^d que son homotéticas a un X dado , por ejemplo, un cuadrado como en la pregunta original, un disco o un cubo d -dimensional . Sea

F(X)=\inf _{S}\sup _{I}{\frac {|I|}{|S|}},

donde S abarca las familias finitas descritas anteriormente, y para una familia S dada , I abarca todas las subfamilias que son independientes , es decir, que consisten en conjuntos disjuntos, y las barras denotan el volumen total (o área, en el caso plano). Aunque el valor exacto de F ( X ) no se conoce para ningún X convexo bidimensional , se dedicó mucho trabajo a establecer límites superiores e inferiores en varias clases de formas. Al considerar solo familias que consisten en conjuntos que son paralelos y congruentes a X , se define de manera similar f ( X ), que resultó ser mucho más fácil de estudiar. Así, R. Rado demostró que si X es un triángulo, f ( X ) es exactamente 1/6 y si X es un hexágono con simetría central , f ( X ) es igual a 1/4.

En 2008, Sergey Bereg, Adrian Dumitrescu y Minghui Jiang establecieron nuevas cotas para varias F ( X ) y f ( X ) que mejoran los resultados anteriores de R. Rado y VA Zalgaller. En particular, demostraron que

0.1179\approx {\frac {1}{8.4797}}\leq F({\textrm {cuadrado}})\leq {\frac {1}{4}}-{\frac {1}{384}}\approx 0.2474,

y eso $f(X)\geq {\frac {1}{6}}$ para cualquier plano convexo X .

Referencias

Ajtai, Miklós (1973), "La solución de un problema de T. Radó", Bulletin de l'Académie Polonaise des Sciences, Série des Sciences Mathématiques, Astronomiques et Physiques , 21 : 61– 63, MR 0319053
Bereg, Sergey; Dumitrescu, Adrian; Jiang, Minghui (2010), "Sobre los problemas de cobertura de Rado", Algorithmica , 57 (3): 538– 561, doi : 10.1007/s00453-009-9298-z , MR 2609053 ; anuncio preliminar en SWAT 2008 , doi : 10.1007/978-3-540-69903-3_27
Croft, Hallard T .; Falconer, Kenneth J .; Guy, Richard K. (1991), Problemas sin resolver en geometría , Libros de problemas en matemáticas, Nueva York: Springer-Verlag, doi : 10.1007/978-1-4612-0963-8 , ISBN 0-387-97506-3, MR 1107516
Radó, Tibor (1928), "Sur un problème relatif à un théorème de Vitali" , Fundamenta Mathematicae , 11 : 228– 229, doi : 10.4064/fm-11-1-228-229 , JFM 54.0098.02
Rado, Richard (1949), "Algunos teoremas de recubrimiento (I)", Actas de la Sociedad Matemática de Londres , Segunda Serie, 51 : 232–264 , doi : 10.1112/plms/s2-51.3.232 , MR 0030782
— — (1951), "Algunos teoremas de recubrimiento (II)", Actas de la Sociedad Matemática de Londres , Segunda Serie, 53 : 243–267 , doi : 10.1112/plms/s2-53.4.243 , MR 0042149
Sokolin, A. (1940), "Sobre un problema de Radó", Actas de la Academia de Ciencias de la URSS , 26 : 871–872 , Zbl 0023.11203
Zalgaller, VA ( 1960), "Замечания о задаче Радо" , Matematicheskoe Prosveshchenie, Ser. 2 (en ruso), vol. 5, págs. 141–148 , Zbl 0145.19203