Poner muchos discos en el cuadrado de la unidad

Question

Consideremos un cuadrado de lado igual a $1$ . Demostrar que podemos colocar dentro del cuadrado un número finito de discos disjuntos, con diferentes radios de la forma $1/k$ con $k$ un número entero positivo, tal que el área de la región restante es como máximo $0.0001$ .

Si consideramos todos los discos de esta forma, su área total es $\sum_{k \geq 1}\displaystyle \pi \frac{1}{k^2} - \pi=\frac{\pi^3}{6}-\pi\simeq 2.02$ que es mayor que el área del cuadrado. (He restado $\pi$ porque no podemos colocar un disco de radio $1$ dentro del cuadrado).

Así que los discos de esta forma pueden cubrir muy bien el cuadrado, pero ¿cómo puedo demostrar que hay una familia disjunta que deja fuera una pequeña porción del área?

Answer 1

No creo que esto sea posible para el general $\epsilon$ y dudo que sea posible para el resto $0.0001$ .

A continuación se presentan algunas soluciones con restos inferiores a $0.01$ . Los produje por búsqueda aleatoria a partir de dos configuraciones iniciales diferentes. En la primera, sólo coloqué el círculo con curvatura $2$ en el centro y trató de colocar el resto de los círculos al azar, empezando por la curvatura $12$ ; en la segunda, preposicioné pares de círculos que encajaban en las esquinas e hice una búsqueda determinista del resto.

La estructura de datos que utilicé fue una lista de intersticios, cada uno de los cuales consistía en una lista de círculos que formaban el intersticio (donde las líneas que forman el límite del cuadrado se tratan como círculos con curvatura cero). Recorrí los círculos en orden de curvatura y para cada círculo intenté colocarlo bien en cada una de las cúspides donde se tocan dos círculos en orden aleatorio. Si un círculo no cabía en ninguna parte, lo descartaba; si eso disminuía el área restante por debajo de lo necesario para llegar al valor objetivo (en este caso $0.99$ ), volví a la última decisión.

También lo hice sin usar el círculo con curvatura $2$ . Para ese caso hice una búsqueda completa y no encontré configuraciones con resto menor a $0.01$ . Por lo tanto, si hay una solución mejor en ese caso, debe implicar la colocación de los círculos en un orden diferente. (Siempre podemos transformar cualquier solución en una en la que cada círculo esté colocado cómodamente en una cúspide formada por otros dos círculos, por lo que probar sólo esas posiciones no es una restricción; sin embargo, los círculos con menor curvatura podrían sentarse en las cúspides de los círculos con mayor curvatura, y no habría encontrado esas soluciones).

Para el caso que incluye el círculo con curvatura $2$ La búsqueda no fue completa (no creo que se pueda hacer completamente de esta manera, sin introducir más ideas), por lo que no puedo excluir que haya configuraciones significativamente mejores (incluso con colocación en orden), pero intentaré describir cómo llegué a dudar de que haya mucho margen de mejora más allá de $0.01$ y, en particular, que esto se puede hacer para un $\epsilon$ .

Las razones son tanto teóricas como numéricas. Numéricamente, descubrí que éste parece ser un típico problema de optimización combinatoria: hay muchos mínimos locales, y los mejores están bastante cerca unos de otros. Es fácil llegar a $0.02$ ; es relativamente fácil llegar a $0.011$ ; se necesita un poco más de optimización para llegar a $0.01$ y más allá de eso prácticamente todas las soluciones que encontré estaban dentro de $0.0002$ más o menos de $0.01$ . Así que una solución con $0.0001$ tendría que ser de un tipo completamente diferente a todo lo que encontré.

Ahora, por supuesto a priori puede haber alguna solución sistemática que sea difícil de encontrar mediante este tipo de búsqueda pero que se pueda demostrar que existe. Este podría ser el caso de $0.0001$ pero estoy bastante seguro de que no es el caso para el general $\epsilon$ . Para demostrar que es posible dejar un resto menor que $\epsilon$ para cualquier $\epsilon\gt0$ En este caso, se podría intentar argumentar que, tras una fase inicial, siempre será posible encajar los círculos restantes en el espacio restante. El problema es que tal argumento no puede funcionar, porque estamos tratando de llenar el área racional $1$ descartando los múltiplos racionales de $\pi$ de la superficie total $\pi^3/6$ por lo que no podemos hacerlo descartando un número finito de círculos, ya que $\pi$ es trascendental.

Por lo tanto, nunca podremos llegar a una etapa en la que podamos demostrar que los círculos restantes encajarán exactamente, y por lo tanto cada prueba que demuestre que podemos vencer a un $\epsilon$ tendría que demostrar de algún modo que los círculos restantes pueden dividirse en dos subconjuntos infinitos, y que uno de ellos encaja exactamente en los huecos restantes. Por supuesto, esto también es posible en principio, pero parece bastante improbable; el problema me parece un típico problema de optimización combinatoria desordenada con poca regularidad.

Una razón relacionada para no esperar una solución limpia es que en un Junta apolínea con curvaturas enteras, algunos enteros suelen aparecer más de una vez. Por ejemplo, se podría intentar aprovechar el hecho de que las curvaturas $0$ , $2$ , $18$ y $32$ forman un cuádruple que nos permitiría llenar toda una media esquina con una junta de círculos de curvatura entera; sin embargo, en esa junta, muchas curvaturas, por ejemplo $98$ , se producen más de una vez, por lo que tendríamos que hacer excepciones para ellos, ya que no se nos permite reutilizar esos círculos. Además, si miramos las juntas producidas por $0$ , $2$ y los números de $12$ a $23$ (que son los candidatos a colocarse en las esquinas), verás que el cuarto número aumenta más rápidamente que el tercero; es decir, $0$ , $2$ y $18$ llevar a $32$ mientras que $0$ $2$ y $19$ ya llevan a $(\sqrt2+\sqrt{19})^2\approx33.3$ por lo que no sólo no se pueden colocar todos los números de $12$ a $23$ en las esquinas (ya que sólo dos de ellas encajan y sólo hay cuatro esquinas), pero entonces si se empieza de nuevo con $24$ (que es el siguiente número en la junta iniciada por $12$ ), ni siquiera puedes continuar con la misma progresión, ya que el espacio ha aumentado. La diferencia tendría que ser compensada por el espacio restante en las esquinas que no forma parte de las juntas con el gran $2$ -círculo, pero que es demasiado pequeño para recoger la holgura, lo que hace que sea difícil evitar la caída de varios de los círculos en el rango medio alrededor de los treinta.

Mi impresión del proceso de optimización es que nos vemos obligados a descartar demasiada área bastante pronto; es decir, no podemos esperar a que algunas irregularidades iniciales se asienten en algún patrón regular que podamos explotar. Por ejemplo, la primera solución que se muestra a continuación utiliza todas las curvaturas excepto la siguiente: 3 4 5 6 7 8 9 10 11 16 17 20 22 25 30 31 33 38 46 48 49 52 53 55 56 57 59 79 81 94 96 101 106 107 108 113 125 132. Ya en 49 el área restante es menor que la que se necesitaría para llenar el cuadrado. Otras soluciones que he encontrado difieren en los detalles de los círculos que consiguen introducir, pero el área total siempre es inferior a $1$ temprano. Por lo tanto, parece que son las restricciones irregulares del principio las que limitan lo que se puede conseguir, y esto no se puede compensar con un esquema ingenioso que se extienda hasta el infinito. Incluso se podría demostrar, mediante una búsqueda exhaustiva, que no se puede colocar un conjunto inicial de círculos sin descartar demasiada superficie. Para ser riguroso, habría que tener en cuenta muchas más posibilidades que mi búsqueda (ya que los círculos podrían colocarse en cualquier orden), pero no veo por qué permitir que los círculos más grandes se coloquen más tarde debería suponer una diferencia tan grande, ya que hay muy poco margen de maniobra para su colocación al principio si queremos que quepan la mayoría de los que están entre $12$ y $23$ .

Así que aquí están las soluciones que he encontrado con resto menos de $0.01$ . Las configuraciones mostradas se llenan hasta un área $\gtrsim0.99$ y que le quede una cola de pequeños círculos que valen alrededor de otro $0.0002$ . Para el primero, he comprobado con aritmética de enteros que ninguno de los círculos se superpone. (De hecho, coloqué los círculos con aritmética de enteros, utilizando aritmética de punto flotante para encontrar una aproximación de la posición y una única iteración del método de Newton en aritmética de enteros para corregirla).

La primera configuración tiene $10783$ círculos y se halló mediante una búsqueda aleatoria repetida comenzando sólo con el círculo de curvatura $2$ colocado; creo que corrí algo así como $100$ ensayos separados para encontrar este, y algo así como $1$ en $50$ de ellos encontraron una solución con el resto de la misma $0.01$ Cada prueba tardó un par de segundos en un MacBook Pro.

La segunda configuración tiene $17182$ círculos y se encontró colocando inicialmente pares de círculos con curvaturas $(12,23)$ , $(13,21)$ , $(14,19)$ y $(15,18)$ tocándose en las esquinas y ajustando sus posiciones exactas a mano; el ajuste trajo una ganancia de algo así como $0.0005$ , lo que hizo que el resto se redujera por debajo de $0.01$ . La búsqueda de los círculos restantes se llevó a cabo de forma determinista, en el sentido de que siempre traté de colocar primero un círculo en las cúspides formadas por los círculos más pequeños y las líneas de demarcación; de este modo, se mantenía disponible el mayor espacio contiguo posible en las cúspides entre el círculo grande y las líneas de demarcación.

También intenté colocar pares de círculos con curvaturas $(13,21)$ , $(14,19)$ , $(15,18)$ y $(16,17)$ en las esquinas, pero sólo llegó hasta $0.9896$ con eso.

Aquí están las versiones de alta resolución de las imágenes; están reducidas en esta columna, pero puede abrirlas en una nueva pestaña/ventana (donde quizás tenga que hacer clic en ellas para activar la función de autoescala del navegador) para obtener la resolución completa.

Búsqueda aleatoria:

Con círculos precolocados:

Answer 2

Vamos a remangarnos. Dejemos que $C_k$ denotan el disco de radio $1/k$ . Supongamos que podemos cubrir un área de $\ge 0.9999$ utilizando un conjunto de discos no superpuestos dentro del cuadrado unitario, y que $S$ denotan el conjunto de enteros $k$ tal que $C_k$ se utiliza en esta portada.
Entonces requerimos

$$\sum_{k\in S}\frac{1}{k^2} \ge 0.9999/\pi \approx 0.318278$$

Como el OP señaló, sabemos que $1 \not\in S$ . Esto deja

$$\sum_{k\ge2}\frac{1}{k^2} \approx 0.644934$$

que nos da $0.644934 - 0.318278 = 0.326656$ capacidad de sobra" para jugar.

Caso 1 Supongamos que $2 \in S$ . A continuación, el disco más grande que cabe en los espacios de las esquinas dejados por $C_2$ es $C_{12}$ , por lo que debemos lanzar $3,...,11$ de $S$ . Esto desperdicia

$$\sum_{k=3}^{11}\frac{1}{k^2}\approx0.308032$$

y estamos a punto de agotar nuestra capacidad sobrante: nos quedaríamos con $0.326656-0.308032=0.018624$ para jugar.

Caso 2 Supongamos ahora que $2 \not\in S$ . Entonces podemos encajar $C_3$ y $C_4$ en el cuadrado de la unidad, pero no $C_5$ . Así que desperdiciamos

$$\frac{1}{2^2} + \frac{1}{5^2} = 0.29$$

dejándonos con $0.326656-0.29=0.036656$ para jugar.

Ninguno de estos casos me hace confiar en que esto sea factible.

Answer 3

Sugiero la siguiente idea: Mira http://en.wikipedia.org/wiki/Descartes%27_theorem y en particular los casos especiales. Demostrar inductivamente que todas las curvaturas siguen siendo enteras como en http://en.wikipedia.org/wiki/Apollonian_gasket . Ahora coloque algunos círculos bien elegidos en el cuadrado y quizás rellene hasta las esquinas (ya que el relleno entre una esquina y un círculo no se maneja con Decartes). Todas las demás áreas, es decir, entre los círculos y entre los círculos y los bordes del cuadrado, se pueden rellenar con el teorema de Decartes. Probablemente puedas demostrar analíticamente qué radios vas a utilizar. Ahora suma sus áreas.