Creación de particiones en el plano en tres conjuntos la intersección de los vértices de cada cuadrado de lado 1?

Question

Q1. Es posible dividir el plano en tres conjuntos tales que cada uno de ellos contiene al menos uno de los vértices de cada cuadrado de lado 1 ? (Me refiero a todas las plazas de lado de longitud 1, no sólo a aquellos con lados paralelos a los ejes de coordenadas.)

Q2. Deje $n$ ser el mayor entero tal que el avión podría ser dividido en $n$ conjuntos tales que cada uno de ellos contiene al menos uno de los vértices de cada cuadrado de lado 1. Es fácil ver que $2\le n \le 4$. ¿Cuál es el valor de $n$? Cualquier referencia? Edit. @Zander a continuación demostrado que $n=4$ no es posible (esto es un nuevo resultado? No esperaba que la $n=4$ sería posible, pero yo no tenía una prueba).

Q3. Las variaciones de la pregunta anterior, cuando, en lugar de los vértices de un cuadrado con lado de la $1$, podemos tomar y corregir cualquier subconjunto $S$ del avión. Deje $n(S)$ ser el mayor entero tal que el avión podría ser dividido en $n(S)$ conjuntos tales que cada uno de ellos se cruza cada congruentes (tal vez de la orientación de la conservación) copia de $S$. Claramente $1\le n(S) \le |S|$. ¿Cuál es el valor de $n(S)$? Parte de la respuesta en este caso sería encontrar adecuado $S$ para que esta pregunta es muy interesante. Hay referencias a trabajar a lo largo de estas líneas que ha sido hecho? (La pregunta parece natural para finito de conjuntos, pero quizás también interesante para algunos infinito $S$.)

Answer 1

Q1. Sí. En primer lugar, tenga en cuenta que el avión puede ser dividido como el conjunto de todas las líneas con pendiente 1. Estas líneas pueden ser indexados por sus intersecciones en x, por lo definen $L_k$ a ser la línea con intercepto en x $k$, que tiene por ecuación $y=x-k$. Ahora, definir tres grupos de la siguiente manera:

$$A = \{k \in \mathbb{R} \mid \lfloor k \rfloor \equiv 0 \pmod 3 \}$$ $$B = \{k \in \mathbb{R} \mid \lfloor k \rfloor \equiv 1 \pmod 3 \}$$ $$C = \{k \in \mathbb{R} \mid \lfloor k \rfloor \equiv 2 \pmod 3 \}$$

Los tres conjuntos que la partición del plano tales que cada uno de ellos contiene al menos uno de los vértices de cada cuadrado de lado 1 se

$$S_A = \bigcup_{k \ \in \ A} L_k \ \ \ \ \ \ \ \ \ S_B = \bigcup_{k \ \in \ B} L_k \ \ \ \ \ \ \ \ \ S_C = \bigcup_{k \ \in \ C} L_k$$

Cualquier cuadrado de lado de longitud 1 es de la forma $\{(x,y), (x+1,y), (x,y+1), (x+1,y+1) \}$ algunos $x,y \in \mathbb{R}$. Los interceptos en x de la pendiente-1 líneas que estos puntos se encuentran en son $x-y -1$, $x-y$, y $x-y+1$ (la primera y la cuarta puntos ambos tienen intercepto en x $x-y$).

Ahora, tenga en cuenta que$\lfloor x-y-1 \rfloor = \lfloor x-y \rfloor - 1$$\lfloor x-y+1 \rfloor = \lfloor x-y \rfloor + 1$, y que ninguno de $\lfloor x-y \rfloor - 1$, $\lfloor x-y \rfloor$, y $\lfloor x-y \rfloor + 1$ son congruentes el uno al otro mod 3. Por lo tanto cada uno de los conjuntos $S_A$, $S_B$, y $S_C$ contiene al menos uno de los cuadrados de los cuatro vértices.

Answer 2

Para Q2 $n=4$ no es posible.

Deje $c(\mathbf{x}) \in \{A,B,C,D\}$ denotar el color de un punto de $\mathbf{x}$. Como se señaló en los comentarios, una de 4 para colorear con cada unidad cuadrada con cuatro diferentes colores de los vértices requeriría

C1: No pares de puntos separados por una distancia de $1$ o $\sqrt 2$ puede tener el mismo color.

A partir de C1 podemos mostrar:

C2: Para cualquier punto de $\mathbf{o}$ y cualquier ortonormales de vectores $\mathbf{u},\mathbf{v}$ $$ c(\mathbf{x}+2\mathbf{u}) = c(\mathbf{x}) \text{ para todo } \mathbf{x}=\mathbf{s}+m\mathbf{u}+n\mathbf{v} $$ o $$ c(\mathbf{x}+2\mathbf{v}) = c(\mathbf{x}) \text{ para todo } \mathbf{x}=\mathbf{s}+m\mathbf{u}+n\mathbf{v} $$ para $m,n\in\mathbb{Z}$. Es decir, $c$ es periódica con período de $2\mathbf{u}$ o $2\mathbf{v}$ en el entramado generado por $\mathbf{u},\mathbf{v}$.

A partir de C1 y C2 , se obtiene:

C3: Para $\mathbf{o},\mathbf{u},\mathbf{v}$ como encima hay algunos $\mathbf{x}=\mathbf{o}+m\mathbf{u}+n\mathbf{v}$ con $$ c(\mathbf{x}) = c(\mathbf{x}+2\mathbf{u}) = c(\mathbf{x}+2\mathbf{v}) $$ o $$ c(\mathbf{x}) = c(\mathbf{x}+4\mathbf{u}) = c(\mathbf{x}+4\mathbf{v}) $$

Y C2 y C3 contradicen C1, por lo tanto no hay tal coloración es posible.

Prueba: C1$\implies$C2:

Cualquiera de las $c(\mathbf{o}+2m\mathbf{u})=c(\mathbf{o}),c(\mathbf{o}+(2m+1)\mathbf{u})=c(\mathbf{o}+\mathbf{u}) $ todos los $m$, o bien hay algo de $\mathbf{x} = \mathbf{o}+m_0\mathbf{u}$ $c(\mathbf{x}),c(\mathbf{x}+\mathbf{u}),c(\mathbf{x}+2\mathbf{u})$ tres colores diferentes, wlog $A,B,C$. En ese caso, las restricciones de C1 únicamente determinan $c(\mathbf{x}+n\mathbf{v})$. Específicamente $c(\mathbf{x}+2n\mathbf{v})=A$$c(\mathbf{x}+(2n+1)\mathbf{v})=C$. En una imagen, comenzando con $\mathbf{x}$ en la parte superior izquierda con $\mathbf{u}$ va a la derecha y $\mathbf{v}$ bajando: $$ \begin{array}{cccc} \cdots & A & B & C & \cdots \\ \cdots & C & D & A & \cdots \\ \cdots & A & B & C & \cdots \\ \cdots & C & D & A & \cdots \\ \cdots & A & B & C & \cdots \\ & \vdots & \vdots & \vdots \end{array} $$ Por lo tanto, ya sea en la fila que contenga $\mathbf{o}$ o de la columna que contiene a $\mathbf{x}$ es periódica con período de $2\mathbf{u}$ o $2\mathbf{v}$ respectivamente, y es fácil ver que, o bien implica que el resto de la celosía es periódica con el mismo período.

C1 y C2 $\implies$ C3:

A partir de C2 wlog asumir para colorear en el $\mathbf{o},\mathbf{u},\mathbf{v}$ celosía tiene período de $2\mathbf{u}$. Hay algunos $\mathbf{x}$ con $c(\mathbf{x}+2\mathbf{v})=c(\mathbf{x})=c(\mathbf{x}+2\mathbf{u})$, que satisface la primera condición de C3, o de lo $c(\mathbf{x}+2\mathbf{v})\ne c(\mathbf{x})$ por cada $\mathbf{x}$ en la red. En ese caso wlog deja que los colores de $\mathbf{o},\mathbf{o}+\mathbf{u},\mathbf{o}+\mathbf{v},\mathbf{o}+\mathbf{u}+\mathbf{v}$ $A,B,C,D$ respectivamente, y esta condición, junto con las restricciones de C1 puede llenar el colorante en el enrejado. En una imagen, se debe seguir: $$ \begin{array}{cccc} \cdots & A & B & A & \cdots \\ \cdots & C & D & C & \cdots \\ \cdots & B & A & B & \cdots \\ \cdots & D & C & D & \cdots \\ \cdots & A & B & A & \cdots \\ & \vdots & \vdots & \vdots \end{array} $$ Por lo tanto $c(\mathbf{o}+4\mathbf{v}) = c(\mathbf{o}) = c(\mathbf{o}+4\mathbf{u})$.

C2 y C3 $\implies$ no C1:

En una red con $\mathbf{o},\mathbf{u},\mathbf{v}$ como el anterior, desde C3 hay un $\mathbf{X}$ $\mathbf{Y}=\mathbf{X}+t\mathbf{u}, \mathbf{Z}=\mathbf{X}+t\mathbf{v}$ y $$ c(\mathbf{X}) = c(\mathbf{Y}) = c(\mathbf{Z}) $$ para cualquiera de las $t=2$ o $t=4$. Hay ortonormales de vectores $\mathbf{u}',\mathbf{v}'$ tal que $\mathbf{Y}' = \mathbf{X}+t\mathbf{u}', \mathbf{Z}' = \mathbf{X}+t\mathbf{v}'$$\left\vert \mathbf{YY}'\right\vert = \left\vert \mathbf{ZZ}'\right\vert = 1$.

Entonces por C2 cualquiera de las $c(\mathbf{Y}')=c(\mathbf{X})=c(\mathbf{Y})$ o $c(\mathbf{Z}')=c(\mathbf{X})=c(\mathbf{Z})$, contradiciendo C1.