¿Pueden cubrir plazas de área infinita siempre una unidad cuadrada?

Question

Esta es una afirmación de uno de mis estudiantes hicieron sin justificación en su examen. Definitivamente no era la forma correcta de abordar el problema, pero ahora he sido nerdsniped en tratando de averiguar si es cierto.

Deje $a_i$ ser una secuencia de reales positivos tales que $\sum a_i^2 = \infty$. A continuación, $[0,1]^2$ pueden ser cubiertos por los traduce de las plazas $[0,a_i]^2$.

Definitivamente no es suficiente que el $\sum a_i^2>1$: Usted no puede cubrir una unidad cuadrada con $5$ alineado al eje plazas de sidelength $1/\sqrt{5}$.

Answer 1

Nosotros en realidad sólo necesita $\sum a_i^2 >4$ para que esto se sostenga*. En particular, tenga en cuenta que esta condición implica que hay algunos finito set $I$ de la indexación subconjunto tal que $\sum_{i\in I}a_i^2>4$.

Deje $b_i$ ser la mayor potencia de dos menos que o igual a $a_i$ por cada $i\in I$. Claramente, $2b_i>a_i$. En particular, $\sum_{i\in I}b_i^2>1$. Ahora, podemos construir inductivamente una por cuadrados de lado $b_i$$i\in I$. Para ser más específicos, para cada una de las $k$, vamos a $c_k$ el número de $i\in I$ tal que $b_i=2^{-k}$. Estamos equivalentemente, tratando de cubrir $[0,1]^2$ por una colección de los cuadrados de las potencias de dos en los laterales de longitud, con $c_k$ copias de $[0,2^{-k}]^2$.

Sin embargo, esto es fácil: Vamos a $G_k$ ser la partición** de $[0,1]^2$ se traduce en $[0,2^{-k}]^2$ en la forma obvia (es decir, por rebanar en $2^k$ filas y columnas). Tenga en cuenta que $G_{k+1}$ es siempre un refinamiento** de $G_k$. Entonces, podemos colocar las plazas de mayor a menor; podemos avidez lugar, como muchos de los mayores $c_1$ plazas en $G_1$ como sea posible. Entonces, si la plaza no es completa, podemos poner tantos $c_2$ plazas en el descubierto células de $G_2$ como sea posible - y así sucesivamente. Ya que cada uno es un refinamiento de la última, siempre podemos colocar una plaza nueva, sin superposición de una plaza anterior - a no ser que todo ya está completo. Este proceso debe terminar eventualmente, ya que sólo tiene un número finito de plazas. Sin embargo, desde sus áreas suma a más de uno, y están siendo colocados sin solapamiento, que realmente debe cubrir la plaza.

(*Esta desigualdad no es necesario ser estricto; si se traza a través de la discusión, el hecho de que la desigualdad de $2b_i>a_i$ es de estricta nos permite debilitar la desigualdad para la suma)

(**Esto es todo, hasta los límites de las células, lo que podría cruzan. Pero ya que estamos tratando con un conjunto finito de plazas, la unión está cerrado, por lo que los conjuntos de medida cero no importa de todos modos)

---

He aquí una ilustración del proceso, donde las plazas se supone que tienen potencias de dos, como las longitudes de los lados, $c_1=2$$c_2=5$$c_3=9$$c_4=12$. Observar que no hay realmente nada de lo que podría salir mal:

Answer 2

Una respuesta a explotar la idea de que Se Jagy descritos en los comentarios.

Si hay algo de $a_n\geq 1$ no hay nada que probar, por lo que podemos suponer $0< a_n <1$. No hay nada que probar también si $\limsup a_n>0$, por lo que podemos suponer $\lim_{n\to +\infty}a_n=0$.

Asumiendo $\sum_{n\geq 1}a_n<+\infty$ tendríamos $\sum_{n\geq 1} a_n^2<+\infty$, lo $\sum_{n\geq 1}a_n$ es divergente. Podemos decir que algunos subconjunto finito $S\subseteq \mathbb{N}^+$ es una buena subconjunto si $\sum_{s\in S}a_s\geq 1$ y decidir que el rango de una buena subconjunto es $\min_{s\in S}a_s$. Podemos escoger los buenos subconjunto con el rango más alto (hay un rango más alto desde $\lim_{n\to +\infty}a_n=0$) para cubrir una franja tan alto como el rango de dicho subconjunto, eliminar estos elementos de la secuencia original, re-índice y repetir.

No es difícil mostrar que el conjunto de tiras construido por esto $\min\max$ algoritmo voraz es un cover de la plaza entera, es decir, que la suma de las filas supera en algún momento. Suponiendo que una infinidad de tiras que se produce, el hecho de que estas tiras no cubren toda la plaza, sino $\sum_{n\geq 1}a_n^2$ es divergente conduce a una contradicción.

---

Esto introduce una horriblemente difícil problema:

¿Cuál es el infimum de $r\in\mathbb{R}^+$ tal que para cada secuencia $\{a_n\}_{n\geq 1}$$a_n\in(0,1)$$\sum_{n\geq 1}a_n^2\geq r$, es posible que se cubran $[0,1]^2$ se traduce de $[0,a_1]^2,[0,a_2]^2,[0,a_3]^2,\ldots$?

Answer 3

Deje $(X_i,Y_i)$ ser una secuencia de yo.yo.d. uniforme de las variables en $[0,1]$ y deje $S_i$ ser el cuadrado de lado a $a_i$ centrada en $(X_i,Y_i)$. Deje $(x,y)$ ser un punto en la unidad de la plaza. Entonces

$$\begin{align} \mathbb{P}\left((x,y) \notin \bigcup_iS_i\right)&=\prod_i \bigl(1-\mathbb{P}((x,y)\in S_i)\bigr) \\ &\leq \prod_i \bigl(1-a_i^2/4\bigr). \end{align} $$

Desde $\sum_i a_i^2$ es divergente, $\prod_i \bigl(1-a_i^2/4\bigr)=0$ $(x,y)$ se encuentra en $\bigcup_i S_i$ casi seguramente. De ello se desprende que casi seguramente, $\bigcup_i S_i$ contiene todos los puntos racionales en el interior de la plaza. Tomar una realización de variables $(X_i,Y_i)$ : debe ser posible demostrar que el $\bigcup_i S_i$ cubre de hecho en toda la plaza, incluso si no puedo encontrar un buen argumento para que.

Answer 4

Si $a_i\geq 1$ para un $a_i$ entonces es fácil de hacer, de lo contrario para cada cuadrado independientemente elegir un punto en $[0,1]^2$ uniformemente al azar para ser el centro de ese cuadrado.

Por cada punto $(u,v)$ la probabilidad de que $(u,v)$ está cubierto por esa plaza es al menos $a_i^2/4$ (peor caso es un punto de esquina).

Así que la probabilidad de que $(u,v)$ no es cubierto es $p=\prod_{k=1}^{k=\infty} (1-a_k^2/4) \leq exp(-\sum_{k=1}^{\infty}a_k^2/4)=0$

Edit - ahora no estoy convencido de esto, pensé que el acabado sería sencillo pero no es tanto así.

Answer 5

Nota primero el caso interesante es $a_i \rightarrow 0$, ya que de lo contrario hay infinitamente muchos cuadrados con lado de longitud mayor que en el $\epsilon$. Para considerar este caso. También, sólo necesitamos considerar el caso donde todos los $a_i<1$. El fin de la secuencia de lo que $a_i\geq a_{i+1} \: \forall(i)$.

La línea de los n primeros cuadrados (con longitudes de lado $a_1,a_2,\dots,a_n$) hasta sus longitudes sólo suma a $\geq 1$. Estos cubren un rectángulo cuya altura es $a_n$ (debido a que asumimos que el $a_i$ están disminuyendo). Después de la línea hasta la próxima $m$ plazas hasta sus longitudes sólo suma a $\geq 1$, y traducirlos por $a_n$, de modo que las dos líneas de los cuadrados de cubierta de un rectángulo con altura $a_n + a_m$. Repita.

Deje $a_k$ a ser el lado de la última plaza en la fila $k$. Fila $k+1$ tiene una anchura $<2$, y de cada cuadrado tiene la altura $<a_k$, por lo que el área que cubre es $<2a_k$. Ya que la suma de todas las áreas es $\infty$, debemos tener $\sum a_k =\infty$. Esto significa que el apilamiento de las filas de cuadrados en la parte superior de uno al otro, podemos hacer que la pila arbitrariamente alta. En particular, se puede hacer 1 de alto, de modo que cubra la unidad de la plaza.