El problema de la tabla 2 dimensiones

Question

Estábamos tratando de resolver este maravilloso problema, pero no hemos logrado resolverlo.

Es así: Sea $R=[0,1]^2$, y $D\subseteq R$ un conjunto convexo que interseca cada lado de $R$. Define una tabla como un conjunto del tipo $[a,b]\times[0,1]$ o $[0,1]\times[a,b]$. Las tablas son paralelas a los ejes. Demuestra que para cada conjunto de tablas que cubre $D$, se cumple que la suma de las áreas de las tablas es al menos 1.

Gracias, LLAP.

Una pista del oráculo: El Teorema del Matrimonio. (Todavía no lo hemos resuelto)

Answer 1

Como prometí, aquí es una solución geométrica, sin "Matrimonio " Teorema" (también me gustaría ver una solución que se usa).

Una observación con respecto a métodos probabilísticos.: No creo que la medida de Lebesgue en $R$ es el objeto correcto aquí, desde $D$ tiene medida de Lebesgue cero (si $D$ es igual a la diagonal de $R$). Yo sospecho, sin embargo, que hay una prueba usando una medida de Lebesgue en $R$, que detecta "anchos" de subconjuntos en lugar de sus áreas (ver mi comentario sobre George Lowther de la prueba). Sin embargo, no sé cómo construir uno (al menos, sin primero probar el Teorema 1).

A continuación es mi solución casi completamente reescrito (que originalmente se perdió dos casos).

Voy a etiquetar los vértices de $R$ $a=(0,0), b=(0,1), c=(1,1), d=(1,0)$. Por el "ancho" de un tablón me refiero a la longitud de su lado más corto. Yo deje de $\pi_1, \pi_2$ denotar las proyecciones de $R$ a su lado horizontal $ad$ vertical y lateral $ab$ respectivamente.

Teorema 1. Para cada colección finita $C$ de planchas que cubren $R$, el ancho total $W$ de $C$ es $\ge 1$.

Prueba. La prueba es por inducción sobre el número total de $N$ de tablones. Si $N=1$, es claro que $W\ge 1$.

Ahora, considere el caso $N=2$ cuando $C$ consistir en una tabla vertical $P$ y uno horizontal tablón $Q$ de los anchos $v$ y $w$, respectivamente. (El caso $N=2$ con sólo dos horizontales o dos verticales tablones reduce inmediatamente para $N=1$.)

Lema 1. Si $N=2$, entonces $W=v+w\ge 1$.

Prueba. Desde $D$ cruza todos los cuatro lados de $R$, considerar el cuadrilátero $D'=x_1y_1x_2 y_2\subconjunto D$ donde $x_1\ad\cap D', x_2\ac\cap D', y_1\ab\cap D', y_2\cd \cap D'$. Los tablones de $P$ y $Q$ romper los bordes de $R$ en subsegments de las longitudes de $g_1, g_2$ y $h_1, h_2$, consulte la figura a continuación. Yo sólo considerará el caso crítico se muestra en la figura, donde los segmentos de $y_1x_2, x_2y_2, y_2x_1, x_1y_1$ pasar a través de los cuatro puntos de intersección de $z_1, z_2, z_3, z_4$ de los límites de las tablas (si este no es el caso, uno puede modificar $D'$, $P$ y $Q$, de modo que la anchura total de $P$ y $Q$ estrictamente disminuye y todavía cubierta $D'$).

Considerar la sombra de rectanges como en la figura: Rectángulos marcados con el mismo color tienen la misma área. El área total de los cuatro sombra rectanges adyacentes a las esquinas de $R$ es igual a $$(h_1+h_2)(g_1+g_2)= (1-v)(1-w).$$ Por otro lado, el área de la rectange $z_1 z_2 z_3 z_4$ equivale a $vw$ y, claramente, el área total de los rectángulos sombreados en el interior de $z_1 z_2 z_3 z_4$ igual $(1-v)(1-w)$. Por tanto, tenemos $$(1-v)(1-w)\le vw$$ $$1\le v+w=W,$$ como se reivindica. qed.

Ahora, vamos a $N\ge 3$ y supongamos que para cada colección de $<$ N, planchas, $W\ge 1$. Ahora voy a considerar sólo las colecciones de tablas donde cada tabla es diferente de la totalidad de los $R$ (de lo contrario, la demanda es clara).

Considere la posibilidad de una colección $C$ de tablones que consta de $m$ vertical de tablones de $P_i$ y $n$ listones horizontales $Q_j$, donde $m\le$ n (de lo contrario podemos cambiar las coordenadas verticales y horizontales) y $N=m+n\ge 3$. I número de la vertical de tablones de $P_i$ de izquierda a derecha. Sin pérdida de generalidad, podemos suponer que la vertical de tablones son disjuntos a pares y listones horizontales también son pares distintos (de lo contrario, se amalgaman la no-discontinuo vertical/horizontal de tablas, sin aumentar el ancho total $W$ y reducir el número de tablas). Por la misma razón, podemos asumir que cualquier subconjunto de $C$ no cubre $D$.

El complemento $$D\setminus \bigcup_{i=1}^m P_i$$ es una unión de conjuntos convexos $D_j$. Yo también la cantidad de $D_j$'s de izquierda a derecha. Cada $D_j$ está cubierto por exactamente un tablón horizontal (por el disjointness de la propiedad). Por lo tanto, la cantidad de $k$ de los conjuntos convexos $D_j$ es $\le$ n. Además, $k\in \{m-1, m, m+1\}$ puesto que existe exactamente un $D_j$ entre cada consecutivos par $P_i, P_{i+1}$. Desde $m\le$ n, se sigue que, en la mayoría de los que uno de los pilares de $Q_i$ cubre las dos componentes de $D_j$, lo que significa que $$k-1\le n\le k.$$ Mediante la combinación de estas desigualdades, vemos que $$m\le k\le m+1,$$ y, por lo tanto, $P_1$ o $P_m$ no contiene uno de los dos lados verticales de $R$. (Supongo que es de $P_1$ que no contiene $ab$, de lo contrario, podemos cambiar la orientación.) Por último, si $k=m$ (i.e, $P_m$ $cd$) $n=k=m$ y, por lo tanto, cada tabla $Q_i$ cubre exactamente uno de los componentes de $D_j$. En cualquier caso, yo deje de $Q_1$ denotar el tablón horizontal que cubre $D_1$.

Caso 1: $k=$ n, es decir, de cada $Q_i$ cubre exactamente una $D_i$, $i=1,...,$ n. Como hemos señalado anteriormente, el componente $D_1$ tiene intersección no vacía con el segmento vertical de $ab$. Deje de $h_1$ denotar la longitud de la proyección de $\pi_2(D_1)\subconjunto ab$ y dejar $v_1$ denotar la longitud de la proyección de $\pi_1(D_1)$ de $D_1$. Desde $D_1$ está cubierto por un $Q_1$, es claro que la anchura de $Q_1$ es $\ge h_1$.

Lema 2. $v_1\le h_1$.

Prueba. Considere la posibilidad de un punto de $x\in D_1\cap ab$ y el segmento de $yz=D_1\cap P_1$. El triángulo de $\Delta=xyz$ contenida en $D_1$. Por otra parte, la convexidad de $D$ y el hecho de que se cruza todos los cuatro lados de $R$ implica que los rayos de $x$ extender los segmentos de $xy$ y $xz$ ambos cruzan la unión de los segmentos horizontales $ac\copa da$. Es entonces un geométricas elementales de cálculo a la conclusión de que la altura de $v_1$ (desde el vértice de $x$) de $T$ es $\le$ de la longitud de la base de $yz$ de $T$. El último es de $\le h_1$. qed.

Deje de $P_0\subconjunto de R$ denotar la tabla vertical que es el producto de $\pi_1(D_1)\times ab$ ($P_0$ no es una parte de nuestra colección $C$ de tablones). Por el Lema 1, el ancho de $P_0$ es $\le$ el ancho de $Q_1$.
A continuación, reemplace $Q_1$ con $P_0\copa P_1$. Desde $Q_1$ cubre sólo el componente de $D_1$, lo que sigue es que la nueva colección de $C'$ de tablones todavía cubre $R$. Por el Lema 1, $C'$ ha anchura total $W'\le W$ y, por construcción, $C'$ consiste en $N-1$ tablones. Por lo tanto, por la inducción de la asunción, $1\le W'\le W$ y ya está. Esto concluye la prueba del Teorema 1 en el Caso 1.

Caso 2: $n=k-1$. Entonces $k=m+1$, $n=m$.

Subcase 2a: $Q_1$ cubre $D_1$ y (después de renumeración si es necesario) con un horizontales claras tablón de $Q_n$ cubre $D_{n+1}$. A continuación, repetimos el argumento del Caso 1 y a la conclusión de que $W\ge 1$.

Subcase 2a: $Q=Q_1$ abarca tanto a los $D_1$ y $D_{n+1}$. A continuación, cambiar las funciones de las direcciones horizontal y vertical (esto es ACEPTAR desde $n=m$). Repitiendo este caso-por-caso de análisis llegamos a la conclusión de que existe una tabla vertical $P:=P_\ell$ que abarca dos componentes de $E_1, E_{n+1}$ de $$R\setminus \bigcup_{i=1}^n Q_i.$$ Los componentes de $E_1, E_{n+1}$ no vacío intersecciones con los lados horizontales de $R$. Ahora, elija de cada subconjunto de $D_1, D_{m+1}, E_1, E_{n+1}$ un punto de $y_1, y_2, x_1, x_2$ que pertenece a un lado de la $R$.

Lema 3. El convex hull $D'$ de $x_1, x_2, y_1, y_2$ es cubierto por los tablones de $P$ y $Q$.

Prueba. Esto es suficiente para mostrar que cada borde de $D'$ contenida en $K=P\copa Q$. Supongamos que existe un borde de $D'$ (después de reetiquetar, podemos asumir que este borde es de $x_1y_1$), el cual no está incluido en los $P\copa Q$. Deje de $x_1'\en x_1y_1$ y $y_1'\en x_1y_1$ ser los puntos de intersección del límite de $K$ con $x_1y_1$ (estos puntos de intersección son etiquetados de modo que $x_1'$ pertenece a la parte izquierda de $s_1$ de $P$ y $y_1'$ pertenece a la parte inferior de $t_1$ de $P$. Deje de $z_1'=s_1\cap t_1$; a continuación, el sólido ángulo recto del triángulo de $x_1'y_1'z_1'$ no está cubierto por $P\copa Q$. Sin embargo, por el disjointness propiedad de las tablas, si se sigue que un pequeño rincón de $x_1'y_1'z_1'$ en el vértice de $z_1'$ no está cubierto por ninguna tablón en $C$.

Contradicción. qed.

En vista del Lema 3, ahora podemos aplicar el Lema 1 (ya tenemos una cobertura de $D'$ por dos tablones) y a la conclusión de que el ancho total de $P$ y $Q$ es $\ge 1$.

Esto concluye la prueba del Teorema 1. qed

Me dio una demostración del Teorema 1 para finitos colecciones de tablones. Una aproximación fácil argumento implica que la misma conclusión se sostiene para los contables de las colecciones de los tablones. (Por innumerables colecciones, la declaración no tiene sentido, como lo que puedo decir.)

Teorema 1 es un caso especial de mucho más difícil teorema (teorema 2, a continuación) probado por T. Bang en

Una solución para el "Tablón Problema", Actas de la AMS, 2 (1951).

El "Tablón de Problema" en sí mismo era el planteado por A. Tarski en 1932.

Teorema 2: Deje que $D\subconjunto de R^d$ ser un delimitada subconjunto convexo y $C$ es una contables de la colección de planchas que cubren $D$. A continuación, el ancho total de $C$ es $\ge$ el ancho de $D$.

Aquí están las definiciones de: Un tablón en $R^d$ es la región cerrada delimitada por dos paralelas hyperplanes. El ancho de una tabla es la distancia entre el hyperplanes. El ancho total de $C$ es la suma de la anchura de las tablas en $C$. El ancho de $D$ es el infimum de las longitudes de sus proyecciones ortogonales a las líneas rectas en $R^d$.

La explosión de la prueba es inteligente y nonelementary. Esto ha llevado a una serie de problemas, algunos de los cuales todavía están abiertos. Lee aquí para saber más sobre él.

Answer 2

Aquí hay una prueba alternativa, usando un método de 'acoplamiento' probabilístico, a través del siguiente Lema. A lo largo, dejo que $D$ sea como en la pregunta: un subconjunto convexo de $R=[0,1]^2$ que intersecta cada uno de los cuatro lados de $R.

Lema: Existen variables aleatorias $U_1,U_2$ (definidas en algún espacio de probabilidad) que son ambas uniformes en $[0,1]$, y tal que $(U_1,U_2)$ está en $D$ con probabilidad 1.

[Nota: Aunque $U_1$ y $U_2$ aquí tienen la distribución uniforme, no hay necesidad de que la distribución conjunta de $(U_1,U_2)$ sea uniforme, o incluso tener una distribución absolutamente continua. Por ejemplo, si $D$ es una de las diagonales del cuadrado unitario, que tiene medida de Lebesgue cero pero satisface los requisitos, entonces tomaríamos $U_1=U_2$ (o $U_1=1-U_2). Esto asegura que$(U_1,U_2)\in D$y, si$U_2$se elige con la distribución uniforme, entonces$U_1$ también es uniforme.

Si $A\subseteq[0,1]$ es el conjunto de coordenadas $x$ de las tablas verticales, entonces es una unión finita de intervalos cerrados, las tablas verticales cubren la región $A\times[0,1]$ y tienen un área total de $\lambda(A)$ ($\lambda$ es la medida de Lebesgue). De manera similar, si $B\subseteq[0,1]$ es el conjunto de coordenadas $y$ de las tablas horizontales entonces cubren la región $[0,1]\times B$ y tienen un área total de $\lambda(B)$. El siguiente corolario del lema anterior es entonces una respuesta positiva a la pregunta original.

Corolario: Si $A,B$ son subconjuntos medibles de $[0,1]$ tales que $D\subseteq(A\times[0,1])\cup([0,1]\times B)$, entonces $\lambda(A)+\lambda(B)\ge1.

Prueba: Tomando $U_1,U_2$ como variables aleatorias uniformemente distribuidas en $[0,1]$ con $(U_1,U_2)\in D$ (casi seguramente), \begin{align} \lambda(A)+\lambda(B)&=\mathbb{P}(U_1\in A)+\mathbb{P}(U_2\in B)\\ &\ge\mathbb{P}(U_1\in A{\rm\ o\ }U_2\in B)\\ &=\mathbb{P}\left((U_1,U_2)\in(A\times[0,1])\cup([0,1]\times B)\right)\\ &\ge\mathbb{P}\left((U_1,U_2)\in D\right)\\ &=1. \end{align>

---

Ahora daré una prueba del lema, que requerirá pasar por varios casos. Dado $\pi_i\colon\mathbb{R}^2\to\mathbb{R}$ ($i=1,2$) que denota la proyección sobre las coordenadas $x$ y $y$ respectivamente, $\pi_i(x_1,x_2)=x_i$, necesitamos encontrar una variable aleatoria $X$ que tome valores en $D$ tal que $\pi_1(X)$ y $\pi_2(X)$ son ambos uniformes en $[0,1]$. El lema entonces será respondido tomando $U_i=\pi_i(X).

Haré uso repetido del hecho de que si $X$ está uniformemente distribuido en una de las diagonales de un rectángulo $[a_1,b_1]\times[a_2,b_2]$ entonces $\pi_i(X)$ está uniformemente distribuido en $[a_i,b_i]$. La idea es encontrar un conjunto finito de rectángulos $R^{(k)}=[a^{(k)}_1,b^{(k)}_1]\times[a^{(k)}_2,b^{(k)}_2]$ y números $p^{(k)}\ge0$ que suman a $1$ tales que cada $R^{(k)}$ tiene un par de esquinas opuestas en $D$ (y, por convexidad, una diagonal en $D$), entonces podemos elegir $X$ para que esté uniformemente distribuido en la diagonal de $R^{(k)}$ con probabilidad $p^{(k)}$. Luego, $U_i=\pi_i(X)$ está uniformemente distribuido en el intervalo $[a^{(k)}_i,b^{(k)}_i]$ con probabilidad $p^{(k)}$, por lo que tiene una densidad de probabilidad $$p_i(x)=\sum_kp^{(k)}(b^{(k)}_i-a^{(k)}_i)^{-1}1_{\{a^{(k)}_i < x\le b^{(k)}\}}.$$ Lo haré de manera que la densidad de probabilidad sea $1$ en $(0,1].

Primero, sean $P_1=(x_1,0)$, $Q_1=(0,y_1)$, $P_2=(x_2,1)$ y $Q_2=(1,y_2)$ puntos de intersección de $D$ con los bordes de $R. Entonces, el cuadrilátero$P_1Q_1P_2Q_2$está contenido en$D

Por simetría, suponemos que $x_1\le x_2$, $x_1\le y_1$. Hay algunos casos a considerar (incluyo diagramas, con la zona sombreada siendo la envoltura convexa de los puntos $P_1,Q_1,P_2,Q_2$, que está contenida en $D, y las líneas rojas son las diagonales del rectángulo que soportan la distribución de$X).

Caso I: $y_1\ge y_2

En este caso, los cuatro rectángulos con diagonales $P_1Q_1$, $Q_1P_2$, $P_2Q_2$, $Q_2P_1$ no se intersectan. Junto con el rectángulo central, $[x_1,x_2]\times[y_1,y_2]$, que está contenido en $D, dividen$R. Explícitamente, los rectángulos $[0,x_1]\times[0,y_1]$, $[0,x_2]\times[y_1,1]$, $[x_2,1]\times[y_2,1]$, $[x_1,1]\times[0,y_2]$ y $[x_1,x_2]\times[y_2,y_1]$ dividen $R$ y cada uno tiene una diagonal en $D. Entonces, podemos elegir$X$ para que esté uniformemente distribuido en una diagonal de cualquiera de estos rectángulos con una probabilidad igual al área del rectángulo.

En los casos restantes, los rectángulos con diagonales $Q_1P_2$ y $Q_2P_1$ se superponen, por lo que la construcción en el Caso I no funciona.

Caso II: $x_1\le y_1\le x_2\le y_2$. En este caso, $P_1Q_1$ es la diagonal de un rectángulo que es más alto de lo que es ancho. Agregamos un rectángulo a la derecha de este para hacer un cuadrado, y tomamos diagonales de estos. De manera similar, agregamos un rectángulo debajo del que tiene diagonal $P_2Q_2$ para hacer un cuadrado, y tomamos diagonales de estos. Estos dos cuadrados no se superponen, por lo que podemos agregar el segmento de línea en $D$ que une las esquinas más cercanas de estos cuadrados (que es una diagonal del cuadrado de $[y_1,x_2]^2). Más explícitamente, usando 'BL-TR' para significar 'diagonal de abajo a arriba a la derecha', etc.

• $R^{(1)}=[0,x_1]\times[0,y_1]$, $p^{(1)}=x_1$ (TL-BR = $P_1Q_1$ está en $D).
• $R^{(2)}=[x_1,y_1]\times[0,y_1]$, $p^{(2)}=y_1-x_1$ (BL-TR está en $D).
• $R^{(3)}=[y_1,x_2]\times[y_1,x_2]$, $p^{(3)}=x_2-y_1$ (BL-TR está en $D).
• $R^{(4)}=[x_2,1]\times[x_2,y_2]$, $p^{(4)}=y_2-x_2$ (BL-TR está en $D).
• $R^{(5)}=[x_2,1]\times[y_2,1]$, $p^{(5)}=1-y_2$ (BR-TL = $P_2Q_2$ está en $D).

Caso III: $x_1\le y_1\le y_2\le x_2$. Esta es una disposición similar al Caso II, excepto que el rectángulo con diagonal $P_2Q_2$ es más alto de lo que es ancho, por lo que agregamos un rectángulo a la izquierda de este en lugar de debajo para hacer un cuadrado.

• $R^{(1)}=[0,x_1]\times[0,y_1]$, $p^{(1)}=x_1$ (TL-BR = $P_1Q_1$ está en $D).
• $R^{(2)}=[x_1,y_1]\times[0,y_1]$, $p^{(2)}=y_1-x_1$ (BL-TR está en $D).
• $R^{(3)}=[y_1,y_2]\times[y_1,y_2]$, $p^{(3)}=y_2-y_1$ (BL-TR está en $D).
• $R^{(4)}=[y_2,x_2]\times[y_2,1]$, $p^{(4)}=x_2-y_2$ (BL-TR está en $D).
• $R^{(5)}=[x_2,1]\times[y_2,1]$, $p^{(5)}=1-x_2$ (TL-BR = $P_2Q_2$ está en $D).

Caso IV: $x_1\le x_2 < y_1 < y_2. En este caso, cualquier par de cuadrados (con orientación estándar) que contengan las diagonales$P_1Q_1$y$P_2Q_2$ se superponen, por lo que la construcción en los casos I y II no funciona.

El punto $(x_2,y_1)$ está en $D, y existe un$a_0\in[0,y_1], b_0\in[x_2,1]$único tal que$(x_2,a_0)$y$(b_0,y_1)$están en$Q_2P_1. Explícitamente, $a_0=y_2\frac{x_2-x_1}{1-x_1}$ y $b_0=y_2^{-1}(y_1+x_1(y_2-y_1)). Escogiendo$a\in[a_0,y_1]$y$b\in[x_2,b_0], de manera que $(x_2,a)$ y $(b,y_1)$ estén en $D, tomamos

• $R^{(1)}=[0,x_1]\times[0,y_1]$, $p^{(1)}=x_1$ (TL-BR = $P_1Q_1$ está en $D).
• $R^{(2)}=[x_1,x_2]\times[0,a]$, $p^{(2)}=x_2-x_1$ (BL-TR está en $D).
• $R^{(3)}=[x_2,b]\times[a,y_1]$, $p^{(3)}=y_1-x_2$ (BL-TR está en $D).
• $R^{(4)}=[b,1]\times[y_1,y_2]$, $p^{(4)}=y_2-y_1$ (BL-TR está en $D).
• $R^{(5)}=[x_2,1]\times[y_2,1]$, $p^{(5)}=1-y_2$ (BR-TL = $P_2Q_2$ está en $D).

Se puede ver que utilizando esta distribución, $U_2=\pi_2(X)$ es uniforme en $[y_1,1] con probabilidad$1-y_1$y es uniforme en cada uno de$[0,a]$y$[a,y_1]. La probabilidad de que $U_2$ esté en $[0,a]$ es $x_1\frac{a}{y_1}+(x_2-x_1). Para que$U_2$sea uniforme en$[0,1] necesitamos resolver $x_1\frac{a}{y_1}+(x_2-x_1)-a=0. Se puede verificar que esto es negativo para$a=a_0$y positivo para$a=y_1, por lo que se puede resolver para algún $a$ en $[a_0,y_1]. Explícitamente,$a=y_1\frac{x_2-x_1}{y_1-x_1). Del mismo modo, escojiendo $b=(y_2-x_2)^{-1}(y_1+x_2(y_2-y_1-1)) da la distribución uniforme para$U_1=\pi_1(X).